| # | User | Rating |
|---|---|---|
| 1 | tourist | 3947 |
| 2 | ecnerwala | 3654 |
| 3 | jiangly | 3627 |
| 4 | jqdai0815 | 3620 |
| 5 | orzdevinwang | 3612 |
| 6 | Benq | 3586 |
| 7 | Radewoosh | 3582 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | ksun48 | 3474 |
| # | User | Contrib. |
|---|---|---|
| 1 | awoo | 163 |
| 2 | maomao90 | 160 |
| 3 | adamant | 156 |
| 4 | atcoder_official | 155 |
| 5 | maroonrk | 153 |
| 6 | -is-this-fft- | 148 |
| 6 | SecondThread | 148 |
| 8 | Petr | 147 |
| 9 | nor | 145 |
| 10 | cry | 144 |
https://codeforces.com/contest/1983/problem/D
In this problem. Count inversion concept comes into play but why ?? What is the exact intuition behind it? Like why only count inversion. and what are the other type of problems where this concept is used.
If the two arrays can be transformed to the same one, then they can also be transformed to where they are both sorted in ascending order. The number of swaps of consecutive elements to sort an array in ascending order is the number of inversions. For the sake of the explanation, let the first array have less inversions. So we sort it and still have to use more swaps to sort the second array, so if $$$inv_b - inv_a \equiv 0 \ (mod \ 2)$$$, then you can just repeatedly swap some two elements in the first array until the second array is sorted.
Okay thnx