A twenty billion week

TopCoder SRM 760 was the main event of the Jun 10 - Jun 16 week, and even it did not have so many participants since it took place at a Europe-unfriendly time (problems, results, top 5 on the left). fjzzq2002 had a healthy lead after the coding phase, and had only increased it through challenges. Congratulations on a convincing victory!

In my previous summary, I have mentioned a Google Code Jam problem: you are playing a game that starts with 10¹² coins arranged in a row. In one turn, each player must pick any 10¹⁰ consecutive coins and remove them. The remaining coins are not shifted, therefore the coins that were on both sides of the removed segment do not become consecutive. The player who can't make a move loses. The first player always picks a valid move uniformly at random, and you are playing for the second player. Your goal is to win at least 499 games out of 500.

The key idea is the following: a block of exactly 2*10¹⁰ consecutive coins is extremely useful when playing against a random player. If a random player makes a move inside this block, it will almost certainly be not at the boundary, and thus no further moves will be possible there, so unless we make a move at the boundary ourselves, this block behaves exactly like a block of size 2*10¹⁰-1, or a block of size 10¹⁰. However, if it's our turn and we need to do so, we can move at the boundary of this block and leave a block of size 10¹⁰ behind which still allows one more move. In other words, we can skip a move if we have a block of size exactly 2*10¹⁰ available.

Skipping a move turns a losing position for you into a losing position for other player, which means we can win with certainty if we know if the current position is winning or losing :) However, we don't know that in the general case. Instead of trying to determine it, let's just do the following: if there is a block of size >=3*10¹⁰, we can make a move that creates a block of size exactly 2*10¹⁰, let's do so. Otherwise if there's still a block of size at least 2*10¹⁰+1, let's make any move inside any such block.

At some point we will end up in a situation where all remaining blocks are of size between 10¹⁰ and 2*10¹⁰. The random player makes exactly one move in any such block, so it's very easy to determine if a position is winning or losing: losing positions have an even number of such blocks. If we are in a losing position, and there's still at least one block of size 2*10¹⁰ remaining, we can use the above trick to skip a turn and give the other player a losing position.

And since we always create such blocks while there are still large blocks remaining, and the random player can destroy them but does not always do so as it's more likely to move inside a bigger remaining block, the probability that we will have at least one block of size 2*10¹⁰ remaining when we reach that "simple" state with no bigger blocks is essentially 1.

Thanks for reading, and check back for more!