F - Simultaneous Swap Editorial by Kiri8128


In problems involving two arrays, sometimes it can be easier to think about them by fixing one of the arrays.

First, if \(A\) and \(B\) are different as multisets, it’s impossible, so let’s assume that the multisets are identical.

If the elements of \(A\) are distinct, consider sorting \(A\) and \(B\) so that \(A\) is in ascending order. Assume we perform the operation with \(i=1,\ j=2,\ k=3\) when:

\[A: 1, 2, 3, \cdots \\ B: 4, 5, 6, \cdots\]

It becomes:

\[A: 2, 1, 3, \cdots \\ B: 6, 5, 4, \cdots\]

After fixing \(A\) back, it eventually becomes:

\[A: 1, 2, 3, \cdots \\ B: 5, 6, 4, \cdots\]

This means a 3-cycle permutation has been applied to \(B\). In this way, it can be seen that any 3-cycle permutation can be performed. Generally, it is known that the set of even permutations coincides with the set of permutations that can be expressed as a product of 3-cycle permutations. Therefore, we can determine it by examining the parity of the inversion number. If \(A\) contains multiple identical elements, it is always possible as this allows a swap in \(A\) without changing the result.

posted:
last update: