SWAPGAME - Editorial

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

O(2\times N\log N+N) \approx O(N\log N)

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

I honestly feel that the time constraints should have been more accommodative (2 secs. maybe), because the ‘constructive’ solutions that used things such as Segment Trees also deserved to get AC as they too could have only been created after reaching the key observation.

5 Likes

We never even considered Segment Trees as a solution, when a straightforward sorting based solution existed. Even then, some solutions passed using Segment Trees.

So according to me, the constraints were fine.

you really should stop spoiling the editorials for us!

I think it can be done in O(n) time complexity
for i in range(int(input())):
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ans = 0
for i in range(n):
ans -= a[i](i+1)
for i in range(n):
ans += b[i]
(i+1)
print(ans)

1 Like

To show the accuracy of the evaluation given, imagine that you can (temporarily) have more than one entry in a particular location of the array, and break the swapping action into to two steps. Moving the A_i to the succeeding position costs A_i, then moving the A_{i+1} item down to the prior position refunds A_{i+1}. Clearly this gives the same net cost of (A_i - A_{i+1}), but we can also see that any move can be achieved by moving each entry directly to their final locations for their half of the cost (positive or negative) and summing the one-entry move cost. This is what the formula given, \sum_i A_i(pos_i - i) expresses.

This scheme also allows us to score each starting or finishing position, by imagining all entries piled up at the start of the array and moving them to their locations. Then the score for the A array will be V_A = \sum_i A_i\cdot i and of course the score for B will be V_B = \sum_j B_j\cdot j and the cost for moving between them will be V_B - V_A, since we are given that the transition is possible.