Problem A. Attack
It was the easiest problem. "Do what they ask".
Problem B. Big Pyramid
This one was a so tricky that I didn't see the trick. (Thanks to Ulan Degenbaev for such a nice problem!) I submitted this problem seven times and didn't get AC :) I was so mad, that I eventually gave up and went to bed. I solved this problem today though. The problem asked to find the largest pyramid given the elevation map on the area. Area was dived into H by W cells and for each cell they give us how many blocks can possibly stand on it. Pyramid of height N is defined the following way: in the very center there is one block of size 1x1x1, under this block there is another set of 9 blocks, i.e. 3x3, finally on the Nth level of the pyramid there are 2*N-1 x 2*N-1 blocks. The trick was that some cells are possibly covered with "sand". Which means if the elevation area looks like this:
3 3 3
3 2 3
3 3 3
We still know there is a pyramid of height two with the center located at cell (1,1), i.e. the actual pyramid is like this:
1 1 1
1 2 1
1 1 1
The excess is the SAND on the pyramid!
So, keeping that in mind we can easily design O(H^2*W^2) algorithm to find largest pyramid of the area. Consider all possible centers of the pyramid and then try to expand from that center. It's easy to code, I wish I did it during the contest.
Edit: Thanks to the dfyz, as he pointed out there is a better O(H*W*max(H,W)) solution. I was able to improve my previous O(H^2*W^2) solution to run in O(H*W*max(H,W)) time as well. That was possible because my "expand" method was based on finding minimum element on the certain interval of a row or a column. So, pre-computation of those values reduces the running time to the desired
Problem C. Coloring Palette
This was an implementation problem. Especially easy to code if you know STL and how to write your own compare function for the STL's sort method.
Problem D. Draw Rectangles
This is a well-known problem. First we draw red rectangles on the plane. Then we draw blue rectangles on the plane. As usual rectangles can intersect overlap, etc. So the problem asks to find area of the red rectangles. It can be solved in many ways. One approach is to do sweep algorithm.
Problem E. Elementary Algebra
Nice problem. Each letter is a node in the graph. First we merge all nodes that appear in the X=Y expressions. The we say there is an edge from X to Y if there is an expression X>Y, also there is an edge from Y to X if there is an expression X<Y. then can be reduced to transitive closure problem or figuring out whether exists in the if there a cycle answer is "NO" otherwise "YES".
I didn't figure out the problem during contest. I knew it was an easy DP, I just didn't see it right away. Basically given two strings (say A and B) you have to find how many strings of minimal length contain both of the given strings as substrings. The DP is the following:
1) Let D[i][j] - be the length of the minimal string that contains strings A[1...i] and B[1..j];
2) Let B[i][j] - be the number of such strings.
If you're interested in how to compute those values read next paragraph:
D[i][j] = D[i-1][j-1], if A[i] is equals to B[j], otherwise D[i][j]=min(D[i-1][j],D[i][j-1])+1.
Similarly B[i][j]=B[i-1][j-1], if A[i]==B[j],
otherwise let best=min(D[i-1][j],D[i][j-1]),
if D[i-1][j]==best then we add B[i-1][j] to B[i][j],
If best==D[i][j-1] then we also add B[i][j-1] to B[i][j].
Finally, I guess it's obvious to figure out where the answer to the problem would be.
I'm quite surprised to hear an O(W^2*H^2) algorithm was enough to get B accepted. My teammate ran a straightforward implementation on his machine on a huge test, and it timed out, so he ended up coding and submitting an O(W*H*max(W,H)) one. Guess you were lucky. :)
ReplyDeleteHere is the code, if you want to look at it :)
ReplyDeleteGreat editorial! Could you explain what the thought process was when you were coming up with this:
ReplyDeleteif(best == D[i-1][j]) B[i][j] += B[i-1][j];
if(best == D[i][j-1]) B[i][j] += B[i][j-1];
Basically, when computing value of D[i][j], if S1[i] is not equal to S2[j] then there might be one or two possible best sub-problems to choose from:
ReplyDelete1st sub-problem: take the best solution for the S1[1..i-1] and S2[1..j] which corresponds to the D[i-1][j] and add to that solution S1[i].
2. Take the best solution for the S1[1..i] and S2[1..j-1] which corresponds to the D[i][j-1] and add to that solution S2[j].
In case of both of the sub-problems (D[i-1][j] and D[i][j-1]) are equal (i.e. the length of best string) we have two possibilities to choose from
and thus, while computing B[i][j] we need to add both B[i-1][j] and B[i][j-1].
In other cases (when either D[i][j-1] is smaller or D[i-1][j] is smaller) we only add one corresponding value (either B[i][j-1] and B[i-1][j]).
Does that makes any sense at all?