i also did merge sort but didnt get 37 points why???
@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.
2 Likes
Can someone please explain me in simple language what we have to do in this question. I am not able to solve it.
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. DYNAINV.It Problem - CodeChef belongs to setter code
how to solve the problem without modulo 2 in O(logn) per query ? i solved it in (NlogN + QrootNlogN) , is anything better possile ?
I think you can do it @rajat1603 . Instead of breaking upinto pieces try maintaining Fenwick trees starting at position i such that they span upto 2^j , then you can achieve something log N * log N I guess!!
Read Sparse Table on Topcoder , My idea is very similar to that , wherever we can break into square root pieces , we have a very high probability that we can do it like the sparse table!
https://www.codechef.com/viewsolution/7948758
This is my solution which gives WA. Can anyone identify the mistake?
Can somebody please tell what’s wrong with my answer , its showing WA in the last two tasks.I have used enhanced merge sort to count the number of inversions and used the fact that parity changes after every swap.
https://www.codechef.com/viewsolution/8959784
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
No.
For the initial permutation, you have to find the value, which can be zero or one.
@yash_15 : Terrific! An elegant explanation!
@xcwgf666: Please include this explanation in the editorial. It’s really helpful.
@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 .
how it will work? plz explain
@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!
@yash_15 sir how did you come up with such a fantastic solution, i could have never dreamt of thinking it on my own
Oh, this k has no relation with the other k . This was used to say that the number of inversions is odd (formally).
I actually already did O((N + Q)logn * log(max)) using segtree on trie or treap on trie but both gave TLE , idk why but O(NlogN + NrootNlogMax) worked faster.