Editorial for Yet Another Contest 1 P3 - Fluke

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Josh

This game is highly symmetrical, which motivates the following strategy known as 'strategy stealing'.

We can instruct Josh to go first. Whenever Josh marks a cell, we can simply mark the same cell but rotated 180^{\circ} about the center of the board. Because of rotational symmetry, and the fact that a cell is never adjacent to the cell which is rotated 180^{\circ} about the center of the board from it, it is easy to see that whenever Josh makes a valid move, then our move will also be valid. Thus, we can never run out of moves first, so we will always win.

The only situation where this does not work is if N is odd and Josh marks the center cell, since the same cell can't be marked twice. For odd N, we can choose to go first and mark the center cell, and then perform the strategy stealing as described before.


There are no comments at the moment.