Some time ago, I was part of the scientific committee at infO(1)Cup. While discussing problems with other members of the committee I proposed the following problem:

You have to play a game against the interactor on a $$$N$$$ by $$$M$$$ matrix. Initially all cells are unclaimed. You and the interactor, alternatively, take turns claiming a non-empty set of unclaimed cells. The set of cells chosen in a turn has to be able to fit in a $$$K$$$ by $$$K$$$ bounding box without being rotated and has to be connected. (There exists a path between any two cells in the set passing only through cells in the set, we define a path as a sequence of cells such that any two consecutive cells have a common side). You can choose whether to play first or second.

Before I discuss the solution to the above problem, I first wish to show you a similar puzzle known in the folklore as "The round table coin game" or as "The faustian round table coin game" . The puzzle goes as follows:

The Devil proposes to play a game against you. If you win, he will give you everything that you desire, otherwise he will take your soul. The game is played on an empty round table. You take turns placing identical coins on the table. In a turn you have to place exactly one coin on the table such that it does not overlap with another one. Note that once a coin is placed on the table you can't move it. The player who cannot make a move loses. You can choose whether to play first or second.

The winning strategy is to choose to play first and place a coin in the center of the table. Then, you can always mirror the opponents move as follows:

As seen in the animation above we will never run out of moves to do, since our opponent has to do them first. Now, let's return to our original task. We can try extending this reasoning by considering the following 2 cases:

• If $$$K$$$ is $$$1$$$, there is not much that we can do since all players can only claim exactly one cell per turn. We can decide whether to go first or second by looking at the total number of moves $$$N * M$$$. If it is odd, we should play first. Otherwise, we should play second.

• Otherwise, we could try transforming our coin strategy to adapt to this setting. We start by placing a $$$1$$$ by $$$1$$$ square in the middle of the board and then mirror our opponents moves. Unfortunately, this strategy has two major flaws.

First, let's consider a board with even lengths. Where exactly is the center and how can we place a $$$1$$$ by $$$1$$$ square there? The answer is that the center is in this case not a $$$1$$$ by $$$1$$$ square but a $$$2$$$ by $$$2$$$ square, so we have to adapt our strategy to place $$$2$$$ by $$$2$$$ squares. What about boards with even length and odd width or vice versa? For them, the center is not a square, but actually a $$$1$$$ by $$$2$$$ or $$$2$$$ by $$$1$$$ rectangle. Naturally, we should adapt our strategy to consider such cases and if necessary place rectangles instead of squares in the middle.

Secondly, if in the first turn we play a piece that is too small, our opponent could place a really long piece that wraps around our middle piece and intersects with its own mirror image. This flaw can be easily corrected by making the middle piece as big as possible while still respecting the bounding box condition and its symmetry.

After correcting these $$$2$$$ flaws, we finally have a working strategy. Check out the following animation for an example:

How do we actually write the interactor?

The strategy of the contestant should be clear now, but what about the strategy of the interactor? How can we guarantee that a wrong solution will fail? If the contestant chooses to play as the second player, we can easily punish them by making the grader play perfectly as the first. If the first player places a middle piece that is too small, we can simply wrap around it, thus creating a bigger middle piece. However, what if our opponent decides to not even place his first piece in the middle? Or what if our opponent places the first piece correctly, but fails to mirror our moves. How can we punish such incorrect solutions?

After careful consideration, we reached the conclusion that the only way to punish the contestant for having a bad strategy was to do random moves until the end. We claimed that if the contestant had a bad strategy, then by doing those random moves we could create enough chaos on the board to derail his algorithm and balance our chances of winning. Those random moves would be mostly spread around the sensitive spots such as the center or the mirror images of already placed pieces. This is a decent method since the interactor only has to win once to deem the solution incorrect, while the contestant has to win all the time.

Another idea that was proposed during the meeting was that if we restricted to the shape of the sets of cells it would be easier to come up with a strategy for the interactor to punish those wrong moves. The discussed shapes included but were not limited to: only squares, only rectangle, only tetris pieces. We even considered introducing non-connected shapes, however none of these ideas materialized into something useful.

In the end, the question boiled down to the 2 following points:

• Is it acceptable to propose such an interactive problem if you can't guarantee that the judge will play optimally well? And if it is acceptable, where do we draw the line? What is the acceptable probability of an incorrect strategy passing?

• Should we even invest that much time into preparing this problem? Or as a very wise man once said: "Is it even worth to propose a problem if the grader is harder to write than the actual solution?".

Ultimately, the problem didn't make the cut because of all of these shortcomings. However, that is exactly why it is worth sharing here.

Open questions

• Do we have a name for this type of game theory problems, where there exists an easily provable winning strategy for the first move, yet it is almost impossible to determine for an arbitrary state if it is winning?
• Is there any modification of the problem, for which it is possible to find a strategy for the interactor?
• Is there any strategy that the first player can adopt that will win against a random interactor, yet will lose against a hypothetical perfect player?

Closing remarks

I wish to thank awoo, Ari, and -is-this-fft- for helping me with making the animation work on codeforces. For any future persons that wish to upload animations, use the .gif format and upload it with the .png extension (Just change the extension, don't change the format to .png). I also wish to thank my brother for doing the animations.

In any case, I hope you liked this blog and I hope to hear your opinion regarding such problems.