NerfThis's blog

[Help] Round 869 Div2 Problem D
By NerfThis, history, 12 months ago, In English

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.

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

→ Reply