GCJ round 1C

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.

GCJ round 1B

A. Notice that you always take a prefix after sorting.

B. Draw N= 1 to 7, then you see a pattern. The answer is always 1/2^k

C. DP, although many topcoders use trie.

dp[n][p] is min cost to split S[1..n] into words such that the last mismatch occurs at n-p. So p = 1, 2, 3, 4, 5 (for 5 and above, they are the same)

dp[0][5] = 0
for i = 1 to n
for w = 0 to dict.size()-1
  cut dict[w] from the end of S[0..i-1]
  for the transition to be valid, the word dict[w] itself must have mismatch dist >= 5 as required, and we need previous dp[i-len][prev] be dist=5 or more away

One important implementation detail: Since there are 5*10^5 words and n is 4000, using vector for dict is 10 times slower than using char[][], which means a difference of 15min vs 1.5 min

TC SRM 578 div1

p250, very similar to a previous tc 250 problem. The first step is to identify components, that is, nodes with L1 distance <= dist with 'v'. Then we have the count of each component. Let odd and even be the number of components with odd and even number of nodes, to get an overall even count, we must choose an even number of odd components and any number of even components.

An analytical solution is 2^even * (2^odd / 2), because binomial sum is even, and (n choose 0) + (n choose 2) + ... + (n choose 2k) = (n choose 1) + (n choose 3) + (n choose 5) + ... + (n choose 2k+1)

A dp approach is to use dp[n][0] and dp[n][1] denote the number of sets with component 1 to n, and [0] if sum is even and [1] if sum is odd. Then the empty set is dp[0][0] = 1, and dp[0][1] = 0
The recurrence is
let components be numbered 1, 2, ..., n
if (cnt[i] is odd) dp[i][0] = (dp[i-1][0] + dp[i-1][1])
                         dp[i][1] = (dp[i-1][0] + dp[i-1][1])
because we can use the odd component to make odd become even, and not use it leaves the sum odd.
if (cnt[i] is even) then dp[i][0] = dp[i-1][0] * 2, since use cnt[i] or not leaves even as even, and dp[i][1] = dp[i-1][1] * 2 for the same reason.

Some contestant even implemented choose[n][r] and do the actual summation.

One catch, we need to return dp[n][0] - 1. And since we are doing mod 10^9+7, we need to be a bit careful. If dp[n][0] = 0 MOD 10^9+7, then we would return -1 which is bad. Fortunately for me and many contestants with ignorance, since the real answer is 2^k, the mod will never return 0. So we are saved. What a relieve.

p500, I got almost everything, but still could not finish. The dp solution is
dp[l][r] counts number of ways to place wolves with last two at l and r.

dp[0][0] indicates no wolves.
dp[0][l] indicates only one wolf at location[l], which is 1-based.
dp[l][r] = sum of p = 0 to l-1, dp[p][l] such that [p,r] is not contained in any of the L[i], R[i] intervals. Notice that we need to shift the L[i], R[i] value to the right by 1 to make it 1-based.