Contest Duration: - (local time) (210 minutes) Back to Home

## C - Block Game Editorial by rng58_admin

During the game, let’s keep the following two values:

• $$L$$, the number of consecutive empty cells to the left of Snuke (before the nearest block to that direction).
• $$R$$, the number of consecutive empty cells to the right of Snuke (before the nearest block to that direction).

Only these two values matter because Snuke can never reach beyond these $$L + R + 1$$ cells. Also, notice that if $$a \leq a'$$ abd $$b \leq b'$$, the state $$(a', b')$$ is not worse than $$(a, b)$$ for Snuke (to give a formal proof, use an induction on the number of remaining steps).

Thus, we can simulate the game as follows:

• We start with the state $$(\infty, \infty)$$.
• In Snuke’s turn, he may change the state $$(L, R)$$ to $$(L+1, R-1)$$ or $$(L-1, R+1)$$ (or may not).
• In your turn, you change the state $$(L, R)$$ to $$(0, \min \{ L, R \})$$.

For a given turn string, how to check the winner? For example, suppose that the turn string is $$S...SBS...SBS...SBS...SBS...SBS...S$$, and run lengths of $$S$$ are $$a, b, c, d, e, f$$ from left to right.

• After the first $$B$$, the state is $$(0, \infty)$$.
• Then Snuke changes the state to $$(b, \infty)$$.
• After the second $$B$$, the state is $$(0, b)$$.
• Then, for Snuke, it is optimal to change the state to $$(x, b-x)$$, where $$x = \min \{ [b/2], c \}$$.

By repeating this kind of observations, we get that Snuke wins iff $$\min \{ [b/8], [c/4], [d/2], e \} \geq 1$$, or equivalently, $$b \geq 8, c \geq 4, d \geq 2, e \geq 1$$.

Now we can get an $$O(N log N)$$ DP solution to solve the original problem.

posted:
last update: