idk I was writing answer since min. Took time in copying this from Statement and formatting

Please help me what is wrong in my code. It is showing wa in subtask 1 & 3. https://www.codechef.com/viewsolution/25021435

Can you explain this line,specially the lists values?

(PS:-Either I’m thinking in wrong way,Or I think this statement is wrong or mistyped)

Using sets to find inversions have a worst case time complexity of O(n^2). Prefer other methods as described by the editorialist.

During June Lunchtime, when I copied the MergeSort code first from GeeksforGeeks, I got 30 points just like you. But then I copied the MergeSort code from HackerEarth, and it gave AC. I guess the problem is same : I changed the MergeSort code in yours and it gave AC.

Link to AC submission of your code : https://www.codechef.com/viewsolution/25024426

Link to HackerEarth MergeSort code : https://www.hackerrank.com/challenges/ctci-merge-sort/editorial

When i implemented the editorialist’s solution I got 50 marks and the last subtask was getting TLE.

Link to the code: click here

Then i realised that an element ‘x’ can only be at positions x,x-d,x-2d,x-3d…1 or x+d,x+2d,…n if we wish to sort the permutation using swapping numbers whose difference is d.

After using this in the code I now get WA in my subtask 2 and 3. I know that am i going wrong somewhere but can’t figure it out. Any help is appreciated

Link to the code: click here

Edit:

Used coordinate compression on fenwick tree to get AC and removed a wrongly placed break statement from the second code.

It was problem of int and long long. Now got AC

take an example:

5 2

5 4 3 2 1

we will need 3 swap in the cycle [5,3,1]

first [5,1,3]

then [1,5,3]

then [1,3,5]

similarly in bigger cycles it might me much more than (sizeofcycle-1)

Can anyone help me, dont know why i’m getting TLE

solution: https://www.codechef.com/viewsolution/25026524

will you pls tell me your idea ??

Actually the idea behind your solution is exactly same as explained in the editorial. To implement the number of elements which are smaller than current element and placed after it in the array, you have used Order statistics, whereas a well known BIT based solution exists as well [which I think the editorials mentioned].

You have made three small mistakes in your code.

- Use long long to count total number of inversions. Integer may overflow in the following case:

Suppose you have n=200,000 and D=1

And you are given the array in descending order. In this case total no of inversions is n*(n-1)/2 which is 19999900000 which will cause integer overflow. - You have made a small mistake in implementation of merge sort merge function. Instead of using temp.push_back(a[i++]) in the while loops you have used temp[k++] = a[i++].
- You haven’t passed arrays by reference.(vectors needs to be explicitly passed by reference in c++)

Cheers

Check out this AC code:

https://www.codechef.com/viewsolution/25034109

Thanks a lot sir, it’s people like you that make this community great.

At least give him a like then

At least like his reply if he helped you.

That’s a beautiful comment.Together we learn, together we grow. Cheers

how do we claim that we are allowed to swap only the adjacent elements??

bro can you help me with my solution, I don’t know where it is getting wa. I tried via generating multiple testcases, and checking it with other people code, there is no differece. But on codechef it keep getting WA.

My solution.

Use long long int instead of int.