Half Shuffle

Let $M=\{i\mid P_i\ne i\}$ be the set of misplaced positions and let $m=|M|$.

If $m=0$, the answer is $0$.

If $1\le m\le N$, the answer is $1$. Choose every misplaced position and add arbitrary fixed positions until exactly $N$ positions are chosen; one rearrangement can sort them all.

Now assume $m>N$. Let $A$ and $B$ be the position sets chosen in two rearrangements. Since $|A|=|B|=N$,

$$|A\cap B|=|\{1,\cdots,2N\}\setminus(A\cup B)|.$$

Every position outside $A\cup B$ is never touched, so it must already be a fixed point.

If at least one fixed point exists, the answer is $2$. One rearrangement is impossible because $m>N$, while a fixed point can be kept outside both chosen sets so that the permutation can always be finished in two rearrangements.

Now suppose there is no fixed point. Then no position can lie outside $A\cup B$, so the equality above forces $A\cap B=\varnothing$. Thus $A$ and $B$ partition all positions. Every position in is touched only by the first rearrangement, so all of them must already be correct after that rearrangement.

Decompose the permutation into cycles. If $A$ contains only part of a cycle, at least one position in that part needs a value that remains in $B$. Therefore $A$ must be a union of whole cycles. Conversely, if some cycle lengths sum to exactly $N$, those cycles can be sorted in the first rearrangement and all remaining cycles in the second.

Hence, when there is no fixed point, two rearrangements are possible if and only if some subset of the cycle lengths sums to exactly $N$. This is a standard subset-sum DP and can be checked in $O(N^2)$ time.

If such a subset exists, the answer is $2$; otherwise it is $3$. Two rearrangements are impossible by the condition above, while one preliminary rearrangement can create a fixed point, after which at most two more rearrangements are sufficient.

Therefore the answer is always one of $0,1,2,3$. The time complexity is $O(N^2)$ per test case and the memory complexity is $O(N)$.

Solution written by GPT5.6