## Ex - General General Editorial by en_translator

Let us call the operation with \(i=x\) **move \(x\)**.

### Narrowing down the moves

We only have to consider the following ways:

- Using at most two kinds of moves.
- Using at most three kinds of moves, two of which are among moves \(2,4,6\), and \(8\), and the other is one of moves \(1,3,5\), and \(7\), the latter of which is used only once.

## Proof

We will show that any ways of moves that does not fall into the two patterns above can be boil down to one of them without increasing the moves. First, we consider the case where $3$ kinds of moves are used. (We omit the case that coincides with one of them with inversion or rotations, and those using both of the moves in the opposite directions like moves $1$ and $4$.)### Using symmetry

The second condition claims that three kinds of move are used, but one of them is used once. Therefore, we can exhaustively search which of moves \(1,3,5\), and \(7\) to use once to boil down to the case with two moves.

The case with two kinds of move can be covered relatively easily using symmetry. By letting \((A',B') = (B,-A), s'=s_3s_4s_5s_6s_7s_8s_1s_2\), we can rotate the destination and the direction of moves by \(90\) degrees. Thus, we can inspect the case with the plane rotated by \(0\), \(90\), \(180\), and \(270\) degrees, for each of which it is sufficient to check the following \(9\) patterns:

- Using no moves
- Using only move \(1\)
- Using only move \(2\)
- Using moves \(1\) and \(2\)
- Using moves \(1\) and \(3\)
- Using moves \(1\) and \(4\)
- Using moves \(1\) and \(6\)
- Using moves \(1\) and \(8\)
- Using moves \(2\) and \(4\)

If you’d prefer, you may flip the plane vertically to coincide the \(4\)-th with \(8\)-th and \(6\)-th with \(7\)-th.

### Another solution

Let \(\mathrm{dp}_{i,j,k}\) (Dynamic Programming) be the minimum number of operations required when we have determined the \(2^0\)’s, \(2^1\)’s, \(\ldots\), and \(2^i\)’s places of the numbers of moves \(1,2,\ldots\), and \(8\), and the carries and borrows of \(x\)- and \(y\)- coordinates are \(j\) and \(k\), respectively. If the transitions are precalculated, the \(dp\) requires at most \(37\) kinds of transitions from \((\log A \times 7 \times 7)\) states per one case, for a total of about \(6 \times 10^8\) steps for \(T=10^4\). Although this is a relatively large number of the number of steps in the intended solutions of most problems, this actually works in less than \(1\) second.

While the actual execution time varies depending on the constant factor of the implementation, we can use an almost obvious fact that the worst case is \(s_1s_2s_3s_4s_5s_6s_7s_8=\) `11111111`

to check with Code Test that it indeed finish within the time limit before confidently submitting.

posted:

last update: