[IOI 2015 — Sorting](http://wcipeg.com/problem/ioi1522)↵
↵
#### Statement↵
If we **resume**, then it says: "We've got an **array $S$ of length $N$** (with **distinct** values) and two arrays **$Jx$ , $Jy$ of length $M$** (all arrays filled with values **from 0 to N-1**). Then the game starts and it consist of **M turns**, each turn $i$ goes this way:↵
↵
- A: We **swap** $S[ Jx[i] ]$ with $S[ Jy[i] ]$ (Jx[i] **can be equal** to Jy[i])↵
- B: Then we're allowed to do **any swap** (we can swap a value with **itself**). I will call this **custom moves**↵
↵
↵
The objective of the game is to make the **array $S$ sorted** with the **lower amount of turns**. We're **guaranteed** that there is a solution with an amount of turns **lower or equal than $M$**.↵
↵
**Limits:**↵
↵
- $N \leqslant 200000$↵
- $M \leqslant 600000$↵
- $M = 3N$, so $M>N$↵
↵
#### First Procedure↵
↵
We'll define a new **array** $F$ of length $N$. Each $F[a]$ will be filled with "Where S[a] value will be at end if we don't run any **custom swaps** on that place". We can build this array in $O( N+M )$. How? In three steps. ↵
↵
↵
↵
- The first of $O(M)$:↵
We make a copy P of array S, and make all the M steps on P so we've got the final array with no extra **custom moves**.↵
- The second of $O(N)$:↵
Now we make another array V of length N. $V[b]$ Will store where the number b value is stored at the end.↵
- And the third also of $O(N)$:↵
We'll set F[i] to the position stored in V of S[i] value. ( F[i] = V[S[i]] )↵
↵
#### Two properties to observe.↵
↵
We need to make two observations. ↵
- First, if we run the non-custom swap of a turn, then we can update in $O(1)$ the F array of final positions of items. If the turn moves $S[a]$ and $S[b]$ then we swap $F[a]$ with $F[b]$ and the $F$ array will be updated correctly. Proof: The only affected places A,B will swap its values, and a same value always will point to the same final place in F if we only run non-custom moves.↵
- Second, if we run a **custom swap**, then there is **no need of updating F array**. Because although that place **changed its value**, the new value of that place will end in the same place as the last value that was there was going to end.↵
↵
#### First Approach↵
So, if the last two properties are correct, then we can make an algorithm to at least get the array sorted (although it won't get the lower amount of turns). It will work on $O(N+M)$↵
↵
Note that a sorted final array must be $[0,1,2, ... , N-1]$. This means we know where each value should end. (the final index is equal to its value, i will call it $Q$)↵
We make all the steps of first procedure. And now, We will **iterate** all M turns.↵
In each turn I:↵
↵
- We will run the non-custom swap, and **update the F array**↵
- We will make a **custom swap**.↵
↵
As in each turn we know where each item will end (F), then we know how to strategically swap a value to be on the right position! So if a spot $i$ has $F[i] = y$ and $S[a] = y$ and we swap then, then we know that the $y$ value is not swapped (by a custom swap) anymore then we're guaranteed it will end in the right place. **In other words**, We know that the place where an item will end will need to have as value that index, the place where that item will end. (There is a possibility also that we don't need to make any swap because the value is already in its correct place, if this happens, we will skip that swap, and continue in that place with the next needed value. In the case there are no more values to correct, we will just swap (0,0) and wait **until the M turns have passed** )↵
↵
How to do detect the correct swap in $O(1)$, leading to an $O(M)$ algorithm? We need to maintain besides all other arrays, one more array E such that $E[x]$ has where the x value is on S. This array needs to first be computed in $O(N)$ and then each time we make a swap (custom or non-custom) we will need to **update E** in $O(1)$.↵
↵
↵
This algorithm has a total **complexity** of $O(N+M)$, because there are multiple steps all of either $O(N)$ or $O(M)$.↵
↵
But we are not guaranteed that the number of steps will be **minimized**, because we are thinking of getting the array sorted when $M$ turns have gone though, not before. However, with this solution we'll get the first three sub tasks.↵
We'll first to solve the problem without trying to get the lower amount of turns. This solution (that is pretty) hard, will then make us solve the harder sub-task with a simple binary search with no modifications of the algorithm.↵
↵
This solution points to **make the array to be sorted** when $M$ **turns** have passed. Not **after**, not **before**. ↵
↵
Note that the sorted array must be $[0,1,2, ... N-1]$, or, in other words $\forall i : 0 \leq i < n-1 \to S[i]=i$.↵
We need all $S[i]$ to be equal to its index.↵
↵
We know that we make the array sorted when M turns passed. This **must happen**. So, we can predict **how items will move until the M turns have passed**. We can answer for each item i, where its **value will be when all M moves have passed**. Also we can answer "where the item **i** in the final sequence **is** in the **actual sequence**" if we don't make more additional moves of course. ↵
We know that the item **i** in the final sequence must be equal to i! And we know where this item in the final sequence is in the current sequence. So we'll only need to swap (in the first turn), the sequence with value **i** to the place that will go to the index **i** in the final sequence. ↵
↵
We'll need to repeat this process in each of the M turns. And in each turn we'll update two arrays ↵
1. F = "where the item **i** in the final sequence **is** in the **actual sequence**↵
2. E = "where is the item with value **i** in the actual sequence"↵
↵
This way we will in each turn swap $E[i]$ with $F[i]$, this means, "the place where i value is" to "the place that will be in the final array in i". Of course in the case $E[i]!=F[i]$, otherwise we increase i and try to swap the next one. ↵
↵
****↵
#### The final approach: Binary Search↵
↵
We will need to consider trying to solve the problem "If there only were $W\leqslantM$ turns". We the algorithm of above with can answer to solve the answer "Can we solve the problem on $W$ turns?". So with a **binary search** we will test to get the lower $W$ that makes it possible to solve the problem.↵
That will be the answer with a total algorithm complexity of $O(log(M)*(M+N))$.↵
↵
↵
#### Conclusion↵
This is an extremely hard task, Although no special algorithm is needed, you need some observations and to not get lost while thinking things because there is a good amount of **deep thinking** needed. Good Luck. ↵
↵
Code: [Coming soon]
↵
#### Statement↵
If we **resume**, then it says: "We've got an **array $S$ of length $N$** (with **distinct** values) and two arrays **$Jx$ , $Jy$ of length $M$** (all arrays filled with values **from 0 to N-1**). Then the game starts and it consist of **M turns**, each turn $i$ goes this way:↵
↵
- A: We **swap** $S[ Jx[i] ]$ with $S[ Jy[i] ]$ (Jx[i] **can be equal** to Jy[i])↵
- B: Then we're allowed to do **any swap** (we can swap a value with **itself**). I will call this **custom moves**↵
↵
↵
The objective of the game is to make the **array $S$ sorted** with the **lower amount of turns**. We're **guaranteed** that there is a solution with an amount of turns **lower or equal than $M$**.↵
↵
**Limits:**↵
↵
- $N \leqslant 200000$↵
- $M \leqslant 600000$↵
- $M = 3N$, so $M>N$↵
↵
#### First Procedure↵
We'll define a new **array** $F$ of length $N$. Each $F[a]$ will be filled with "Where S[a] value will be at end if we don't run any **custom swaps** on that place". We can build this array in $O( N+M )$. How? In three steps. ↵
↵
↵
↵
- The first of $O(M)$:↵
We make a copy P of array S, and make all the M steps on P so we've got the final array with no extra **custom moves**.↵
- The second of $O(N)$:↵
Now we make another array V of length N. $V[b]$ Will store where the number b value is stored at the end.↵
- And the third also of $O(N)$:↵
We'll set F[i] to the position stored in V of S[i] value. ( F[i] = V[S[i]] )↵
↵
#### Two properties to observe.↵
↵
We need to make two observations. ↵
- First, if we run the non-custom swap of a turn, then we can update in $O(1)$ the F array of final positions of items. If the turn moves $S[a]$ and $S[b]$ then we swap $F[a]$ with $F[b]$ and the $F$ array will be updated correctly. Proof: The only affected places A,B will swap its values, and a same value always will point to the same final place in F if we only run non-custom moves.↵
- Second, if we run a **custom swap**, then there is **no need of updating F array**. Because although that place **changed its value**, the new value of that place will end in the same place as the last value that was there was going to end.↵
↵
#### First Approach↵
So, if the last two properties are correct, then we can make an algorithm to at least get the array sorted (although it won't get the lower amount of turns). It will work on $O(N+M)$↵
↵
Note that a sorted final array must be $[0,1,2, ... , N-1]$. This means we know where each value should end. (the final index is equal to its value, i will call it $Q$)↵
We make all the steps of first procedure. And now, We will **iterate** all M turns.↵
In each turn I:↵
↵
- We will run the non-custom swap, and **update the F array**↵
- We will make a **custom swap**.↵
↵
As in each turn we know where each item will end (F), then we know how to strategically swap a value to be on the right position! So if a spot $i$ has $F[i] = y$ and $S[a] = y$ and we swap then, then we know that the $y$ value is not swapped (by a custom swap) anymore then we're guaranteed it will end in the right place. **In other words**, We know that the place where an item will end will need to have as value that index, the place where that item will end. (There is a possibility also that we don't need to make any swap because the value is already in its correct place, if this happens, we will skip that swap, and continue in that place with the next needed value. In the case there are no more values to correct, we will just swap (0,0) and wait **until the M turns have passed** )↵
↵
How to do detect the correct swap in $O(1)$, leading to an $O(M)$ algorithm? We need to maintain besides all other arrays, one more array E such that $E[x]$ has where the x value is on S. This array needs to first be computed in $O(N)$ and then each time we make a swap (custom or non-custom) we will need to **update E** in $O(1)$.↵
↵
↵
This algorithm has a total **complexity** of $O(N+M)$, because there are multiple steps all of either $O(N)$ or $O(M)$.↵
↵
But we are not guaranteed that the number of steps will be **minimized**, because we are thinking of getting the array sorted when $M$ turns have gone though, not before. However, with this solution we'll get the first three sub tasks.↵
↵
This solution points to **make the array to be sorted** when $M$ **turns** have passed. Not **after**, not **before**. ↵
↵
Note that the sorted array must be $[0,1,2, ... N-1]$, or, in other words $\forall i : 0 \leq i < n-1 \to S[i]=i$.↵
We need all $S[i]$ to be equal to its index.↵
↵
We know that we make the array sorted when M turns passed. This **must happen**. So, we can predict **how items will move until the M turns have passed**. We can answer for each item i, where its **value will be when all M moves have passed**. Also we can answer "where the item **i** in the final sequence **is** in the **actual sequence**" if we don't make more additional moves of course. ↵
We know that the item **i** in the final sequence must be equal to i! And we know where this item in the final sequence is in the current sequence. So we'll only need to swap (in the first turn), the sequence with value **i** to the place that will go to the index **i** in the final sequence. ↵
↵
We'll need to repeat this process in each of the M turns. And in each turn we'll update two arrays ↵
1. F = "where the item **i** in the final sequence **is** in the **actual sequence**↵
2. E = "where is the item with value **i** in the actual sequence"↵
↵
This way we will in each turn swap $E[i]$ with $F[i]$, this means, "the place where i value is" to "the place that will be in the final array in i". Of course in the case $E[i]!=F[i]$, otherwise we increase i and try to swap the next one. ↵
↵
****↵
#### The final approach: Binary Search↵
↵
We will need to consider trying to solve the problem "If there only were $W\leqslantM$ turns". We the algorithm of above with can answer to solve the answer "Can we solve the problem on $W$ turns?". So with a **binary search** we will test to get the lower $W$ that makes it possible to solve the problem.↵
That will be the answer with a total algorithm complexity of $O(log(M)*(M+N))$.↵
↵
↵
#### Conclusion↵
This is an extremely hard task, Although no special algorithm is needed, you need some observations and to not get lost while thinking things because there is a good amount of **deep thinking** needed. Good Luck. ↵
↵
Code: [Coming soon]
