Shiro's Mirror Duel

This is interactive, so the coin is real. The correct mindset is not “force every exact swap”. You cannot. The play is to make progress in a structure that survives the mirror randomness.

Define $m(i)=n-i+1$. Position $i$ is mirrored with position $m(i)$, and value $v$ is mirrored with value $m(v)$. In the final sorted permutation, the value-pair $\{i,m(i)\}$ must occupy the position-pair $\{i,m(i)\}$.

Phase 0: handle the middle

If $n$ is odd, the middle position $c=(n+1)/2$ mirrors to itself, and the middle value $c$ also mirrors to itself. So before doing pair logic, put value $c$ into position $c$.

While $pos[c] \ne c$, query $(c,pos[c])$.

The judge either swaps $(c,pos[c])$, which succeeds, or swaps $(c,m(pos[c]))$, which does not move value $c$. So each attempt succeeds independently with probability $1/2$, and the expected cost is $2$ moves. Annoying, but tiny.

Phase 1: make every value-pair symmetric

Now process every $i$ from $1$ to $\lfloor n/2 \rfloor$. Let:

• $a=pos[i]$
• $b=pos[m(i)]$

If $a+b=n+1$, then values $i$ and $m(i)$ are already in mirrored positions.

Otherwise query:

$(a,m(b))$

Why does this work? There are two possible swaps:

• Swap $(a,m(b))$. Value $i$ moves to $m(b)$, while value $m(i)$ stays at $b$. Those positions are mirrored.
• Swap $(m(a),b)$. Value $m(i)$ moves to $m(a)$, while value $i$ stays at $a$. Those positions are mirrored.

Either way, the pair becomes symmetric after exactly one query. No coin drama here. The coin tries to be clever and still gets clowned.

Also, once a processed value-pair occupies both positions of some mirror pair, later phase-one operations for different values cannot accidentally break it. To touch one of those positions, the operation would have to involve one of those already processed values or its mirror position, but that whole mirror pair is already occupied by the processed pair.

So phase one costs at most $\lfloor n/2 \rfloor$ moves.

Phase 2: move symmetric blocks to their targets

After phase one, every pair $\{i,m(i)\}$ is a block sitting in some mirrored position-pair. Now process $i=1,2,\dots,\lfloor n/2 \rfloor$ and put block $i$ into positions $i$ and $m(i)$.

While the block is not fully correct:

• If $pos[i] \ne i$, query $(i,pos[i])$.
• Otherwise, value $i$ is already correct, so query $(m(i),pos[m(i)])$.

Why does this make sense?

Suppose the block $\{i,m(i)\}$ is currently symmetric, but not at its target. If we query $(i,pos[i])$, then:

• one outcome swaps value $i$ into position $i$;
• the mirrored outcome swaps value $m(i)$ into position $m(i)$.

So from the state where neither side is correct, one query always makes exactly one side correct.

From the state where exactly one side is correct, querying the other side has two outcomes:

• with probability $1/2$, it fixes the other side too, and the block is done;
• with probability $1/2$, it swaps the already-correct side back out, returning to the zero-correct state.

Let $A$ be the expected number of moves from zero correct positions, and $B$ from one correct position. Then:

$A=1+B$

and

$B=1+\frac12 A$

Solving gives $A=4$. So each block costs $4$ moves in expectation during phase two. There are $\lfloor n/2 \rfloor$ blocks, so this phase costs about $2n$ moves in expectation.

Total expected moves:

$\frac n2 + 2n = 2.5n$

plus the tiny middle handling when $n$ is odd. The limit is $\lfloor 2.5n+800 \rfloor$, so the extra $800$ is there to absorb unlucky coin streaks. There is no deterministic guarantee against absurd randomness, because the problem literally hands control to a fair coin. That is the whole gimmick.

Correctness summary

Phase 0 places the only self-mirrored value correctly when it exists.

Phase 1 guarantees that every mirrored value-pair $\{i,m(i)\}$ occupies some mirrored pair of positions.

Phase 2 processes target pairs from outside representatives $1$ through $\lfloor n/2 \rfloor$. Once a block is fixed at its target pair, later blocks cannot touch it, because their values are elsewhere and their target pairs are different. The loop for a block ends only when both values are in their exact sorted positions. Therefore, after all blocks are processed, every position contains its own value, so the permutation is sorted.