Editorial for CPC '19 Contest 1 P5 - A Puzzlingly Puzzling Puzzle Problem 😎

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: wleung_bvg

Solution Sketch

For all subtasks, we can represent the game as a graph where each board configuration is a vertex. An N \times M board will have \frac{(N \cdot M)!}{2} valid configurations. There are a number of ways to do this, such as indexing permutations, bitmask techniques, or strings.

Subtask 1

For the first subtask, there are only 12 possible board configuration. We can randomly make 12 moves for each player and track of the minimum moves for each player to reach the target board. If we do this enough times, we will have the correct answer with high probability.

Time Complexity: depends on implementation

Subtask 2

For the second subtask, we can perform a breadth first search from each player's starting board, for each game, and select the player with the least number of moves.

Time Complexity: \mathcal{O}((N \cdot M)! \cdot K \cdot Q)

Subtask 3

For the third subtask, a key observation is that the starting board configuration does not change for each player. We can perform a single breadth first search from each player's starting board, creating a distance array. To determine the answer, we will check the distance array for each player and select the minimum.

Time Complexity: \mathcal{O}(K \cdot ((N \cdot M)! + Q \cdot N \cdot M))

Subtask 4

For the fourth subtask, we can perform a multi-source breadth first search from each of the players instead of a single-source breath first search. We will keep track of the distance and player for each vertex. The answer can then be determined in \mathcal{O}(1) time for each game. This solution should work for subtasks 1 to 3 as well.

Time Complexity: \mathcal{O}((N \cdot M)! + (K + Q) \cdot N \cdot M)

Subtask 5

For the last subtask, there is only a single game, but a very large graph. A few key observations are that the graph is fairly random and that since the starting and target boards are generated uniformly at random, we do not have to worry about the worst cases. Thus, we can perform a tridirectional breadth first search from the two starting board and ending board configurations. When a path starting from the target board intersects any of paths from the player's boards, we know we have found the minimum answer (in theory, we will have to keep checking all vertices at that depth to find the minimum player index, but with random data, it is very unlikely that the two players will have the same number of moves). By the birthday paradox, this will result in visiting approximately \sqrt{(N \cdot M)!} vertices (in practice, it is slightly more that that). Note that this solution will not pass subtask 4.

Time Complexity: \mathcal{O}((K + Q) \cdot \sqrt{(N \cdot M)!})