A moonlit week

The Universal Cup Stage 3: Polar was the first event of this week (problems, results, top 5 on the left, still not updated cup standings). In all three stages of this season the first two places went to the same two teams, and in odd-numbered rounds team USA1 comes out on top, if only by less than one wrong submission this time. Congratulations to both season leaders!

AtCoder Grand Contest 074 wrapped up the week just a few hours ago (problems, results, top 5 on the left, analysis, race standings). Just one minute before the end of the round it seemed like Nachia executed a perfect strategy, solving C and B first, then deciding to go for D instead of A since it was clear at that point that A+B+C would not be enough to win the round, and getting D with 15 minutes remaining to go on top with a unique set of problems solved.

However, ksun48 made not one but two submissions on C during the last minute, one of which turned out to be correct. How does one submit, find and fix a bug, and submit again, all within the last minute of the round? Well done, Kevin!

I have spent most of the round on the same problem C. It was clear from the constraints that one should dig in the direction of going from ~n to ~2n using 3 additional bits, and in the end this is exactly how my solution works, but somehow this digging took me more than 2 hours, mostly on paper.

I think it took me so long since I have made a reduction that made the solution more difficult, and did not consider rolling it back (instead, I have persevered and solved the more difficult reduced problem): I was looking for a way to configure the 3 additional bits in such a way that we can go from a LIS of length k for n/2 either to lengths k, 2k and 2k+1 or to lengths k, 2k+1 and 2k+2, depending on the parity of n.

The reason I wanted three options instead of the usual two was that the 2k+x options would not cover small values of LIS, so I thought it would make sense to make sure we also can keep k unchanged; however, on further thought after the round it became clear that the small values not covered are only 1 and possibly 2; and it is always very easy to obtain a LIS of 1 by just making everything equal, and also not hard to obtain a LIS of 2 by making almost everything equal.

Despite a few spoilers above, I hope you can still enjoy solving that problem if you have not already: you are given a single integer n<=2¹⁰, and you need to produce a sequence p_i of n integers such that 0<=p_i<2³⁰, such that for every value of k between 1 and n there exists a number a such that the longest strictly increasing subsequence of the sequence q_i=p_i&a has length k. Here & denotes bitwise and, in other words we consider a certain subset of bits of p_i, the same subset for all i.

In my previous summary, I have mentioned a Hacker Cup problem: you are given a string of 0s and 1s of length <=600000. Two players are playing a game, making moves in turns. On each move of the first player, they erase any prefix of the string that ends with a 0. On each move of the second player, they erase any suffix of the string that starts with a 1. The player who cannot make a move loses. Who will win if both play optimally?

First of all, the first player always takes a 0, and the second player always takes a 1. Naively, one might think that we should just count if there are more 0s or 1s in the string. However, it is very easy to come up with a counter-example: string 110 has more 1s than 0s, but the first player still wins because they can erase it in one go. The 1s in the beginning of the string don't really matter, as long as there is at least one 0.

However, since having more 0s still seems useful for the first player, a somewhat natural idea is to check: what if the first player tries to make a move that maximizes the balance of the remaining string — the difference between the number of 0s and 1s? Here a counterexample is also not that hard: from the string 0100 we can go to two different strings 100 and 0 with the maximum balance of 1, however if we go to 100 then the second player can take the remaining string and win, while if we go to 0, the second player loses.

Guided by this counterexample, what if we always break ties by choosing the shortest possible string with the maximum balance? After spending some time finding yet another counterexample to this approach and failing, I've decided to look for a proof that it works instead.

Suppose we have used that strategy for the first move, and the remaining string has some non-negative balance (it feels intuitive that the balance has to be non-negative for us to win). What happens to the balance after the move of the second player? After some experimentation, we can notice that it always becomes strictly positive. And indeed, it is not hard to prove by contradiction: suppose it is non-positive after the move of the second player. Suppose the string remaining after the move of the first player is s, and the second player has removed then removed the suffix u, and what remained is t, so s=tu. 

The balance of s is non-negative, the balance of t is non-positive, and u starts with a 1. Since the balance of u is the balance of s minus the balance of t, is is also non-negative, so it must have a 0. Consider its first 0, which splits the string u as u=v0w, where v consists only of 1s. But then the first player could have additionally erased the string tv0 in their first move. Since the balance of t is non-positive, and the balance of v0 is non-positive, the balance of tv0 is non-positive, which means that the balance of w is the same or higher than the balance of s=tv0w. But this contradicts the choice of s.

So, after the move of the second player the balance will become strictly positive. But then we can apply the same approach (make the move that maximizes the balance of the remaining string, breaking ties to shorter remaining strings), and the balance of the remaining string will be non-negative (since at least if we take the first 0 it is non-negative, and we maximize it), so we can repeat this until we win.

We can already submit our solution at this point, but formally speaking we also need to prove that if the first player cannot make a move that leaves a string with a non-negative balance, then the second player wins. And indeed, we can apply the same argument as above: if we have left a string with a strictly negative balance, then from the point of view of the second player it has a strictly positive balance, and they can apply exactly the same strategy as above to win.

This solution is longer than the one in the editorial, but it is how I solved the problem during the round, and I hope it shows how to arrive at a solution without having to pull an idea out of thin air, for example an idea to consider balanced parentheses sequences as the editorial does.

Thanks for reading, and check back next week!