[Tutorial] Problems about swapping adjacent elements

Правка en15, от TheScrasse, 2021-06-24 19:45:46

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 - 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 - pos(x)$$$. For each $$$x$$$, $$$x - 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).

1430E - String Reversal (rating: 1900)

Hint 1
Hint 2
Hint 3
Solution

EGOI 2021/2

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++)

Other problems

IOI 2019/1 JOI 2021/3 (Final Round)

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 that can be solved with this technique.

I hope you enjoyed the blog!

Теги tutorial, swap, greedy, inversions

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en24 Английский TheScrasse 2021-07-02 09:45:23 17 Tiny change: 'i$ in the reversed string (i' -> 'i$ in the palindromic string (i'
en23 Английский TheScrasse 2021-07-01 15:05:04 81
en22 Английский TheScrasse 2021-07-01 01:10:53 66 Tiny change: '-ex.pdf)\n--------' -> '-ex.pdf)\n[problem:103148B]\n--------'
en21 Английский TheScrasse 2021-06-25 09:54:33 1 Tiny change: 'nal strings, i.e. the' -> 'nal string, i.e. the'
en20 Английский TheScrasse 2021-06-25 09:50:09 35
en19 Английский TheScrasse 2021-06-24 21:10:59 57 Tiny change: '4])<br>\n[J' -> '4])<br>\n[problem:1526D] ([user:somil_jain_120])<br>\n[J'
en18 Английский TheScrasse 2021-06-24 20:28:03 566 Tiny change: '89585e71/)<br>\n[JOI' -> '89585e71/) ([user:Arceus03]<br>\n[JOI'
en17 Английский TheScrasse 2021-06-24 19:49:22 50
en16 Английский TheScrasse 2021-06-24 19:48:13 4 Tiny change: 'I19_shoes)\n[JOI 202' -> 'I19_shoes)<br\n[JOI 202' (published)
en15 Английский TheScrasse 2021-06-24 19:45:46 689
en14 Английский TheScrasse 2021-06-24 19:38:26 2296
en13 Английский TheScrasse 2021-06-24 18:49:16 2455
en12 Английский TheScrasse 2021-06-24 18:31:03 2565
en11 Английский TheScrasse 2021-06-24 17:42:49 2304
en10 Английский TheScrasse 2021-06-24 17:38:16 501
en9 Английский TheScrasse 2021-06-24 17:26:59 1099 Tiny change: 'yyx}$ (or \text{yxxy}). Instead' -> 'yyx}$ (or $\text{yxxy}$). Instead'
en8 Английский TheScrasse 2021-06-24 17:13:35 1710
en7 Английский TheScrasse 2021-06-24 16:09:57 26 Tiny change: 'o skip it if you al' -> 'o skip it and jump to the problems if you al'
en6 Английский TheScrasse 2021-06-24 16:08:27 428 Tiny change: ' \dots, a_14 = 11$ (in' -> ' \dots, a_{14} = 11$ (in'
en5 Английский TheScrasse 2021-06-24 15:54:59 2011 Tiny change: 'inversions\nYou can ' -> 'inversions in $O(n \log n)$\nYou can '
en4 Английский TheScrasse 2021-06-24 14:02:25 501
en3 Английский TheScrasse 2021-06-24 13:56:57 4139 Tiny change: '$k$ moves.' -> '$k$ moves.\n\n#### Proof 2\nLet's '
en2 Английский TheScrasse 2021-06-24 01:25:28 882 Tiny change: ' everyone,\nproblems' -> ' everyone,<br>\nproblems'
en1 Английский TheScrasse 2021-06-24 00:40:41 69 Initial revision (saved to drafts)