Official

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:

  1. Using at most two kinds of moves.
  2. 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$.)
  • If moves $1$, $2$, and $3$ are used, we can obtain the same result by decreasing moves $1$ and $3$ once each and increasing move $2$ once. By repeating this until one of the numbers of moves $1$ and $3$ becomes $0$, we can make the number of moves at most $2$.
  • If moves $1$, $2$, and $4$ are used, and move $1$ is used twice or more, we can obtain the same result by decreasing move $1$ twice, increasing move $2$ once, and decreasing move $4$ once. By repeating this until the number of move $1$ becomes $1$ or less, we can make it satisfy the conditions.
  • If moves $1$, $2$, and $7$ are used, it is sufficient to increase move $1$ once and decrease moves $2$ and $7$ once each.
  • If moves $1$, $2$, and $8$ are used, it is sufficient to decrease move $1$ twice and increase moves $2$ and $8$ once each.
  • If moves $1$, $3$, and $6$ are used, it is sufficient to decrease move $1$ once.
  • If moves $1$, $4$, and $6$ are used, it is sufficient to decrease move $1$ twice and increase moves $4$ and $6$ once each.
    • If four or more kinds of moves are used, at most two of them are moves $2,4,6$ or $8$ because the moves in opposite directions are not chosen, and thus at least two of them are $1,3,5$, or $7$. By choosing two of them and any other one, we can decrease the number of moves by one.

    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: