PROBLEM LINK:
Author: Kamil Dębowski
Tester: Sergey Kulik
Editorialist: Pawel Kacprzak
DIFFICULTY:
Hard
PREREQUISITES:
Creativity
PROBLEM:
The task is to win a modified version of the game known as Cat Trap, Black Cat, Chat Noir or Circle The Cat. The game is played on a regular hexagon grid of side N=20. The goal of the game is to trap the cat in at most M turns. The cat starts the game in the central cell of the grid. A single turn consists of two moves: first, the cat moves to any not yet blocked cell X adjacent to its current cell, for the distance from X to any border cell is minimum among such cells. The distance means the minimum number of moves the can have, using only not yet blocked cells, to take to reach any border cell. After that, you have to block exactly one cell, which is not yet blocked and the cat is not in that cell. You win the game if at any point the cat is not able to reach any border cell. You lose when the cat escapes the grid. The task is to win the game in at most M turns. Notice that the problem is interactive, which means that you don’t know cat’s moves beforehand, you just know the rules the cat uses to perform its moves.
QUICK EXPLANATION:
Find out how to force the cat to move towards the center of one side of the grid, and while it is moving there, build a trap waiting for him exactly in that place. When the cat walks into the trap, close it from the other side.
EXPLANATION:
Subtask 1
In the first subtask, we have to trap the cat in at most 500 turns. Notice that in 500 turns is enough to mark all border cells if only the cat doesn’t escape the grid during this process. Thus one possible solution is the following:
-
We block all 6 corners of the grid, and exactly one (doesn’t matter which) border cell adjacent to each of the corners. This takes exactly 12 moves. Cells blocked here will be very helpful later.
-
We allow the cat to move towards the border until it needs exactly 2 more moves to reach a border cell. Since we are not allowed to skip our moves, we can, for example, block some cells on the border
-
Now, the cat needs exactly 2 moves to reach a border cell, the situation is shown below:
-
We block a cell just “underneath” the cat, like shown below:
-
Now, when the cat is about to move one cell closer to the border, and has two choices, without loss of generality, let’s assume that it went to the following cell:
-
Now, since in step 4 we blocked the cell “underneath” the cat, only one border cell is reachable from current cat’s position (here, we take advantage of the fact that we blocked one border cell adjacent to each corner at the beginning, otherwise, near the corners, there will be more than one border cell reachable from current cat’s position). Thus, we block that only reachable border cell as follows:
-
Now, the cat is forced to move either left or right alongside the border, and when it chooses one of these directions, it will follow it, so we are going to block all border cells adjacent to cat’s current cell as long as there are not yet blocked border cells. Here, it’s very handy that we blocked all the corner cells at the beginning, since otherwise when the cat is adjacent to a corner cell, then it is possible that two border cells will be adjacent to its current cell, so the cat will be able to escape.
-
Finally, all border cells are blocked, and the cat is trapped
It’s also possible that the cat will move straight to one of the corners, but this situation is even better for us - because two cells there are already blocked. You can check yourself that we won’t get a situation where the cat is adjacent to two empty border cells.
This approach uses around 6 \cdot N turns because we only block border cells, which is fine here because in this subtask we have to trap the cat in 500 turns.
Subtask 2
In the second subtask, we have to win in at most 20 turns, so the task is significantly harder. Notice that it implies that we are only allowed to block 20 cells, and after that, the cat has to be trapped. It follows, that the cat must be trapped in some small part of the grid. Thus, the idea is to force the cat to walk towards the center of one of the sides of the grid and while it is walking there, prepare a trap in that place.
First of all, we want to avoid the case when the cat is going straight to one of the corners, so just after its first move, we block adjacent cell to his current cell which lies on the path from that cell to the closest corner, so the cat is forced to make a turn. After that turn, we know towards which side the cat is walking, moving one step closer to the border in a single move, so we are going to prepare a trap there. Specifically, we are going to prepare the trap just in the center of the side towards the cat is moving. This is crucial because only there we are always capable of forcing the cat to move into the trap. When the trap is ready, we have to force the cat to go there, so we cut off all other moves leaving the cat without a choice - remember that the cat always picks the shortest path to the border, so it is stupid enough to fall into the trap. Whenever the cat gets closer to the border, it has two choices for the next move, so we can force him wherever we want by blocking one of these possibilities. As soon as the cat walks into the trap we close the exit and the cat is trapped.
In order to see that method in action, run the visualizer attached to the problem statement with the following sequence of moves:
cat(1,-1)
block(2,-2)
cat(2,-1)
block(19,-10)
cat(3,-2)
block(18,-10)
cat(4,-3)
block(17,-9)
cat(5,-4)
block(19,-8)
cat(6,-5)
block(18,-7)
cat(7,-6)
block(17,-7)
cat(8,-7)
block(16,-7)
cat(9,-8)
block(10,-9)
cat(10,-8)
block(11,-9)
cat(11,-8)
block(12,-9)
cat(12,-8)
block(13,-9)
cat(13,-8)
block(14,-9)
cat(14,-8)
block(15,-9)
cat(15,-8)
block(16,-9)
cat(16,-8)
block(0,0) # skipping one move
cat(17,-8)
block(16,-8)
cat(18,-8)
block(19,-9)
In the above sequence of moves, cat moves in such a way that it doesn’t want to go into the trap - it goes left and down as far as it can, so we are forced to cut off his intended way many times to for it to the trap. The trap we prepare is pretty small - it uses 6-7 blocked cells and remaining moves are used to block other cells in order to force the cat to walk to the trap. The limit of moves is pretty tight, so this is one of the major difficulties in this subtask.
For implementation details, please refer to setters solution. It uses the exact method described here. One very useful implementation tip is that since the cat can move to any of the six sides of the grid, we can implement grid rotation to avoid handling all cases these cases separately. It is always a good idea to have a short solution because it reduces the cost of fixing possible bugs or extending the solution.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Tester’s solution can be found here.
