a bit of codeforces: Round #212 (Div. 2)

Problem C
C. Insertion Sort

Summary:
By swapping any two element, find the minimum number of swaps needed by insertion sort, and find the number of ways to do so.

Solution:
Firstly, the number of swaps performed by the insertion sort is equal to the number of inversion in the array. (I think there are lots of proofs on this fact)
Secondly, the number of inversion in [0 .. j] is exactly the number of elements bigger than A[j] in [0 .. j].
We need a DP table to solve this problem.
Store B[i][j] which is the number of elements in [0 .. j] which is bigger than i, and
C[i][j] the number of elements in [0 .. j] which is smaller than i.
Now if we swap two elements, in hope for less swap necessary, we should only swap when \(i < j\), A[i] > A[j]. When the elements are swapped, we have:
1. Number of inversions is reduced by B[A[i]][i] + B[A[j]][j]
2. Since we are place A[i] to j which is further up, we need to take of elements in [i+1 .. j-1] which are smaller than A[i] as the number of actual inversion contributed by those elements in [i+1 .. j-1] has actually reduced by 1. Therefore, actual number of inversion is reduced by C[A[i]][j] - C[A[i]][i].
3. Similarly, A[j] is placed to position i, hence all elements in [i+1 .. j-1] which are smaller than A[j] will actually contribute additional 1 inversion. Hence we add C[A[j]][j] - C[A[j]][i].
4. Finally we add the contribution of A[i] and A[j] in their respective new position, hence B[A[i]][j] + B[A[j]][i] - 1. (The -1 in the end is because initially B[A[j]][i] includes contribution by A[i], but since we move A[i] out of [0..i], it is reduced by 1)
Hence we end up with \(O(N^2)\) algorithm, which performs calculation of inversions after swapping in \(O(1)\) time.