Difficulty : Simple
Pre-requisites : Basic Math
Problem : Maintain the number of inversions in the permutation (modulo 2), while performing swap operations.
At first, let’s consider some partial solutions.
How to get 14 points
Here you can simulate the whole process. The constraints are designed in such a way that after every swap, you can calculate the number of inversions again by iterating through all the pairs (i, j), where i < j and checking that ai > aj. Then you can output the number of inversions after taking it modulo 2.
How to get 37 points
There are faster methods of calculating the number of inversions, for example O(N log N) algorithm using the merge sort. If you have the same idea as in the 14-point solution, but calculate the number of inversions faster, you can have O(QN log N) solution that will fit in the TL for the second subtask and will bring you additional 23 points.
Please note that all these solutions doesn’t use the fact that we’re required to output the answer modulo 2. But modulo makes the problem much simpler than without modulo version. Though, the version without modulo part can be solved within the same time and memory bounds (see related links) for the given constraints.
How to get 100 points
If you run your solution at the different own test cases, you will note that no matter which numbers we swap, the parity of the number of inversions will always change. This gives rise for the following solution:
- Read the permutation and calculate the number of inversions in it. This can be done in any known way, as it’s a standard problem. For example, you can use fenwick tree or merge sort. Writer’s solution uses fenwick tree. But this is even an overkill here, because you only need the number of inversions modulo 2. You can use the fact that the permutation 1 2 3 … N has 0 inversions and every swap operation changes the parity of the number of inversions.
- Then, read Q queries. No matter what pair of numbers we swap, the parity of the number of inversions in the permutation will change. So the answers will have zeroes and ones alternating.
But how to prove that the parity will always change?
Let’s call transposition a swap of two adjacent numbers in the permutation, namely, swap of ai and ai+1.
Let’s show that a single transposition always change the parity of the number of inversions. It’s easy to see that if the pair (i, i+1) makes an inversion, then after the transposition this pair will not make an inversion and vice versa.
Now consider a general case: when you swap AL and AR (L < R). Say, we want to place AR to the L-th place. We need R-L transpositions to do it.
After we do them, we obtain:
1 2 ... AR AL AL+1 ... AN
Here AL stands at the position L+1, so we need R-L-1 extra transpositions to put it to the R-th place. Then, we’ll get:
1 2 ... AR AL+1 ... AL AR+1 ... AN
But that is exactly what we wanted to obtain - this new permutation is obtained from the initial one by doing just a single swap. Now, let’s calculate the total number of transpositions done: (R-L)+(R-L-1). It’s equal to 2(R-L)-1 - this number is always odd. So the number of transpositions done in the swap is always odd, and knowing that every transposition changes the number of inversions we obtain that every swap changes the number of inversions as well.
- A problem at SPOJ where you can check your inversion-finding logic. It requires you nothing but calculate the number of inversions in the array.
- A version of this problem without the modulo part at SPOJ. There you need to use some cleverer logic about maintaining the number of inversions. Pay attention that the given array there is not a permutation, so the parity of the number of inversions will not necessary change after every swap there.