Editorial for DMOPC '22 Contest 3 P1 - Holiday Colouring
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Hint 1
What is the optimal first move for Red? What about for Green?
Hint 2
What happens if the total number of squares in the grid is even? What if it isn't?
Subtask 1
In this subtask, the game is played on a one-dimensional grid. It is easy to see that it is always optimal for Red to make their first move closest to the center of the grid. Since if they were to go further to the left or right, Green can easily take the square next to Red's and force them into the smaller portion of the grid. Subsequently, it can be seen that Green's optimal first move is to take the square adjacent to Red's that gives them ownership of the larger portion of the grid.
If is odd, Red is able to colour in the square directly in the middle of the grid, leaving them with one more square than Green in the end. Otherwise, Red and Green each colour the two squares closest to the middle on their first move giving them the same number of squares.
Subtask 2
The central ideas from subtask 1 still carry forward. The key intuition required is that the optimal strategy for both players is to first create a "wall" straight across that prevents the other player from ever colouring into their region of the grid. It is still optimal for Red to make their first move as close to the center as possible, as it leaves Green with the minimum largest portion of the grid they can claim ownership of.
If the total number of squares is odd, then Red is able to make their first move in the direct center of the grid. Since Green can't take a square as close to the center as Red, their optimal first move is to take an adjacent square to Red favouring the side of the smaller dimension of the grid. This way, Red ends up with more squares than Green by the end of the game.
Otherwise if the total number of squares is even, Red cannot take the square directly in the middle of the grid. Consequently, Green can take a square just as close to the middle of the grid as Red on their first move. Both players will then end with the same number of squares as Green can just mirror Red's moves.
Comments