I went through the problem and editorial, and about the editorial’s x_1=x_2 case, I think it’s just a typo, and the editorialist meant to write the opposite of who wins. But the editorial’s approach seemed convoluted, so I came up with my own which at least to me seems more intuitive. Here goes.
The important thing in this game is that to win you must capture both the vertical cells at the center of the grid so that the opponent is stuck on a side with lesser number of cells. One can win with a greater difference also but this is the minimum requirement for winning. Odd and even N should be considered separately
ODD: 1 2 3 4 5 +---+---+---+---+---+ | | | X | | | +---+---+---+---+---+ | | | X | | | +---+---+---+---+---+ EVEN: 1 2 3 4 5 6 +---+---+---+---+---+---+ | | | X | Y | | | +---+---+---+---+---+---+ | | | X | Y | | | +---+---+---+---+---+---+
In the odd case if you capture both the cells marked X you win. No matter on which side the opponent lies, he cannot get more than half the cells.
In the even case you must capture the X cells if the opponent is to the left of the center, and the Y cells when the opponent is to the right.
If no player can do either of these, it’s a draw. This occurs when a player ends up directly above/below the other. One player can always mimic the other’s motion and prevent the other from moving vertically. So it will always end in a draw because no one will let the other win.
Let w_1, w_2 be the center coordinates that player 1 and player 2 respectively must capture to win.
If N is odd, then w_1 = w_2 = \frac{N + 1}{2}
If N is even, then w_1 must be one of the two centers that is closer to player 2, and vice versa. That’s because to win a player must trap the other on a side with lesser cells as already discussed. So w_1, w_2 will each end up being \frac{N}{2} or \frac{N}{2}+1.
Let’s consider what each player needs to do to win. If both players cannot win, we decide it’s a draw. The \DeclareMathOperator{\dist}{dist} \dist(a, b) function used below is just the distance along the row dimension, which is just \DeclareMathOperator{\abs}{abs} \abs(a - b).
Case 1: x_1=x_2
Both players are on the same row. For player 1 to win, he must reach w_1 and then move vertically. But for that he must reach w_1 before player 2 can reach w_1. Similarly player 2 wants to reach w_2 before player 1.
If \dist(w_1, y_1) \le \dist(w_1, y_2), player 1 wins.
If \dist(w_2, y_2) < \dist(w_2, y_1), player 2 wins.
You can easily verify this. Note that for player 1 it is \le but for player 2 it is <. That’s because player 1 has the advantage of starting first.
Case 2: x_1 \ne x_2
As before, for player 1 to win, he must reach w_1 and then move vertically. But now if he reaches w_1, but in the next step player 2 also reaches w_1 in the vertically adjacent cell, he cannot win. So each player must reach his target 1 step in advance of his opponent as compared to before.
If \dist(w_1, y_1) < \dist(w_1, y_2), player 1 wins.
If \dist(w_2, y_2) + 1 < \dist(w_2, y_1), player 2 wins.
That’s it. Here is my solution, and a more concise solution.
Let me know if some part is not clear!
