PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
EASY
PROBLEM:
Given arrays A and B of size N. You can swap A_i and A_{i+1} with cost A_i-A_{i+1}. Determine the minimum total cost to make A equal to B.
EXPLANATION:
Suppose we do a number of swaps to A to make it equal to B, and the element at index i in the original array is now at index pos_i.
I claim that the total cost incurred in the above case equals \sum A_i(pos_i-i).
Proof
Let pos_i represent the current position of, the element at index i in the original array. Initially, pos_i=i for all i.
Everytime we swap element A_i (of the original array) with the element A_j to its right:
- pos_i increases by 1,
- pos_{j} decreases by 1,
- the cost increases by A_i-A_{j}\implies the cost increases by A_i and decreases by A_{j}.
We can therefore notice that everytime pos_i is increased by 1, the cost increases by A_i. Similarly, the cost decreases by A_i everytime pos_i is decreased by 1.
In the end, the total number of times the cost increases by A_i is equal to pos_i-i (the cost decreases if pos_i-i is negative).
Therefore, we can calculate the cost contributed by each A_i separately and then add them together, giving us the equation \sum A_i(pos_i-i).
When the elements of A are distinct, array pos is unique and the total cost is therefore fixed. What about the case when A has repeating elements?
I claim that any sequence of swaps that makes A equal B has the same total cost. That is, say there exists i,j\space(i\ne j) such that A_i=A_j. Then, the total cost to rearrange A such that A_i and A_j are at indices pos_j and pos_i (instead of pos_i and pos_j) is the same.
(The proof of this is trivial and left to the reader as an exercise).
Therefore, given A and B, it suffices to find any valid mapping pos such that B_{pos_i} = A_i. We can then use the equation given above to calculate the answer.
Implementation
Create array of pairs C = \{(A_1, 1), (A_2,2),\dots,(A_N,N)\} and D = \{(B_1, 1), (B_2,2),\dots,(B_N,N)\}.
Sort the elements of C and D by the first value of their pairs, in ascending order (breaking ties arbitrarily). Then, since arrays A and B have the same elements, it is easy to see that the first value of C_i equals the first value of D_i for all i.
So, set the value of pos_{C_i.second} as D_i.second, for all i. The validity of this mapping can be shown trivially.
TIME COMPLEXITY:
We sort the array of pairs C and D in O(N\log N) each. We then iterate from 1 to N once, to generate the array pos and calculate the answer. The total time complexity is therefore
per test case.
SOLUTIONS:
Editorialist’s solution can be found here.
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters