### TheScrasse's blog

By TheScrasse, history, 3 years ago,

Hello everyone,
problems about swapping adjacent elements are quite frequent in CP, but they can be tedious. In this tutorial we will see some easy ideas and use them to solve some problems of increasing difficulty. I tried to put a lot of examples to make the understanding easier.
The first part of the tutorial is quite basic, so feel free to skip it and jump to the problems if you already know the concepts.

Target: rating $[1400, 2100]$ on CF
Prerequisites: greedy, Fenwick tree (or segment tree)

## Counting inversions

Let's start from a simple problem.

You are given a permutation $a$ of length $n$. In one move, you can swap two elements in adjacent positions. What's the minimum number of moves required to sort the array?

#### Claim

The result $k$ is equal to the number of inversions, i.e. the pairs $(i, j)$ ($1 \leq i < j \leq n$) such that $a_i > a_j$.

#### Proof 1

Let $f(x)$ be the number of inversions after $x$ moves.
In one move, if you swap the values on positions $i, i + 1$, $f(x)$ either increases by $1$ or decreases by $1$. This is because the only pair $(a_i, a_j)$ whose relative order changed is $(a_i, a_{i+1})$. Since the sorted array has $0$ inversions, you need at least $k$ moves to sort the array.
For example, if you have the permutation $[2, 3, 7, 8, 6, 9, 1, 4, 5]$ ($16$ inversions) and you swap two adjacent elements such that $a_i > a_{i+1}$ (getting, for example, $[2, 3, 7, 6, 8, 9, 1, 4, 5]$), the resulting array has $15$ inversions, and if you swap two adjacent elements such that $a_i < a_{i+1}$ (getting, for example, $[3, 2, 7, 8, 6, 9, 1, 4, 5]$), the resulting array has $17$ inversions.

On the other hand, if the array is not sorted you can always find an $i$ such that $a_i > a_{i+1}$, so you can sort the array in $k$ moves.

#### Proof 2

For each $x$, let $f(x)$ be the number of inversions if you consider only the elements from $1$ to $x$ in the permutation.
First, let's put $x$ at the end of the permutation: this requires $x - \text{pos}(x)$ moves. That's optimal (the actual proof is similar to Proof 1; in an intuitive way, if you put the last element to the end of the array, it doesn't interfere anymore with the other swaps).
For example, if you have the permutation $[2, 3, 7, 8, 6, 9, 1, 4, 5]$ and you move the $9$ to the end, you get $[2, 3, 7, 8, 6, 1, 4, 5, 9]$ and now you need to sort $[2, 3, 7, 8, 6, 1, 4, 5]$. Hence, $f(x) = f(x-1) + x - \text{pos}(x)$. For each $x$, $x - \text{pos}(x)$ is actually the number of pairs $(i, j)$ ($1 \leq i < j \leq x$) such that $x = a_i > a_j$. So $f(x)$ is equal to the number of inversions.

#### Counting inversions in $O(n \log n)$

You can use a Fenwick tree (or a segment tree). There are other solutions (for example, using divide & conquer + merge sort), but they are usually harder to generalize.
For each $j$, calculate the number of $i < j$ such that $a_i > a_j$.
The Fenwick tree should contain the frequency of each value in $[1, n]$ in the prefix $[1, j - 1]$ of the array.
So, for each $j$, the queries look like

• $res := res + \text{range_sum}(a_j + 1, n)$
• add $1$ in the position $a_j$ of the Fenwick tree

#### Observations / slight variations of the problem

By using a Fenwick tree, you are actually calculating the number of inversions for each prefix of the array.

You can calculate the number of swaps required to sort an array (not necessarily a permutation, but for now let's assume that its elements are distinct) by compressing the values of the array. For example, the array $[13, 18, 34, 38, 28, 41, 5, 29, 30]$ becomes $[2, 3, 7, 8, 6, 9, 1, 4, 5]$.

You can also calculate the number of swaps required to get an array $b$ (for now let's assume that its elements are distinct) starting from $a$, by renaming the values. For example,
$a = [2, 3, 7, 8, 6, 9, 1, 4, 5], b = [9, 8, 5, 2, 1, 4, 7, 3, 6]$
is equivalent to
$a = [4, 8, 7, 2, 9, 1, 5, 6, 3], b = [1, 2, 3, 4, 5, 6, 7, 8, 9]$

$a^{-1}$ (a permutation such that $(a^{-1})_{a_x} = x$, i.e. $(a^{-1})_x$ is equal to the position of $x$ in $a$) has the same number of inversions as $a$. For example, $[2, 3, 7, 8, 6, 9, 1, 4, 5]$ and $[7, 1, 2, 8, 9, 5, 3, 4, 6]$ have both $16$ inversions. Sketch of a proof: note that, when you swap two elements in adjacent positions in $a$, you are swapping two adjacent values in $a^{-1}$, and the number of inversions in $a^{-1}$ also increases by $1$ or decreases by $1$ (like in Proof 1).

Hint 1
Hint 2
Hint 3
Solution

Hint 1
Hint 2
Hint 3
Hint 4
Solution

## arc088_e (rating: 2231)

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Implementation (C++)

## arc097_e (rating: 2247)

Hint 1
Hint 2
Hint 3
Hint 4
Solution

Implementation (C++)

## Conclusions

We've seen that a lot of problems where you have to swap adjacent elements can be tackled with greedy observations, such as looking at the optimal relative positions of the values in the final array; then, a lot of these problems can be reduced to "find the number of inversions" or similar.

Of course, suggestions/corrections are welcome. In particular, please share in the comments other problems where you have to swap adjacent elements.

I hope you enjoyed the blog!

• +223

| Write comment?
 » 3 years ago, # |   +10 This problem uses the same idea as "String reversal", but with an extra observation required : https://atcoder.jp/contests/arc120/tasks/arc120_c.
•  » » 3 months ago, # ^ |   0 Hi, I tried to solve arc120_c problem, but i couldn't. I am unable to understand, how the observation (in spoiler) helps to solve the problem. Could you explain it? Spoilerchange Bi = Bi + i and Ai = Ai + i
 » 3 years ago, # | ← Rev. 2 →   +19 Amazing Blog!I came across this concept while participating in one of Hackerearth's Circuit Challenges.These 2 problems use the same technique. Problem 1Problem 2
 » 3 years ago, # | ← Rev. 3 →   +12 Very Good Blog for understanding this concept. I came across this concept while solving 1430E (String Reversal)This problem also uses the same concept. 1526-D (Kill Anton)
 » 3 years ago, # |   0 Swap Adjacent Elements Similar problem with little variation.
 » 3 years ago, # |   +38 I personally fancy counting inversions by modifying merge sort. Merge sortdef merge_sort(A): if len(A) <= 1: return A nhalf = len(A) >> 1 A1 = merge_sort(A[:nhalf]) A2 = merge_sort(A[nhalf:]) B = [] A1.reverse(); A2.reverse() while A1 or A2: if not A2 or (A1 and A1[-1] <= A2[-1]): B.append(A1.pop()) else: B.append(A2.pop()) return B  Merge sort (+ inversion count)def merge_sort(A): if len(A) <= 1: return A, 0 nhalf = len(A) >> 1 A1, invcount1 = merge_sort(A[:nhalf]) A2, invcount2 = merge_sort(A[nhalf:]) B = [] invcount = invcount1 + invcount2 A1.reverse(); A2.reverse() while A1 or A2: if not A2 or (A1 and A1[-1] <= A2[-1]): B.append(A1.pop()) else: invcount += len(A1) B.append(A2.pop()) return B, invcount 
 » 3 years ago, # |   +1 How did u calculate the rating for Atcoder problems?
•  » » 3 years ago, # ^ |   +9 He probably used this
•  » » » 3 years ago, # ^ |   +1 Yes.
 » 3 years ago, # |   0 thanks for the amazing blog, I learned a lot :)I am just having trouble understanding this paragraph: $a^{−1}$ (a permutation such that $(a^{−1})_{a_x}=x$, i.e. $(a^{−1})_x$ is equal to the position of $x$ in a) has the same number of inversions as $a$. For example, $[2,3,7,8,6,9,1,4,5]$ and $[7,1,2,8,9,5,3,4,6]$ have both $16$ inversions. Sketch of a proof: note that, when you swap two elements in adjacent positions in $a$, you are swapping two adjacent values in $a^{−1}$, and the number of inversions in $a^{−1}$ also increases by $1$ or decreases by $1$ (like in Proof $1$).
•  » » 3 years ago, # ^ |   +1 $a_x = y \Leftrightarrow (a^{-1})_y = x$. So, when you swap $a_i$ and $a_{i+1}$, you are swapping $i$ and $i+1$ in $a^{-1}$, and you can prove that the number of inversions of $a^{-1}$ also decreases by $1$ if $a_i > a_{i+1}$.
•  » » » 3 years ago, # ^ |   +1 Got it :) Wonderful blog, I hope you can share with us more of these blogs in the future.
•  » » » 3 years ago, # ^ |   0 what do we mean by position of x in a is this position in sorted a ?
•  » » » » 3 years ago, # ^ |   0 $(a^{-1})_1 = 7$ because $a_7 = 1$, i.e. $1$ is in the $7$-th position in $a$.
•  » » » » » 3 years ago, # ^ |   0 Btw very nice explanation and proofs but I am unable to use this property to solve the mentioned problem where objective is to calculate the #swaps to convert the array a into array b. Can you explain ?
•  » » » » » » 3 years ago, # ^ |   0 You can also calculate the number of swaps required to get an array b (for now let's assume that its elements are distinct) starting from a, by renaming the values.Code: for (i = 1; i <= n; i++) p[b[i]] = i; for (i = 1; i <= n; i++) a[i] = p[a[i]]; Then calculate the number of inversions of $a$.
•  » » » » » » » 3 years ago, # ^ |   0 the arc088_c can be converted into String Reversal problem. As we know in palindromic string first half should be equal to reversed of second half So the problem becomes count the minimum number of swaps to convert first half of the string into reverse of it.link to java solution
•  » » » » » » » » 3 years ago, # ^ |   0 What if the two halves of the string don't contain the same characters?
•  » » » » » » » » » 3 years ago, # ^ |   0 I think you are right. But I am wondering why this solution is accepted.
•  » » » » » » » » » 3 years ago, # ^ |   0 My claim: the number of moves required to reverse a string is $2$ times the number of moves to make the string palindrome. I'll try to prove it.
•  » » » » » » » » » 3 years ago, # ^ | ← Rev. 3 →   +8 That's true. For each pair, you need $2, 1, 0, 1, 0$ moves to make $\text{xxyy}, \text{xyxy}, \text{xyyx}, \text{xyy}, \text{yxy}$ palindrome (respectively), and $4, 2, 0, 2, 0$ moves to reverse them. (edit: updated with the cases with a single character)
•  » » » » » » » » » 3 years ago, # ^ |   +8 You forgot about the odd element. Coincidentally it also has to make twice more moves.
 » 3 years ago, # |   0 Worth trying Count inversions in a range
•  » » 3 years ago, # ^ |   0 Is there some solution in $O(Q*log N)$ without square-root trick?
•  » » » 3 years ago, # ^ |   0
 » 3 years ago, # |   +8 CF link for EGOI problem Luna likes Love.
•  » » 3 years ago, # ^ |   0 Updated, thanks.
 » 3 years ago, # |   -10 You may add arc121c too! A new problem!
 » 3 years ago, # |   0 I am having trouble understanding this, Can somebody explain this line  the array [13,18,34,38,28,41,5,29,30] becomes [2,3,7,8,6,9,1,4,5]. Thanks in advance.
•  » » 3 years ago, # ^ |   0