What is the mathematical proof for " SWAPGAME | MAKE THAT ARRAY! | September Starters 13 | Problem Solution | CodeChef - 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.

Thank you!

Kudos to the author for the perfect explanation.