Check out my comment.
Can you add more comments in your code please. Like why you made a structure , what is the function dfs doing, is it an abbreviation for Depth First Search. I am a beginner and itâs still hard for me to comprehend the editorial and their solution.
1 Like
Thank You 
Can you please elaborate your approach.
Thankx in advance
I have commented for almost everything upto my knowledge except the DSU part.
You can read about DSU (Disjoint Set Union ) in
https://cp-algorithms.com/data_structures/disjoint_set_union.html
Sure , here is my submission : CodeChef: Practical coding for everyone
Just to save you some time, first i call the function âaddpairsâ to add ânew free swapsâ from the connected component.
Then I call the function âtransformâ , to enlarge the cycle (I used DSU) using only free swaps. And then for each cycle I used dp to calculate the answer.
Also, I think that the same elements will be in the enlarged cycle no matter how you enlarge it, but the order of this elements can be different and that could change your possibilities for the splitting process. At least in the way I implemented, I think this can return a wrong answer.
My code will fail in this case :
1
17 9
1 15 14 3 4 13 5 17 8 9 12 2 11 6 16 7 10
8 14
10 11
3 6
4 6
10 13
2 14
11 17
7 9
1 16
The correct answer is 9. And my code outputs 10 . Although, if I randomized the process of enlarging the cycle, it could get the correct answer (9) . Thatâs why I think that the order matters.
I think the way you have implemented addPairs, the function is not adding all the pairs, which are possible. you can use dfs or bfs to find all the connected nodes (through pairs) and then add all of them as pairs.
letâs chat over hangout and not spam this discuss thread.
my email id: ashok1113@gmail.com
can you provide your code link
CodeChef: Practical coding for everyone i need cases where my code fails.and want to know was my approach correct?
@harisisbatman Sir,sorry to disturb you but can you explain me the actions of âsplitting the cyclesâ,âfinding maximum number of disjoint cyclesâ, that you have done? I am not able to understand also how bitmask dp is helping usâŚ
I would be grateful if you can kindly help this beginnerâŚ
Thanks in advance
1 Like
Sir, can you explain in a bit detailed manner what is all this enlarging of cycles you are talking about?
sir can explain code by some comment
1 Like
@rajarshi_basu Sir,can you kindly explain why the setterâs solution is returning character in the get function()? and what is this char &ans in get function?And also why are we considering that total edges will be 18 max??Because n vertices can have nC2 edges here where every edge represents a possible swap and so maximum edges can be 18C2âŚ
Anyone else also kindly help me if you have any knowledge of the above questions?
Thanks in advance
- I inputted the robot_graph (Hope its is clear to you what I am doing with the input and how I have structured the indices of vases that the robot can swap into a graph).
- I did DFS on the robot_graph to set the representatives. By this, I mean finding the connected components. For example, if 1, 2 and 4 are connected then I will set rep[1] = rep[2] = rep[4] = 1. This helps me in identifying which vertex belongs to which connected component.
- I generated the new compressed graph where each vertex now represents a single connected component. You donât have to understand each and every line of my code, you should just know what I am doing. (As a matter of fact, I myself donât know how I am doing this step in my code. I will have to analyze it). But you should think about it yourself how you can do it.
- The most important part is detecting the maximum number of cycles. I donât actually know what bitmask dp means. And you donât need to know it either to understand my solution.
I have used repeated BFSs to do this task. I believe you can also do it with DFSs. The whole idea is to start the search from the source vertex until I find a cycle. Once I find a cycle. I delete this cycle from the graph and recursively calls the same function on the same graph to detect the rest of the cycles. It returns me how many more cycles I can have if I chose to delete that specific cycle at that specific time.
After that, I add that cycle back in my graph and I continue my BFS to detect any more cycles.
Iâll explain it again.
In my function, I take two parameters, the source, and the graph. In one function execution, I find all the cycles which start from the source and end at source in the given graph. Whenever I find any such cycle, I delete it, calls the function recursively for the remaining graph, I add it back again and keep my search running to look for any other cycles which are also starting from source and ending at the source.
On a side note, sir, please donât call me sir, I appreciate the gesture but it really feels awkward to me 
5 Likes
ok
@harisisbatman Itâs so kind of you to explain your approach on our request.I would like to know that
Why dont we just simply count total number of edges in the component (node) graph to get the total cost?
Took the same approach. And this exactly is what the bitmask dp is invariably doing but in a different way. The key is to find the maximum number of cycles. The approach is identifying all disjoint cycles of all sizes starting from shortest to the longest. But this still isnât enough to find the maximum because in order to do that we need to the choose right of cycles before the rest. In order to account this, we find number of cycles taking each node as starting source. This accounts for the need to choose the right cycle before the other cycles.
1 Like
This is because, if you try a few examples on paper, you will find that for every cycle of n edges, you only need to swap n-1 elements and not n. So, to minimize the no. of swaps, you must find the maximum number of cycles.
You can see this in this simplest example- suppose the given permutation is 2 1. In the graph for this permutation, you will have an edge from first node to the second and one from the second node to the first. So there are two edges, but you only need 1 swap to get in to the desired state because those two edges are actually forming a cycle.
I feel like the complexity of the authorâs bitmask solution is kind of dubious. Each cell of the dp has N transitions, which makes the complexity O(N^3 * 2^N). Of course in practice, most cells of the dp probably arenât visited which is why the solution passes under the time limit quite comfortably, but it feels kind of unsatisfying to not have proof initially.
Does anybody have some proof that say for instance, half the cells arenât visited? (in which case N^3 * 2^(N - 1) < 1e9, which gives us a lot more confidence that the solution will pass)