[Tutorial] Problems about swapping adjacent elements

Правка en2, от TheScrasse, 2021-06-24 01:25:28

Hello everyone,
problems about swapping adjacent elements are quite frequent in CP, but they can be tedious.

Counting inversions

Let's start from a simple problem.

You are given a permutation 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})$$$. So you need at least $$$k$$$ moves to sort the array.
On the other hand, if the array is not sorted you can

Теги 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)