What is the minimum cost of arranging the range a (n) (a [i] <= 20) such that the equal values will form a continuous segment?

You provide 1 string: a1, a2..an (a [i] <= 20)

Requirement: The minimum cost (number of steps) to swap any two elements in the sequence so that the final sequence obtained has equal values that lie in succession:

Each step you can only choose 2 adjacent values to swap: swap (a [i], a [i + 1]) = 1steps

example:

1 1 3 1 3 2 3 2

Swap (a [3], a [4])

Swap (a [6], a [7])

-> 1 1 1 3 3 3 2 2

minimum = 2

I need your help.

Solution

Note that since A[i] <= 20 we can go ahead and enumerate every subset of all A[i] and fit comfortably within any time constraints.

Let M be the number of unique A[i], then there is a O(NM + M * 2^M) dynamic programming solution with bitmasks.

note that when I say moving an A[i] I mean moving every element with value A[i]

To understand how we do this let's first consider the brute force solution. We have some set of unique A[i] moved to the front of the string, and then at each step we pick the next A[i] to move behind what we had originally. This is O(M! * N).

There's one important observation to be made here: if we have some set of A[i] at the start of the string, and then we move the next one, the order of our original set of A[i] doesn't actually matter. Any move will cost the same regardless of the order.

Let cost(subset, A[i]) be the cost of moving all A[i] behind that subset of A[i] at the front of the string. Then we can write the following:

dp = [float('inf')] * (1 << M) # every subset of A[i]
dp[0] = 0
for mask in range(len(dp)):
    for bit in range(M):
        # if this A[i] hasn't been moved to the front, we move it to the front
        if (mask >> bit) & 1 == 0: 
            dp[mask^(1 << bit)] = min(dp[mask^(1 << bit)], dp[mask] + cost(mask, bit))

If we compute cost naively then we have O(M * 2^M * N). However we can precompute every value of cost with O(1) per value.

Here's how we can do this:

Idea: The number of swaps needed to sort an array is the number of inversions.

Let's define a new array inversions[M][M], where inversions[i][j] is the number of times j comes after i in the arr. For clarity here's how we would compute it naively:

for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        if arr[i] != arr[j]: inversions[arr[i]][arr[j]] += 1

Assume that we have inversions, then we can compute cost(subset, A[i]) like so:

cost = 0
for bit in range(M):
    # if bit isn't in the mask and thus needs to get swapped with A[i]
    if (subset >> bit) & 1 == 0:
        cost += inversions[bit][A[i]]

What's left is the following:

Compute inversions in O(NM). This can be done with keeping a count of each M at each index in N.
Currently cost is O(M) and not O(1). We can run a separate dynamic programming on cost to build an array cost[(1 << M)][M], where cost[i][j] is the cost to move item j to subset i.

For sake of completeness here is a complete code written in C++. It's my submission for the same problem on codeforces. Note that in that code cost is named contribution.