B - Swap if Equal Length and Sum Editorial by evima
The sum and the number of inversions of a sequence are invariant before and after operations.
When \(A\) and \(B\) have the same sum and number of inversions, it is always possible. We show this through a specific construction method.
We may assume that the number of \(1\)s in \(A\) is at most \(\frac{N}{2}\) (if not, consider the sequence with \(0\) and \(1\) swapped).
Define \(a_i,b_i\) such that the \(i\)-th \(1\) from the left in \(A,B\) is \(A_{a_i},B_{b_i}\) respectively.
As long as \(A \neq B\), repeat the following operation:
- Let \(l\) be the smallest \(i\) such that \(a_i>b_i\), and \(r\) be the largest \(i\) such that \(a_i<b_i\), and set \(d=\min(a_l-b_l,b_r-a_r)\)
- Swap the \((a_l-d)\)-th through \(a_l\)-th elements of \(A\) with the \(a_r\)-th through \((a_r+d)\)-th elements
Each time we perform one operation, the number of \(i\) such that \(A_i=B_i=1\) increases by at least \(1\), so this operation terminates in at most \(\lfloor\frac{N}{2}\rfloor\) times, and \(A\) matches \(B\).
posted:
last update: