What is the mathematical proof for " - YouTube " solution?
Consider ith element in array A, and its pos in array B be j. You know that you gotta move this element from index i to index j via some sequence of swaps. The score when two elements (of index u and u+1) are swapped is a[u] - a[u+1].
The total score must be in form of-> C1 * a[1] + C2 * a[2] …Cu * a[u]…Cn * a[n]. Where C1,C2…Cn are some integer coefficients. I will call Cu * a[u] as the “contribution” of a[u] in the score. Note when a[u] moves a distance 1 right in some swap +a[u] is added to score. (a[u+1] is subtracted from score too, but it is not a part of contribution of a[u]).
In general, an element a[u] when it moves a “net distance” of D. It’s “contribution” is a[u] * D. This is because everytime it moves +1 units +a[u] is added, and -1 units, then -a[u] is added. So it only depends on “net distance” travelled not on “how” it is being travelled.
So what’s the contribution of a[i] to the score? It is simply a[i] * (j-i). As it has to move a net distance of j-i, to get to its correct position. Note that in process of moving a[i], it might affect the pos of some elements. But it won’t matter, because the net distance moved by every element to get to its correct position will remain unchanged. It’s like saying an element initially in pos 5, has to go to position 6. But in the process, it goes to 5->3 (Due to movement of a[i]) Still it has to reach 8. So net distance moved equals 3-5 + 6-3, 3 gets cancelled out and net distance is still +1.
But what if there are duplicates? What would be their correct position.
Example: if my array A is {2 , 2 , 2 , 3 , 4} and B is {3 , 2 , 2 , 4 , 2} . What is the “correct” position of a[1] (correct pos is its final pos in array B). Is it 2 or 3 or 5?
In this case. Suppose a[i], a[j], a[k] are duplicates and their correct position be I , J , K respectively in array B. (In the optimal solution) The sum of “contribution” of all duplicates is → a[i] * (I - i ) + a[j] * (J-j) + a[k] * (K-k). Since a[i]=a[j]=a[k]=X (say). This simplifies to X*(I + J + K - i - j - k). Which is independent of the order of (I,J,K) (This only depends on sum of I, J and K). This means, u can assign any correct position to duplicates. (I, J , K) will work, so will (J, K , I) and so will (K , J ,I). The result is not gonna change.
5 Likes
Thank you! 
Kudos to the author for the perfect explanation.