SORTVS - Editorial

editorial
, , ,
22

hi all,
My solution
fails on sub task 3 {test case 7 and 9 }
Can someone tell me what is the test case 7 and 9 of subtask 3,
or can review my code.
Thanks in advance.

1 Like
23

there will be a discussion tomorrow (by me) on Youtube Live Codechef channel as well as zoom. (I personally will be seeing the zoom chats so)

4 Likes
24

I also do the same and my code work, did you delete the path after traveling and check whether it already sorted or not?
https://www.codechef.com/viewsolution/32797596

25

Can anyone explain dp+bitmask part of the solution? Or provide some resources to understand it

Thanks in advance

@alei, @arthurfn, @smelskiy

5 Likes
26

I haven’t deleted, why it’s needed? We can use subpath if required later.

27

No man you can’t use subpart later as you are changing its position

28

I have commented what I understood from the Tester’s solution. Just posting here, so that it might be useful for someone. Also if there is anything wrong in my understanding, kindly please point out.

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

5 Likes
29

I have tried a polynomial N^2 algorithm and it worked. Here is my solution:
CodeChef: Practical coding for everyone.
But in the editorial, the proposed solution is exponential, so I wanted to know if my polynomial time solution is correct.
Basically, I tried a similar analogy from the M = 0 case. For each connected component, I tried to push the elements to its correct component in the best way possible based on similar intuition, which I couldn’t prove to ensure minimum swaps. But it worked.

@arthurfn
@smelskiy

2 Likes
30

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

Can someone check my solution. I made graph and then started shorting all cycles.

31

Please can you elaborate your greedy approach ?
I am not able to wrap up the editorial around my head very clearly.

2 Likes
32

Thank you, it makes sense now.

33

It doesn’t seem correct.

Try this case :
1
15 6
15 14 3 7 10 8 13 2 12 6 1 11 9 4 5
1 12
1 2
6 9
4 8
2 13
14 15

Based on setter’s code, it should give 10 as answer. Your code prints 11.

I think you just got lucky

34

The tester’s approach is not greedy. Its DP + Bitmask only.

35

I was able to solve this question in O(n+m) using DSU and DFS. Can anyone review my solution - CodeChef: Practical coding for everyone.
Maybe help me find some mistake in my approach

1 Like
36

I was able to solve this using greedy…
From each node i tried to find minimum size cycle and remove it and continue that thing…
It feels to be right (but it’s greedy) can there be any counter case for my code
https://www.codechef.com/viewsolution/32751065

Thanks

@arthurfn
@ rajarshi_basu
@ diegohdmgz

37

You can try making a code that creates random testcases and compare your solution with setter’s solution. That’s how i found the testcase in the comments above

1 Like
38

I also started enlarging the cycle by free swaps. Then I used dp with bitmask to split the cycles and check which of them gave me the minimum number of non-free swaps. It also got AC, but then I created some random testcases and compared my solution with the setter’s solution and it seems that this approach is wrong (or maybe I didn’t implemented it well). It appears that the solution also depends on how you enlarge the cycle. If you just enlarge it with the first free swaps you find, then I think there could be created a counterexample.

39

If we notice, in whatever order we merge cycles (enlarging), the final cycle is always the same. and one more thing, if any value can be swapped to correct position with free swaps, I do it before enlarging, so the enlarged cycle doesn’t have any free swaps between consecutive elements.
The split order can determine the outcome, so I am checking all the possible ways I can split the cycle using all the swaps with-in cycle. and then recursively calling it. Can you share your solution link, so I can go through it.
Thanks
Ashok

40

Here’s the case for you:
1
18 7
14 15 16 13 2 17 5 10 8 7 6 12 4 18 1 11 9 3
1 4
9 16
1 11
18 5
12 6
3 16
5 14
This case was generated by a friend. This will fail for a lot of greedy approaches.
Correct answer is 11 :slight_smile:.
I had the same approach earlier, removing cycles at each node greedily, but then I randomized it. So it mostly outputs correct now.
Can anyone let me know the probability of my submission failing? :grin:

41

I guess, you were lucky. Because your algorithm doesn’t guarantee the identification of maximum number of cycles. Untitled Diagram
Consider the above graph of families all with equal weights 1. Your algorithm would wrongly choose cycle 012 first which leads to a total count of 2. But in reality the maximum number of cycles is 3.

Counter example -

 1
 9 3
 5 4 6 7 9 8 2 3 1
 1 7
 2 8
 3 9