PROBLEM LINK:
Author: Yuri Shilyaev
Tester: Hasan Jaddouh
Editorialist: Yury Shilyaev
DIFFICULTY:
Medium
PREREQUISITES:
Nothing.
PROBLEM:
Given a grid 2 \cdot N and two players in positions (x_1, y_1) and (x_2, y_2). Each player can move to adjanced by side cell on his turn, but he can’t visit cells visited by the other player. Predict the result of the game.
QUICK EXPLANATION:
Consider all the cases.
EXPLANATION:
It is obvious, that for some time players will move closer to each other and then some different scenarious could happen. After that they would change their x coordinate and move back, but this happens not in each game.
Let’s solve different problems for cases when x_1=x_2 and x_1 \neq x_2. Also let’s make first player to the left of the second, simply reversing the grid.
Solution for x_1 = x_2:
Let the middle between them be pos = \lfloor \frac{y_1 + y_2}{2} \rfloor. Now just compare 2 \cdot pos with 2 \cdot (N  pos). If it is less than 2 \cdot (N  pos), first player wins, if equal the game will end with draw. Second player wins otherwise.
Solution for x_1 \neq x_2:

If y1=y2, the result is draw.

If they stay on one diagonal, i.e y_2  y_1 = 1, than first player can win by moving by x coordinate, or can make a draw moving to the right by y coordinate. Second player can’t win in this case. So let’s compare 2 \cdot y_1 with 2 \cdot (N  y_1).

In the last case, let’s move them to the middle of the distance between them. Let D = y_2  y_1  2. Now, let’s move the first player to the right on \lceil \frac{D}{2} \rceil. And the second to the left on \lfloor \frac{D}{2} \rfloor. Now, the first player can win if his potential number of visited cells is already enough to win. So the first player wins if 2 \cdot y_1 > 2 \cdot (N  y_1). The same for the second player, he could change his plan to move to the middle and change x coordinate on his last chance. Let’s compare if 2 \cdot (y_1 + 1) < 2 \cdot (N  y_1  1). Otherwise, he is ready for draw as the first player.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.