flamie's blog

Help me pls
By flamie, history, 4 years ago, translation, In English

How to solve this problem? https://mirror.codeforces.com/edu/course/2/lesson/8/4/practice/contest/290943/problem/D

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

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why can't u start bfs from each node and when u see distance > 2 u stop bfs?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because there may be a case where each vertex in the graph is connected to each other

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But have u tried? When everything is connected we have n * (n + 1) / 2 edges in total, but m is not that high.

      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Here is my solution which actually passed.

The idea is that you should look at edges and count pairs from both ends.

The only problem we should take care is that we counted pairs who are adjacent, but also 2 edges far away, we should take care of that.

To fix that, we search for all 3 size cycles, and subtract all members of that cycle from the answer and that's it.

Probably 3 size cycle searching can be done in linear time, idk how, I used easy method (can't tell the time complexity of it, probably it is linear as well or closer to linear or test cases are weak), which worked. See code for details.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This will take $$$O(n^2)$$$ if the input graph is a star with center being the node $$$\frac{n}{2}$$$. Half of the nodes will pass $$$j\leq i$$$ condition which will then have the other half elements pass $$$k\leq j$$$ condition ( $$$j$$$ being $$$\frac{n}{2}$$$ in this graph, almost all of the times)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Do you know how to find the number of 3 size cycles in linear time? I was not able to figure it out since I'm weak at graphs and just wrote brute force to verify my idea by getting TLE, but got AC.

      → Reply