DYNAINV - Editorial

[xcwgf666]

Problem link : contest practice

Difficulty : Simple

Pre-requisites : Basic Math

Problem : Maintain the number of inversions in the permutation (modulo 2), while performing swap operations.

Explanation

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 a_i > a_j. 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 a_i and a_i+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 A_L and A_R (L < R). Say, we want to place A_R 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 A_L 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.

Related links

• 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.

Solutions : setter tester

[urdarinda]

so can we do it like if q= odd then output is 1 else output is 0?

[krish8764]

This is first accepted solution which give me 14 points http://www.codechef.com/viewsolution/4157564 and this is my second accepted solution which gives me 37 point http://www.codechef.com/viewsolution/4162711 . The only difference between both is of data type. First one contain all variable in long long and second one contain all variable in int. Can data type create that much impact on time limit ?

[urdarinda]

I exactly had the same solution as yours but I recieved WA ( int) however when I changed to 1 indexed loops I got 2 test cases correct. How is that possible? The solution was still on int

[yash_15]

No.
For the initial permutation, you have to find the value, which can be zero or one.

[yash_15]

To calculate the initial number of inversions, I used a simpler method :

for(i=1;i<=n;i++) // one-indexed array

if a[i] != i, then swap it with the value at position a[i] and repeat for this i, and increment the counter.

So, in every step we move closer to the sorted array, and I think that the complexity is n because in each iteration we set one element right.

[wiseboy]

@xcwgf666 : You have explained a single swap case and that too, in a sorted permutation. I was myself able to think of this during the contest, but when I went forward to generalising it for the case of a swap in a random permutation, I failed to do so. Will you please explain the case of transitions added (or subtracted) in a swap in a random permutation, and how it changes parity?

[yash_15]

@wiseboy and others :

Let the sequence be : a[1],a[2],a[3],…,a[n]. Let a[i] and a[j] are swapped.

Now for terms a[1],a[2],…a[i-1] and a[j+1],a[j+2],…a[n], the swap has no effect.

Now consider some element a[k] such that i < k < j.

WLOG we can put the values 1, 2 and 3 each for a[i], a[j], and a[k].

We shall not count the comparison between a[i] and a[j] for now.

Case 1 : 1 2 3 -> 3 2 1 : <,< => >,>

Case 2 : 1 3 2 -> 2 3 1 : <,> => <,>

Case 3 : 2 1 3 -> 3 1 2 : >,< => >,<

Case 4 : 2 3 1 -> 1 3 2 : <,> => <,>

Case 5 : 3 1 2 -> 2 1 3 : >,< => >,<

Case 6 : 3 2 1 -> 1 2 3 : >,> => <,<

(If you have understood the signs above) The observation is : Number of sign changes (of middle elements) for a swap is always even! In particular, if the number lies between the swapped elements then both signs change otherwise both signs remain same. In this problem, we only want sign changes % 2, which is clearly zero.

Now, this argument applies to all the elements between positions i and j. Means that the position of swapped numbers has no effect!

Now the swapped elements result in change in sign once.

Hence, the overall effect is 2k+1 sign changes, irrespective of the positions of the swapped elements, and there values too. I did not even take the input of those indices as there was only one test case per file!

[wiseboy]

@yash_15 : Terrific! An elegant explanation!

@xcwgf666: Please include this explanation in the editorial. It’s really helpful.

[unlimited700]

@krish8764 long long takes 64 bit while normal int takes 32 bit space in memory , so it is possible because in case of long long it has to process more bits than in int .

[vivekchahar28]

i also did merge sort but didnt get 37 points why???

[suryanit]

how it will work? plz explain

[midhul]

@suryanit He used that fact that any swap operation will simply alter the parity of the no. of inversions. We can write a simple O(n) procedure to count the number of swaps required to sort the given permutation of 1-N, and then use this number to easily determine the final parity. The main insight here is that the no of inversions depends solely on the final order of elements, and not on the swaps which are used to get there.

@yash_15 Thanks for sharing this method!

[shubham12]

@yash_15 sir how did you come up with such a fantastic solution, i could have never dreamt of thinking it on my own

[rach8]

@yash_15 How the overall effect is 2k+1 and not k+1 ?

[wiseboy]

@rach8 : as can be seen, in a random permutation, if we swap any 2 numbers, the number of inversions for any position between the two swapped places will change by either of -2( if the swap resulted in
a[i]< a[k]< a[j]), 0, or +2 accordingly.

now, this is the case for all the intermediate places k, i.e, i< k< j. Hence, the no. of inversion changes can be generalised as 2k.

but, there’s another inversion change to be taken into account, of i and j.
this would always result in:
-1 (if initially a[i]> a[j], then finally a[i]< a[j], destroying 1 inversion)

or +1 for the opposite case.

hence, total inversion changes after each swap are always of the form 2k+1.

[yash_15]

Oh, this k has no relation with the other k . This was used to say that the number of inversions is odd (formally).

[wiseboy]

@rach8 please refer to my answer.

[naman1g2_10]

Can someone please explain me in simple language what we have to do in this question. I am not able to solve it.

[aa1992]

for(i = 1; i <= n; i++) {
t = 0;
for(j = a[i]; j; j = j & (j - 1)) t += fwt[j];
for(j = a[i]; j <= n; j = (j | (j - 1)) + 1) ++fwt[j];
ret = (ret + i - t - 1) % 2; // All we need is just a parity of this number, so we take it modulo 2
}
can please anyone explain whats happenning in above code.what is the use of j& j-1 and j|j-1.thank you.The code is of dynamic inversion problem. http://www.codechef.com/problems/DYNAINV.It belongs to setter code