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 ≤ 200000
- M ≤ 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.
The final approach: Binary Search
We will need to consider trying to solve the problem "If there only were W ≤ M 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)).
