4

[Help] Round 869 Div2 Problem D

 1 year ago
source link: https://codeforces.com/blog/entry/115660
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

I am trying to solve 1818D - Fish Graph with the following idea.

  1. For each node V whose degree is >= 4, do BFS starting from V to find the shortest cycle that includes V.
  2. If such a cycle exists, get all the nodes in this cycle, then check if we can add 2 more extra edges from V to other 2 nodes that are not in this cycle.

My submission (with some comments) is : 204063133. However I am getting WA on test case 2: wrong answer edge (4, 8) was used twice (test case 137).

I am sure my logic is incorrect somewhere but couldn't figure it out. Any help is appreciated.

13 hours ago, # |

8 8 8 4 3 4 7 4 8 2 6 8 3 7 5 1 8 5 This is the 137 case. I think you are not actually finding the shortest cycle or maybe you are doing something wrong while backtracking(adding edges included in special graph) . Overall your logic is correct, we do need to find the shortest cycle from a particular node.

  • 12 hours ago, # ^ |

    It turns out that I made exactly the same mistake mentioned by wakaranai, which is demonstrated by the test case you provided. Thank you!

    PS: how did you find out the test case, out of curiosity?

12 hours ago, # |

← Rev. 2 →  

+12

I faced the exact same issue, with the exact same verdict.

Turns out, I was not considering the fact that if you run a bfs from a starting node and find a cycle, the starting node might not be part of that exact cycle (Imagine a bamboo connected to a cycle). To overcome this, simply check if a cycle can be formed from paths that start at different adjacent nodes of the starting node, and ignore all other cycles.

  • 12 hours ago, # ^ |

    Yeah, this is exactly the mistake I made :) After 15 attempts, I finally got it right, I learned something new today! Thank you!

6 hours ago, # |

Quick note: You can easily get the shortest cycle by using a parent array and DFS. When you find the starting node while running DFS, just simply store a reference to the last node you reached and then return.

This always work because if you first find the longest cycle, you'd return and then the DFS would find the next shortest one and update that reference. But if you find the shortest one first, you'll again return and the DFS would end. check my submission for more detail: 203943422

5 hours ago, # |

← Rev. 2 →  

0

I haven't actually ran your code so apologies if you thought of this but I'm basing this off of your algorithm.

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

A regular bfs traversal doesn't work cuz your cycle might include vertices that you should've used for the two extra vertices instead.

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK