This editorial explains how to construct a solution with at most \(3500\) operations (the bonus task in the main editorial). It assumes you have read the main editorial.

Because a swap usually costs three operations, we can permute \(A\) arbitrarily in \(3N\) operations. Thus, if \(A\) and \(B\) can be matched as multisets, we can make \(A = B\) in \(3N\) operations from there.

To minimize the total absolute difference, we pair the \(i\)-th smallest element of \(A\) with the \(i\)-th smallest of \(B\).

Below is the overall flow of our solution. Here, we mark an element of \(A\) “−” if it is smaller than its partner in \(B\), “+” if larger, “=” if equal.

• While any + or - remains, repeat:
  • Extract only the + and − elements and, using swaps, sort them into this order: - - - … - - - + + + … + + +. (Phase 1)
  • For each + from left to right, while it is +, pair it with the closest − to its left and perform the operation. (Phase 2)

We analyze the number of operations in this solution. First, the number of operations in Phase 2 is \(\frac{\sum |A'_i - B'_i|}{2}\), where \(A'\) and \(B'\) are \(A\) and \(B\) after sorting. Let \(D'_i = A'_i - B'_i\). By considering restoring \(A'\) and \(B'\) from a fixed \(D'\), we can see that \(D'\) has the following requirements:

• \(\sum D'_i = 0\)
• \(\sum |D'_i - D'_{i+1}| \le M\)

The \(D\) that satisfies these and maximizes \(\sum |D_i|\) is obtained by arranging \(\frac{N}{2}\) copies of \(-\frac{M}{2}\) and then \(\frac{N}{2}\) copies of \(+\frac{M}{2}\). Thus, Phase 2 uses at most \(\frac{NM}{4}\) operations.

Next, consider the number of operations in Phase 1. Each iteration of Phase 1 can be implemented by the number of swaps equal to the number of + that need rearranging, so the first iteration of Phase 1 uses at most \(\frac{3N}{2}\) operations. For later iterations, the number of swaps is the total number of elements that are still − after passing all +, which is bounded by \(M\) because each such element decreases the maximum \(D\) by \(1\). Thus, Phase 1 uses at most \(\tfrac{3N}{2} + 3M\) operations.

We may occasionally have to swap \(A_1\) and \(A_N\), but the number of this event is bounded by a constant or happen only when \(\sum D\) is small.

Therefore, the whole solution uses \(\frac{3N}{2} + 3M + \frac{NM}{4} + 3N = \frac{NM}{4} + \frac{9N}{2} + 3M\) operations. It can be seen that this solution has the optimal constant factor with respect to \(NM\).