Div I Hard: KnightsOut
A very interesting problem. I couldn't think of much, I noticed that cases in which the minimum side is less than 2, can be solved using dp or other simple methods. So you would only need to handle the cases in which both dimensions are greater than 3. It seems Petr had a similar idea, but it is far, far away from what I could do in 44 minutes.
Div I Medium: AlternatingLane
This also seemed like a good problem. I imagined plenty of things. Noticed a dp [100000][2][50] could work as long as I figured out a way to do each state in O(high[i]). I think there is a way to do it by accumulating the results for each [previous][0,1][n] for each n. and then you can use a subtraction to get the sum, and the summation formula to get the sum of differences between the previous value and the new one. But it needs work. Something I noticed is that when the lane is already alternating after picking the heights, you are not allowed to cut down trees, even if that would yield a higher beauty. It seems like such thing would make my dp idea more complicated.
When there were around 14 minutes left to the match, I was still far from thinking of a definite solution for the 500. I was paying attention to the summaries and it seemed like it was a good idea to reserve some more time to it. And it was unlikely I would think of the solution and code it in less than three minutes. So I switched to the easy.
Div I Easy: Painting
A cool problem that was actually coding-based instead of math-based like the previous 60 Div 1 easies were... A nice change. I managed to solve it but...
Blunder: I have made many mistakes while coding the solution for this problem, so even though I started coding it right away, I still needed 12 minutes to finish debugging it. Unfortunately, I made a mistake, once I passed all the example cases, it occurred to me to try doing a timeout test "just in case". But think about it, even if I found out that the solution is too slow, I would not have had enough time to fix it (there were only two minutes left). Also, for some reason I made a lot of mistakes when trying to generate a large case with python. Fortunately, I came back to my senses and decided to compile and submit with some few seconds left for the match. This blunder cost me at least 10 points, which would translate in ~30 positions.
The result was a not-good but not-bad position, I earned 2 rating points (but I lost a lot of points last match).
So, here comes my explanation for the easy problem. I plan and hope to get explanations for the other problems seeing how member SRMs don't have editorials, and the problems seemed fun, but it depends on how much time I can manage to have.
Explaining the Div I Easy: Painting
Problem statement
We want to maximize S, the size of a SxS brush. In maximization problems, it often pays to change the option from "Maximize S" to "Is it possible to do it with a value S?". If we use the latter question, we can actually just iterate from higher values of S and keep decreasing S until it is possible to use such value. For example, try a size 50 brush, if it is possible to do it, return 50, then try a size 49 brush, and so and so until a good size is found or until the brush size becomes 1 (in which case we can be certain that the result is 1, as it is always possible to do it).
Since we now want to know if it is possible to use a SxS brush to paint the painting, how about the following algorithm? For every brush position (i,j) , if there is no white cell in the painting in the SxS area starting at (i,j), then we can paint a SxS black square in that area. If it is possible to paint such a black square, there is no reason not to paint the square, because we are allowed to paint the same cell more than once. So, how about we begin with a completely white board and then iterate through all the (i,j) cells in the board, and if it is possible to paint a SxS in each of the cells, just paint it. If at the end the board is equal to the painting, then it is possible to do it with a SxS brush.
Note that such algorithm will require O(min(W,H)) iterations for S, O(W*H) (i,j) iterations for each cell , and inside those iterations, we need to try SxS squares to check if they contain white cells or not and then to paint them. So, we can estimate the complexity to be O( min(W,H) * W*H * W*H ) . With W,H <= 50, that may appear to be too high for the two seconds limit, but in reality, it is not (In fact, the following code needs 67 ms in the worst case, I think a good complexity analysis should show it is actually very fast and the O() notation is hiding something.)
Sample code:
1 int isPossible( vector<string> & picture, int s) {
2 int w = picture.size(), h = picture[0].size();
3
4 // An initially-white board:
5 vector<string> board( w, string(h, 'W') );
6
7 for (int i=0; i<w-s+1; i++)
8 for (int j=0; j<h-s+1; j++) {
9 //pick (i,j):
10 bool can = true;
11
12 // is it possible to draw a SxS black square at (i,j) ?
13 for (int x=i; (x<i+s) && can; x++)
14 for (int y=j; (y<j+s) && can; y++) {
15 can = can && (picture[x][y] != 'W' );
16 }
17 if( can ) {
18 //it is possible, paint it:
19 for (int x=i; (x<i+s) && can; x++)
20 for (int y=j; (y<j+s) && can; y++) {
21 board[x][y]='B';
22 }
23 }
24 }
25 // if the board and the picture are equal,
26 // then it was possible to use a SxS brush:
27 return (board == picture);
28 }
29
30 int largestBrush(vector <string> picture)
31 {
32 int w = picture.size(), h = picture[0].size();
33
34 // try all possible values of s, until finding the
35 // largest valid one:
36 for (int s= std::min(w,h); s>1; s--) {
37 if( isPossible(picture, s) ) {
38 return s;
39 }
40 }
41 return 1;
42
43 }
During the match , I was too cautious and didn't trust the O( min(W,H) * W*H * W*H ) solution, I instead used binary search. Note that if it is possible to use a size SxS brush to paint the painting, then all brush sizes smaller than SxS will also make it possible (You can always make a SxS square by combining smaller squares). And the opposite is also true, if it is not possible to use a SxS brush, then larger brushes will also not be usable. This means that there would be a line dividing the possible brush sizes with the impossible ones, therefore, we can use binary search to find the maximum allowed size.
0 comments:
Post a Comment