Can anyone please explain to me why my code fails at the last test case of Triple Sort problem from May Long. Any help would be appreciated. Thanks in advance.
Link to code :
https://www.codechef.com/viewsolution/33001929
The task is to minimize the number swaps so that it doesn’t exceed N/2 swaps.
try this test case
Answer should be 4 for all test cases
6
9 4
6 1 9 3 2 5 8 7 4
9 4
9 7 5 8 3 4 6 2 1
9 4
9 7 5 8 4 3 2 6 1
9 4
9 7 5 8 6 1 3 2 4
9 4
9 7 5 8 6 3 2 1 4
9 4
9 7 5 8 6 4 2 3 1
If you are getting -1 then you exceeding the n/2 steps.
2 Likes
Your solution is very big. I didn’t really look at what you are doing. But I can give you hints to check what’s could be wrong in your solution.
Compute the cycles in the permutation array. Let’s count of EvenLength Cycle is E and odd-length Cycle is O. Solution exists iff E is even. Minimum #operations required to sort the array is Sum of the floor (CycleLength/2) for each cycle. Printing the index is very easy as it is just printing the indices serially in Computed Cycles with few checks.
Hope it helps 
3 Likes
for me what was occuring was whenever in one operation we can place 2 element into right place we should do that first across the sequence and then try to sort 1 by 1 . and when i was not doing the first type of operation first the steps were increasing
can you give the answers for these test cases.please?
answers means indexes.
all these test cases outputs to 4 but still i get WA on the last test case, my output for all these test cases is
4
1 6 5
3 9 4
1 7 2
2 8 7
4
2 7 6
4 8 2
1 3 9
3 9 5
4
3 5 4
6 3 8
1 2 9
2 9 7
4
1 9 4
2 7 3
5 6 1
8 2 5
4
1 9 4
3 5 6
1 2 8
2 8 7
4
3 5 6
4 8 3
1 2 9
2 9 7
The problem with your solution is the same as one of my first solutions where i got 50,
it is that once see this fact, any odd sized cycle of size k can be sorted in floor(k/2) steps, i mean
(k-1/2) steps, and any cycle of size k, multiple of 4 can be sorted in k/2 steps,
else if the cycle size is a multiple of 2, but not 4, let 2 such cycles have size k1 and k2,
they can be sorted taken together in (k1+k2)/2 steps.
if there are odd number of such cycles in total, then cannot be sorted, so u output a -1,
so, overall, if u identify this it will make it easy,
Coming to coding part, u do the triple sort each time from i =0 till n-1,
but whenever u encounter, 2 elements in each others place ,i.e., cycle size 2, u need to skip them,
and after this loop is over, then u are left with only elements with 2 size cycles,
in ur code the problem is when the element of 2 size cycle are next to each other, hope you get this.just put a check for this and i think you will get an ac verdict. good luck.
1 Like
Can someone point out the error in my code
Solution link: CodeChef: Practical coding for everyone
It is giving WA on last two tasks only
Thanks in advance
thanks
yes , i was missing the case to handle cycles of length2 together seperately.
Thank u.
your solution exceeds the minimum steps required to sort.
First handle cycle of length 3 in one go.
then handle cycles of length 2 seperately.
in this way u will not use more than n/2 steps.
try the above testcases by @ibrijesh .
It worked for me.