P2730 [IOI 1996 / USACO3.2] Magic Squares

After inventing the Rubik’s Cube, Mr. Rubik created its 2D version, called the magic board. Each cell on the magic board has a color. These $8$ colors are represented by the first $8$ positive integers. A board state can be represented by a sequence of colors: starting from the top-left corner of the board, take the integers in clockwise order to form a color sequence.

This is a magic board with $8$ squares of equal size: | $1$ | $2$ | $3$ | $4$ | |:-:|:-:|:-:|:-:| | $8$ | $7$ | $6$ | $5$ | For the board state shown above, we use the sequence $\{1,2,3,4,5,6,7,8\}$ to represent it. This is the initial state. There are three basic operations, denoted by the uppercase letters $\text A$, $\text B$, and $\text C$ (you can change the board state using these operations). Below is a demonstration of applying them to the initial state: $\text A$: Swap the top and bottom rows. | $8$ | $7$ | $6$ | $5$ | |:-:|:-:|:-:|:-:| | $1$ | $2$ | $3$ | $4$ | $\text B$: Move the rightmost column to the leftmost position. | $4$ | $1$ | $2$ | $3$ | |:-:|:-:|:-:|:-:| | $5$ | $8$ | $7$ | $6$ | $\text C$: Rotate the four central cells clockwise. | $1$ | $7$ | $2$ | $4$ | |:-:|:-:|:-:|:-:| | $8$ | $6$ | $3$ | $5$ | At any state during the transformation, all three basic operations can be applied. Write a program to compute the shortest sequence of basic operations that transforms the initial state into the target state.

A single line containing $8$ integers $a_1, a_2, \dots, a_8$ with $1 \leq a_1, a_2, \dots, a_8 \leq 8$, separated by spaces, representing the target state.

The first line contains an integer, the length of the shortest operation sequence. Starting from the second line, output the shortest sequence of operations as a string, wrapping every $60$ characters per line. If there are multiple solutions, output the lexicographically smallest one.

Translation source: NOCOW. Translated by ChatGPT 5