1
00:00:00,240 --> 00:00:07,740
Basically, what we had to do here is that we have four integers, an M, A, M, B, and all of them

2
00:00:07,800 --> 00:00:09,030
are at most 50.

3
00:00:09,060 --> 00:00:10,680
So again, they are really small.

4
00:00:10,890 --> 00:00:11,130
Right.

5
00:00:14,010 --> 00:00:21,450
What we should basically do is create a matrix which has an rows and EM columns.

6
00:00:22,930 --> 00:00:24,120
Binary matrix.

7
00:00:24,300 --> 00:00:24,600
Right.

8
00:00:24,690 --> 00:00:31,350
And so just values of zero and ones such that we need to have to satisfy two properties.

9
00:00:31,740 --> 00:00:37,680
The first one is that each row of this matrix contains exactly a once, the second one.

10
00:00:37,740 --> 00:00:40,950
Each column of the matrix contains exactly B once.

11
00:00:41,420 --> 00:00:41,690
Right.

12
00:00:42,570 --> 00:00:43,170
So that's all.

13
00:00:44,690 --> 00:00:46,550
I have to say yes.

14
00:00:47,600 --> 00:00:51,290
If there is such matrix or no a.

15
00:00:52,210 --> 00:00:52,720
There isn't.

16
00:00:53,110 --> 00:00:55,980
And, of course, if there is to output the matrix, right.

17
00:00:56,800 --> 00:00:57,070
All right.

18
00:00:57,080 --> 00:01:01,590
So I see here constructive algorithms, flows, graph matings, MUF.

19
00:01:01,960 --> 00:01:03,430
Now, there is no need for that.

20
00:01:04,620 --> 00:01:13,490
When I think the proof needs graph and matching and something like that, but we won't get in the proof

21
00:01:13,490 --> 00:01:14,330
of the algorithm.

22
00:01:14,360 --> 00:01:20,360
But let's just stay logically and solve it intuitively.

23
00:01:20,360 --> 00:01:20,630
Right.

24
00:01:21,590 --> 00:01:23,030
So what happens?

25
00:01:23,660 --> 00:01:28,500
Well, when I have these kind of problems in which I have to print yes or no.

26
00:01:29,620 --> 00:01:34,780
I first see the empty half of the glass and they think about when should I print?

27
00:01:34,800 --> 00:01:34,970
No.

28
00:01:35,620 --> 00:01:37,470
So when is it impossible?

29
00:01:38,580 --> 00:01:40,760
To construct such a matrix.

30
00:01:41,900 --> 00:01:51,050
Well, each row has exactly a once, each column has exactly B once.

31
00:01:53,910 --> 00:01:59,940
If each row has exactly a ones, the number of ones is exactly and crossed a.

32
00:02:01,130 --> 00:02:03,610
If each column has exactly be once.

33
00:02:04,760 --> 00:02:07,910
The number of whales should also be equal to M crossed.

34
00:02:07,960 --> 00:02:08,230
B.

35
00:02:09,570 --> 00:02:11,220
So this is the first thing I'm going to check.

36
00:02:11,850 --> 00:02:18,010
First of all, I'm going gonna check if and crossed A equals B crossed em.

37
00:02:19,200 --> 00:02:20,880
If it doesn't, I print.

38
00:02:20,910 --> 00:02:21,260
No.

39
00:02:21,660 --> 00:02:23,140
If it does, I print.

40
00:02:23,190 --> 00:02:23,490
Yes.

41
00:02:23,550 --> 00:02:25,500
I suppose I can do this.

42
00:02:26,220 --> 00:02:27,470
And let me tell you why.

43
00:02:27,480 --> 00:02:35,610
I suppose that because at this point I have floatable the problem in the following way.

44
00:02:36,120 --> 00:02:42,660
Basically what I need to do is for each row choose exactly eight columns.

45
00:02:43,720 --> 00:02:44,800
And increment.

46
00:02:46,560 --> 00:02:48,840
This total sum on that column.

47
00:02:49,350 --> 00:02:49,620
Right.

48
00:02:50,310 --> 00:02:52,680
So what can happen here?

49
00:02:55,810 --> 00:02:58,180
That do cost them one.

50
00:02:59,430 --> 00:03:00,760
All right, I got some here.

51
00:03:00,820 --> 00:03:01,350
All right, good.

52
00:03:01,780 --> 00:03:03,670
So let's do an 80 percent.

53
00:03:05,080 --> 00:03:10,440
But you can you could think about this in the following way, you can think that.

54
00:03:12,260 --> 00:03:18,690
For each row, I basically choose a different columns and I increase their size.

55
00:03:20,280 --> 00:03:25,920
So what I can say here is that I can start if something like column.

56
00:03:26,940 --> 00:03:34,890
Sum's unary column sums, but which has each and every column won two.

57
00:03:37,030 --> 00:03:38,650
All the way to column M.

58
00:03:40,090 --> 00:03:43,020
But so M minus one, let's say, and M here.

59
00:03:43,560 --> 00:03:47,160
And initially the someone each column is zero.

60
00:03:47,280 --> 00:03:47,520
Right.

61
00:03:47,530 --> 00:03:49,230
Because I don't have anything on that column.

62
00:03:49,770 --> 00:03:50,920
So the someone each column is you.

63
00:03:52,200 --> 00:03:53,550
And for each euro.

64
00:03:54,930 --> 00:03:56,790
Let's see here step number one.

65
00:03:58,660 --> 00:03:59,710
Step number two.

66
00:04:01,680 --> 00:04:04,260
And so on and so forth until step number.

67
00:04:06,290 --> 00:04:11,450
So for each of the rows, I basically choose a different columns.

68
00:04:12,600 --> 00:04:14,640
And I increased their son by one.

69
00:04:18,830 --> 00:04:23,270
First, I thought that I will always choose exactly eight columns.

70
00:04:23,300 --> 00:04:23,630
Right.

71
00:04:24,050 --> 00:04:25,280
So eight columns.

72
00:04:26,300 --> 00:04:27,480
Each have this some.

73
00:04:28,890 --> 00:04:30,030
You have the some.

74
00:04:30,960 --> 00:04:33,850
Less, strictly, less then be.

75
00:04:34,830 --> 00:04:37,410
And I just place one day.

76
00:04:38,860 --> 00:04:47,980
The problem with doing this is that you aren't going to feel some columns very quick.

77
00:04:48,360 --> 00:04:48,650
Right.

78
00:04:49,300 --> 00:04:51,400
And I think I have an example for that.

79
00:04:52,590 --> 00:04:53,250
Do I?

80
00:04:55,050 --> 00:04:59,070
I don't know if I have, but anyways, the problems were something like.

81
00:04:59,100 --> 00:05:03,900
So first of all, I thought, all right, for each of these steps.

82
00:05:04,920 --> 00:05:11,670
I'm gonna go through the columns and I'm gonna pick a columns which have some strickler's, then B and

83
00:05:11,670 --> 00:05:12,960
that's all increment those.

84
00:05:14,130 --> 00:05:20,370
The problem with this greedy approach is that you are going to be in increment some columns very, very

85
00:05:20,370 --> 00:05:24,660
quick and they are going to become B and basically you are filling them.

86
00:05:26,240 --> 00:05:28,250
You are, yeah.

87
00:05:28,650 --> 00:05:29,990
You are feeling them right?

88
00:05:30,020 --> 00:05:32,330
There some gets to be really quick.

89
00:05:33,680 --> 00:05:38,090
And when it does, basically that column is unavailable anymore.

90
00:05:38,270 --> 00:05:38,600
Right.

91
00:05:38,660 --> 00:05:47,360
So what happened in the previous approach is that let's say if A was equal to four, basically at each

92
00:05:47,360 --> 00:05:51,640
step, I've taken the same four columns B times.

93
00:05:51,650 --> 00:05:52,010
Right.

94
00:05:52,280 --> 00:05:58,580
So on the first B steps, I just increased those columns by one, those columns by one, those columns

95
00:05:58,580 --> 00:05:59,070
by one row.

96
00:05:59,960 --> 00:06:04,820
So I only do that because they are the first columns that I find.

97
00:06:05,060 --> 00:06:06,230
We have some less than B.

98
00:06:06,800 --> 00:06:08,360
So after B steps.

99
00:06:10,270 --> 00:06:12,730
These columns become unavailable.

100
00:06:14,100 --> 00:06:23,160
And after a couple of steps, a lot of columns will become unavailable and I won't be able to choose

101
00:06:23,790 --> 00:06:29,940
exactly a balance which have some strictly let them be right.

102
00:06:30,420 --> 00:06:30,690
So.

103
00:06:31,790 --> 00:06:38,060
I have to be a little bit more cautious and calculated with how I pick those columns, because if I

104
00:06:38,060 --> 00:06:45,170
pick the seeing columns over and over again, the number of available columns in which I can store a

105
00:06:45,170 --> 00:06:45,680
one.

106
00:06:46,250 --> 00:06:46,580
Right.

107
00:06:47,210 --> 00:06:50,980
Are going to is going to decrease very quick.

108
00:06:50,990 --> 00:06:51,260
Right.

109
00:06:52,280 --> 00:06:58,740
So I need to do something such that on each step I choose a columns.

110
00:06:59,090 --> 00:07:02,450
But I don't end up choosing the same columns over and over again.

111
00:07:03,410 --> 00:07:06,350
And then the whole idea came to me.

112
00:07:06,800 --> 00:07:09,260
I don't know how to prove it super mathematically.

113
00:07:09,260 --> 00:07:10,700
What you probably don't want that.

114
00:07:11,030 --> 00:07:11,780
It's super simple.

115
00:07:12,170 --> 00:07:16,640
Instead of choosing a random columns with some strictly less them be.

116
00:07:18,130 --> 00:07:21,340
You choose the a smallest.

117
00:07:29,620 --> 00:07:30,040
And that's OK.

118
00:07:30,760 --> 00:07:34,120
So you basically have em total columns.

119
00:07:34,150 --> 00:07:34,450
Right.

120
00:07:34,960 --> 00:07:36,790
You have a total of M columns.

121
00:07:38,240 --> 00:07:39,110
You start with.

122
00:07:41,050 --> 00:07:41,890
Only zeros.

123
00:07:43,600 --> 00:07:51,670
And at each and every step you have here, some sumps, you take those columns which have some strictly

124
00:07:51,670 --> 00:07:52,410
let them be.

125
00:07:53,080 --> 00:07:59,920
And instead of picking a random columns, you just pick the smallest column sums and that's all right.

126
00:08:00,310 --> 00:08:05,860
So basically, for each and every step, again, because the number of rows and columns is very small.

127
00:08:06,070 --> 00:08:07,930
I could just brute force.

128
00:08:08,500 --> 00:08:12,640
So for each and every step, I go through the set for the columns.

129
00:08:12,790 --> 00:08:13,090
Right.

130
00:08:14,410 --> 00:08:19,630
And I iStore this column sums in some oray, right?

131
00:08:20,230 --> 00:08:20,780
Call Assam's.

132
00:08:20,890 --> 00:08:21,400
I can tell.

133
00:08:21,490 --> 00:08:22,290
Caller sounds OK.

134
00:08:22,750 --> 00:08:25,630
And basically I keep this very sorted.

135
00:08:26,110 --> 00:08:27,250
You can do this smarter.

136
00:08:27,250 --> 00:08:33,220
We have a priority cure a said or you can just sort of disarray over and over again for each of the

137
00:08:33,220 --> 00:08:33,600
steps.

138
00:08:33,610 --> 00:08:33,870
Right.

139
00:08:34,180 --> 00:08:35,680
So for each and every step.

140
00:08:36,850 --> 00:08:37,630
I take this every.

141
00:08:41,150 --> 00:08:42,470
Sought callers some.

142
00:08:43,280 --> 00:08:47,650
And I just pick the A first the first eight columns anyway.

143
00:08:48,460 --> 00:08:48,700
And.

144
00:08:49,660 --> 00:08:51,150
Have ones there and that's it.

145
00:08:51,620 --> 00:08:56,440
So break up, first of all, chicken of a crust and equals M crust.

146
00:08:56,490 --> 00:08:58,440
B if not print.

147
00:08:58,480 --> 00:08:58,840
No.

148
00:08:59,470 --> 00:09:00,820
If yes, then print.

149
00:09:00,850 --> 00:09:01,240
Yes.

150
00:09:01,750 --> 00:09:05,610
And for having a solution, don't be random.

151
00:09:05,650 --> 00:09:06,610
Those columns.

152
00:09:07,000 --> 00:09:14,860
But be smarter about it and always pick from the columns which still are available.

153
00:09:14,890 --> 00:09:17,050
So have the some strickler's them be big.

154
00:09:17,050 --> 00:09:18,170
The smallest ones.

155
00:09:18,310 --> 00:09:18,640
Right.

156
00:09:18,760 --> 00:09:19,180
Cool.

157
00:09:19,780 --> 00:09:22,960
If you want to see the source code, it's not that hard.

158
00:09:23,260 --> 00:09:29,440
So basically as I've told you and crossed a m crust B if they are different now, add a C out.

159
00:09:29,470 --> 00:09:29,980
Yes.

160
00:09:30,310 --> 00:09:36,820
And what I did is that for each and every row between one and N, I took the vector of Peyer calls,

161
00:09:36,910 --> 00:09:38,170
which is the column sums.

162
00:09:38,560 --> 00:09:40,710
And for each column which has a sum.

163
00:09:40,870 --> 00:09:41,210
Right.

164
00:09:41,230 --> 00:09:43,530
Counter was the number of ones there.

165
00:09:43,960 --> 00:09:44,770
Less than B.

166
00:09:45,220 --> 00:09:48,310
I push it into this vector and I saw this vector.

167
00:09:48,340 --> 00:09:55,260
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

168
00:09:55,270 --> 00:09:55,660
care.

169
00:09:56,170 --> 00:09:59,690
And after sorting, I just take the first A and they take that column.

170
00:10:00,010 --> 00:10:01,210
I increase the counter.

171
00:10:02,050 --> 00:10:03,610
I place a one there.

172
00:10:04,080 --> 00:10:04,970
And basically that's it.

173
00:10:04,990 --> 00:10:05,200
Right.

174
00:10:05,830 --> 00:10:15,280
So if you want to prove that it is always correct to pick the smallest A integers and increment them.

175
00:10:15,640 --> 00:10:17,500
Because it seems right.

176
00:10:17,650 --> 00:10:18,550
It's intuitive.

177
00:10:18,910 --> 00:10:24,130
But in order to prove it mathematically that it's hundred percent correct, I think you're going to

178
00:10:24,130 --> 00:10:26,150
need some furious from Graph Fury.

179
00:10:26,710 --> 00:10:30,200
I think I've learned them in university or something, but of course they forgot themselves.

180
00:10:30,830 --> 00:10:32,650
You're going to have to do your research.

181
00:10:32,950 --> 00:10:33,960
But that was it.