EQBEND - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given an array A, find the minimum number of adjacent swaps needed to make its first and last elements equal.

EXPLANATION:

Let’s fix a value X, and suppose we want to make A_1 = A_N = X happen.

Since we’re working with adjacent swaps, the optimal way to do this is:

  1. Take the leftmost occurrence of X in the array, and keep swapping it left till it reaches the first position.
  2. Take the rightmost occurrence of X in the array, and keep swapping it left till it reaches the last position.

Note in particular that since N \ge 2, we need at least two occurrences of X in the array for this to be possible at all.

So, if we define \text{first}[X] to be the leftmost index containing X, and \text{last}[X] to be the rightmost index containing X, we then need:

  • \text{first}[X] \lt \text{last}[X], since if they’re equal then there’s only one copy of X in the array.
  • \text{first}[X]-1 swaps to move the first occurrence to index 1.
  • N-\text{last}[X] swaps to move the last occurrence to index N.

Thus, when \text{first}[X] \lt \text{last}[X], we need N-1+\text{first}[X] - \text{last}[X] swaps to make A_1 = A_N = X.
(This is using 1-indexing; if you use 0-indexing change the costs appropriately.)

The optimal solution is then obtained by taking the minimum of this across all choices of X.

Note that if no X appears multiple times in the array, the answer is -1 instead since it’s impossible to make A_1 = A_N.

TIME COMPLEXITY:

\mathcal{O}(N + 100) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    first = [-1]*101
    last = [-1]*101
    for i in range(n):
        last[a[i]] = i
        if first[a[i]] == -1: first[a[i]] = i
    
    ans = n+5
    for x in range(1, 101):
        if first[x] < last[x]:
            ans = min(ans, first[x] + n-1-last[x])
    if ans == n+5: ans = -1
    print(ans)