# 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