This round is full of frustration and nervousness and fear that I cannot advance, and I did not. The plan clearly writes, be patient and focus on the problems. But everything goes chaos when I found myself stuck in problem 1 large.
A. a simple problem but requires some care in implementation. To count the number of pairs, you need to keep track of segments with exactly n consonants and then you can start from prevStart+1 to p1, inclusive, and end with p2 to len-1, inclusive, [p1..p2] marks the current segment of n consonants.
I had an extremely ugly code with lots of if/else and while/for inside of each other. Surprisingly the code is actually correct. But I lost my confidence while waiting for it to finish running large input, and thought I had an infinite loop somewhere. After the contest, I ran the code again and found it takes only 1m24s to finish. On the other hand I have to acknowledge that a properly implemented simpler code runs only a fraction of a second.
B. I figured out the small even when panicking, and so do over 1500 other contestants. For small you can advance to X and Y at increment of 1, by taking -k, then +(k+1) until done.
The large is rather daunting, as you need to finish with minimum number of moves, and algorithms with DP or shortest path do not seem to be viable. You need an EXPLICIT strategy. I hate this as this problem gave those who have seen it before an unfair advantage. This problem falls into the category that when you see it the first time, it takes extreme ingenuity to figure out the strategy, then coding is as simple as write a single for loop.
I think I was close, but not enough to finish.
First you know that sign does not matter, you can assume X and Y being non-negative, and you only need to flip the move accordingly.
Next you try to simplify the problem a bit. What if you have only one number, say X, instead of two numbers, how do you move to get X? One then sees that you can do 1, 2, 3, ..., k such that S[k-1] < X and S[k] >= X. Now if S[k] = X, then you are done. Otherwise S[k] > X. In this case we know we need to flip at least one number in 1, 2, ..., k-1 to make the sum equal X. However there is a catch. Flipping a number j to -j will change S[k] to S[k] - 2*j, in other words, flipping sign can never change the parity of S[k]. So we need S[k] to agree with X in parity, if not we need to get one more number k+1 so that S[k+1] agrees in parity with X.
Now consider two cases:
Case 1: S[k-1] < X and S[k] > X, and S[k] and X agree with parity. Then we can show that (S[k] - X) / 2 <= k. Notice that S[k] - X is even in this case. Simple algebra tells us that this is the same as S[k] <= X + 2k, which is S[k-1] <= X +k, and that obviously holds as we have S[k-1] < X.
Case 2: S[k-1] < X and S[k] > X and S[k] and X disagree with parity. Then we need (S[k+1] - X) / 2 <= k+1 so we can flip the sign of the number j = (S[k+1] - X) / 2. This turns out to be S[k] <= X+k+1, which is S[k-1] <= X+1, and obviously this holds.
Given above, we have actually figured out a way to make X, using minimum number of moves. Now how do we generalize to two numbers, X and Y?
Behold, the trick is.....
NOTHING. You heard it right, nothing, just like the response when Pau, the Panda asks for the secret ingredient. We use the same strategy for two numbers, X and Y.
Well, not quite, but it is close to the truth. Take a step back, and consider what is the necessary number of moves to get X and Y. If we can get X and Y, then we should be able to get |X| + |Y|, just combine the moves into 1 dimension. OK, so now what is necessary to get |X| + |Y|. Our previous discussion tells us that we need k moves such that S[k-1] < |X| + |Y| and S[k] >= |X| + |Y|. In case S[k] and |X| + |Y| disagree in parity, we need one more move, that is k+1. Clearly it is necessary, but why is it sufficient, or rather, is i actually sufficient? The problem setter is clever enough that he/she does not want those who can make only this far to pass, so he/she is asking for the actual moves instead of merely the number of moves, which I would have guessed by going this far.
Now why this k or k+1 moves is sufficient, and what is a strategy and did achieve X and Y simultaneously? There are many false starts for possible proofs, because some claims that one tries to make is simply false. Let's run an example to see what is going on. To make things easier we actually start from X, Y and decrease them to zero. The strategy? Always bring down the larger of the two, of course you take the one with larger abs value.
Let X = 3 and Y = 6, the above tells us that we need at least 1,2,3,4,5 moves.
X Y
1,2,3,4,5 3 6
1,2,3,4 3 1
1,2,3 1 1
1,2 2 1
1 0 1
0 0
OK, so you see it, and some conjectures, or false claims could be dismissed. The X and Y may not going down all the time, they might even go up temporarily. And X and Y could be both smaller than k, the next available move (although you can use move from 1 to k, it seems more reasonable to use move = k). However both X and Y did arrive at 0. Then what is the invariant in the iterations to make this final state eventually achieved?
The claim: at every iteration, S[k] >= |X| + |Y| and S[k] agree in parity with |X| + |Y|.
The corollary: X and Y must go down to 0 eventually, since k will go down to 0.
Proof of the claim: In the beginning it is true, so we have base case covered. After one move, w.l.o.g. we may assume X >= 0 and Y >= 0, and X >= Y. Now our move will update (X,Y) to (X-k, Y). We have two cases:
Case 1: X-k >= 0, then we have X-k, Y as the new X and Y, and our S[k] becomes S[k-1], both X+Y and S[k] decrease by exactly k, so our claim X + Y <= S[k] and agree with parity holds.
Case 2: X-k < 0, in this case we need to show k - X + Y <= S[k-1] and they agree in parity. The parity part is easy, as X + Y and X - Y have same parity with S[k], which is S[k-1] + k, as is S[k-1] - k. Now we show the inequality. We have two subcases.
Subcase 1: S[k-1] < X + Y <= S[k] and X + Y agree in parity with S[k]. Then we need to show k - X + Y <= S[k-1], which is k + Y <= S[k-1] + X. Since X >= Y, for any k >= 3 we know this inequality is true. If k = 2, then we know X + Y <= S[2] = 1+2, then X and Y is either 1,1 or 1,2, both are easy to deal with. Similarly we can deal with k = 1.
Subcase 2: S[k-2] < X + Y <= S[k-1] and X + Y disagree in parity with S[k-1], then our move is (k - X, Y) and we need k - X + Y <= S[k-1]. This is almost the same as Subcase 1.
Whew! We have actually proved that the strategy actually works.
Now the take-home message, in graph theory book, there is an acronym:
The Obvious Necessary Condition Is Also Sufficient, that is TONCIAS.
No comments:
Post a Comment