PROBLEM LINK:
Author: Alexey Zayakin
Testers: Hasan Jaddouh
Editorialist: Alexey Zayakin
DIFFICULTY:
Medium-Hard
PREREQUISITES:
DP, math, fractals
PROBLEM:
Two player game is played on a strip consisting of n cells. There is a pawn that is initially located at some cell. The players make moves alternately. During the k-th move the player has to move the pawn from cell p to either (p - k) or (p + k). The player who is not able to make a move loses the game. Both players play optimally.
Given m starting positions of the pawn, for each of them determine which player will win the game.
QUICK EXPLANATION:
Implement a quadratic DP on states (current move, pawn position) and visualize it for some relatively big values of n. Notice that it looks beautiful like a fractal. Find some property of this “fractal” that would allow us to speed up the quadratic DP.
EXPLANATION:
We will start with an \mathcal{O}(n^2) dynamic programming solution. For all the possible states of the game, i.e. pairs (move number, position of the pawn), we will determine whether it is a losing or a winning position. The state (i, p) is a losing state if and only if both (i + 1, p - i) and (i + 1, p + i) are winning positions (assuming all positions with p < 0 or p > n are winning).
Now we will visualize this DP table to better understand how the things work. At the picture below the x-axis is the position of the pawn, y-axis is the number of current move (the first move is at the bottom and the n-th move is at the top), winning positions are colored black and losing ― white.
Looks… like a fractal, right? But if you look closer… you notice it just looks like a fractal. So let’s still try to get some useful properties given the graph just looks like a fractal. The graph has two black “rays” coming out of top corners and going to the middle of the bottom edge. These two “rays” both split into two after passing a little bit more than a half of the graph, each of the two parts later splits into two as well, and so on… The useful property of this structure is that the upper half of the graph consists just of some black prefix, white segment in the middle and a black suffix. Lower there is a big part where every row has just 5 segments, and so on… So here we actually have a property that can be used to speed up our \mathcal{O}(n^2) DP: instead of explicitly computing every row, we will store it as a set of segments of the same color. Given that our DP has an extremely simple transitions, it is possible to compute the “segment representation” of the next row using only the “segment representation” of the previous row in $\mathcal{O}(segment count)$. Now you can just implement this optimization and run it with n = 10^6 to make sure it works fast.
Time Complexity:
\mathcal{O}(n \log{n}) per test case ― empirical estimation based on approximately 15 \cdot 10^6 segments in total for n = 10^6.
Bonus:
Can you prove something here?