F - Rotation Puzzle Editorial by spheniscine


Note that there are only \(4\) possible operations, and since we are limited to \(20\) moves, there are up to \(4^{20}\) possible combinations of operations, but that is still too large for naive breadth-first search.

Instead, we can note that each operation is a permutation (despite the presentation of this problem, it’s easiest to think of these permutations as flat arrays, treating them as grids only for the “rotate” operation), and that permutations form a group, that is:

  • Permutations of the same size are composable (one can be applied after another to result in another permutation), and this operation is associative. Let’s denote the composition operation by \((A * B)(i) = B(A(i))\)
  • There is an identity element, the identity permutation \(I(i) = i\), where \(A * I = I * A = A\).
  • Each permutation has an inverse, where \(A'(A(i)) = i\), therefore \(A * A' = A' * A = I\).

We can thus use a “meet-in-the-middle” technique: use BFS to find all possible permutations reachable from the identity permutation in \(10\) or fewer moves. We store this in a hashmap that maps a permutation to the minimum number of moves required to reach it. Now we iterate through all these permutations; for each permutation \(P\), the permutation required to “complete” it is \(X\) in the equation \(S * P * X = I\), therefore \(X = (S * P)'\). Thus, find \(X\) in the hashmap, and if it exists, update the answer by the sum of the costs of \(P\) and \(X\).

posted:
last update: