# Triple Sort Last Testcase failed

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

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