DPERM - EDITORIAL

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

1 Like

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 HackerEarth MergeSort code : https://www.hackerrank.com/challenges/ctci-merge-sort/editorial

3 Likes

When i implemented the editorialist’s solution I got 50 marks and the last subtask was getting TLE.
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

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

1 Like

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)

1 Like

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

1. 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.
2. 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++].
3. 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
2 Likes

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

2 Likes

At least give him a like then

2 Likes

At least like his reply if he helped you.

3 Likes

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

2 Likes

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.

1 Like