Basically, what we had to do here is that we have four integers, an M, A, M, B, and all of them
are at most 50.
So again, they are really small.
Right.
What we should basically do is create a matrix which has an rows and EM columns.
Binary matrix.
Right.
And so just values of zero and ones such that we need to have to satisfy two properties.
The first one is that each row of this matrix contains exactly a once, the second one.
Each column of the matrix contains exactly B once.
Right.
So that's all.
I have to say yes.
If there is such matrix or no a.
There isn't.
And, of course, if there is to output the matrix, right.
All right.
So I see here constructive algorithms, flows, graph matings, MUF.
Now, there is no need for that.
When I think the proof needs graph and matching and something like that, but we won't get in the proof
of the algorithm.
But let's just stay logically and solve it intuitively.
Right.
So what happens?
Well, when I have these kind of problems in which I have to print yes or no.
I first see the empty half of the glass and they think about when should I print?
No.
So when is it impossible?
To construct such a matrix.
Well, each row has exactly a once, each column has exactly B once.
If each row has exactly a ones, the number of ones is exactly and crossed a.
If each column has exactly be once.
The number of whales should also be equal to M crossed.
B.
So this is the first thing I'm going to check.
First of all, I'm going gonna check if and crossed A equals B crossed em.
If it doesn't, I print.
No.
If it does, I print.
Yes.
I suppose I can do this.
And let me tell you why.
I suppose that because at this point I have floatable the problem in the following way.
Basically what I need to do is for each row choose exactly eight columns.
And increment.
This total sum on that column.
Right.
So what can happen here?
That do cost them one.
All right, I got some here.
All right, good.
So let's do an 80 percent.
But you can you could think about this in the following way, you can think that.
For each row, I basically choose a different columns and I increase their size.
So what I can say here is that I can start if something like column.
Sum's unary column sums, but which has each and every column won two.
All the way to column M.
But so M minus one, let's say, and M here.
And initially the someone each column is zero.
Right.
Because I don't have anything on that column.
So the someone each column is you.
And for each euro.
Let's see here step number one.
Step number two.
And so on and so forth until step number.
So for each of the rows, I basically choose a different columns.
And I increased their son by one.
First, I thought that I will always choose exactly eight columns.
Right.
So eight columns.
Each have this some.
You have the some.
Less, strictly, less then be.
And I just place one day.
The problem with doing this is that you aren't going to feel some columns very quick.
Right.
And I think I have an example for that.
Do I?
I don't know if I have, but anyways, the problems were something like.
So first of all, I thought, all right, for each of these steps.
I'm gonna go through the columns and I'm gonna pick a columns which have some strickler's, then B and
that's all increment those.
The problem with this greedy approach is that you are going to be in increment some columns very, very
quick and they are going to become B and basically you are filling them.
You are, yeah.
You are feeling them right?
There some gets to be really quick.
And when it does, basically that column is unavailable anymore.
Right.
So what happened in the previous approach is that let's say if A was equal to four, basically at each
step, I've taken the same four columns B times.
Right.
So on the first B steps, I just increased those columns by one, those columns by one, those columns
by one row.
So I only do that because they are the first columns that I find.
We have some less than B.
So after B steps.
These columns become unavailable.
And after a couple of steps, a lot of columns will become unavailable and I won't be able to choose
exactly a balance which have some strictly let them be right.
So.
I have to be a little bit more cautious and calculated with how I pick those columns, because if I
pick the seeing columns over and over again, the number of available columns in which I can store a
one.
Right.
Are going to is going to decrease very quick.
Right.
So I need to do something such that on each step I choose a columns.
But I don't end up choosing the same columns over and over again.
And then the whole idea came to me.
I don't know how to prove it super mathematically.
What you probably don't want that.
It's super simple.
Instead of choosing a random columns with some strictly less them be.
You choose the a smallest.
And that's OK.
So you basically have em total columns.
Right.
You have a total of M columns.
You start with.
Only zeros.
And at each and every step you have here, some sumps, you take those columns which have some strictly
let them be.
And instead of picking a random columns, you just pick the smallest column sums and that's all right.
So basically, for each and every step, again, because the number of rows and columns is very small.
I could just brute force.
So for each and every step, I go through the set for the columns.
Right.
And I iStore this column sums in some oray, right?
Call Assam's.
I can tell.
Caller sounds OK.
And basically I keep this very sorted.
You can do this smarter.
We have a priority cure a said or you can just sort of disarray over and over again for each of the
steps.
Right.
So for each and every step.
I take this every.
Sought callers some.
And I just pick the A first the first eight columns anyway.
And.
Have ones there and that's it.
So break up, first of all, chicken of a crust and equals M crust.
B if not print.
No.
If yes, then print.
Yes.
And for having a solution, don't be random.
Those columns.
But be smarter about it and always pick from the columns which still are available.
So have the some strickler's them be big.
The smallest ones.
Right.
Cool.
If you want to see the source code, it's not that hard.
So basically as I've told you and crossed a m crust B if they are different now, add a C out.
Yes.
And what I did is that for each and every row between one and N, I took the vector of Peyer calls,
which is the column sums.
And for each column which has a sum.
Right.
Counter was the number of ones there.
Less than B.
I push it into this vector and I saw this vector.
So as you can see I have a n crossed m log which is not very efficient, but they are small so I didn't
care.
And after sorting, I just take the first A and they take that column.
I increase the counter.
I place a one there.
And basically that's it.
Right.
So if you want to prove that it is always correct to pick the smallest A integers and increment them.
Because it seems right.
It's intuitive.
But in order to prove it mathematically that it's hundred percent correct, I think you're going to
need some furious from Graph Fury.
I think I've learned them in university or something, but of course they forgot themselves.
You're going to have to do your research.
But that was it.