Why Greddily Solving 1 length cycles then 2 length cycles then 3 length cycles and so on does not work with the help of DSU ? Please give me some motivation to go for dp not for greedy in this problem?
4 Likes
I have tried using shortest path algo to travel no. from current index to desired index.
i.e selection sort but swapping through a series of indices(shortest route). It passed only 1st subtask.
Can anyone explain why this approach is not enough.
Thank you…!
@arthurfn @smelskiy I have same query. Why will greedy won’t work ?
I have found all the connected components and then I find cycles of elements b/w different connected components. Size=2 cycle ,size=3 cycle and so on. I will swap elements when I find a cycle.
3 Likes
yes i have also find the connected components and done it but WA for last task
instead of using Bitmasks DP, I Formed two graphs, one for the ones connected by the robot and the other one for where the elements should be, like if an element is in family 1 and it needs to go to an element in family 2 (family refers to all the points connected by the first graph), so family one is connected to family 2 with a weight equal to how many elements need to go there.
afterward, I just removed all possible cycles in the graph.
Here’s my solution :
https://www.codechef.com/viewsolution/32972265
It was a great question really, awesome work, problem setters 
1 Like
WHAT IF U HAVE A NODE THAT MAKE 3 LENGTH CYCLE WITH MANY NODES NODES ,YOU SHOULD TAKE ONLY ONE OF THEM WHICH DEPENDS ON OTHER NODES ,SO WHEN WE WILL HAVE MULTIPLE EQUAL LENGTH CYCLES THEN IT WILL CREATE AN ISSUE
I see, thanks.
An amazing thing is that I used the Simulated Annealing algorithm and passed this problemlink
1 Like
I also used the connected component approach using graph for robot moves.
but instead of splitting the cycles, first I enlarged the cycle by free swaps between two cycles and then split it using any free swaps and checking which one gives minimum count.
solution
Loved solving this problem (and all the others as well).
The freakishly amazing moment was when I drew the highlighted graph and realized that I don’t just have to count the number of cycles but the maximum number of cycles.
Here’s a more clear graph.
There are two ways to select cycles in this graph, either you select 2 yellow cycles or you can select 3 green cycles. Our code must prefer the 3 green cycles over 2 yellow cycles.
14 Likes
Can anyone please review my code. I tried a lot but still wasn’t able to clear the subtask 3. TLE was the main problem for me.
Please review it: My Solution
It was an interesting problem though.
Thank you
I think the following input gives you a counterexample:
1
12 3
5 8 1 10 3 12 4 7 6 9 2 11
1 2
3 4
5 6
In the final directed graph, you’ll have a cyclical triangle, where each of the sides also belongs to cyclical square. If you greedily pick the triangle, then you’ll be left with a single cycle of size 9 (made of the 3 remaining sides of each square). However, the optimal solution is to pick the 3 squares instead.
1 Like
Looking for video tutorial for this problem. Anyone please?
3 Likes
This is one of the test case in TEST#9 Subtask 3:
1
17 6
3 9 16 5 14 2 13 8 1 11 7 6 15 10 4 12 17
8 9
8 17
3 13
5 7
6 17
11 16
This is a counter example of Greedy approach ( taking ascending order of cycle size like 2 , 3 , 4 , 5… , …18).
1 Like
Hi All,
Can you please let me know what should be the answer for the following test case?
1
16 8
3 1 5 7 12 15 4 2 8 11 14 16 13 6 10 9
2 13
3 14
3 6
12 16
11 16
2 7
10 13
5 14
according to my logic it is 9 but some successful submission shows 8.
Any help is appreciated
What’s wrong with my aproach ,
-
Get SCC using graph.( robot swaps that are connected ).
-
Now we keep what we have and what we want .
-
Now swap among the SCCs …cost = 0;
-
Now see if there is any among SCCs which is not at correct place but if placed at a pos’n which would correct it in one move…this is one optimal step. cost = 0;
5 now perform the greedy approach. cost++;
https://www.codechef.com/viewsolution/32797189
This gave me correct ans on the testcases I tested on.
According to my logic also the answer is 9…don’t know why. 
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