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

# | User | Rating |
---|---|---|

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 202 |

2 | 1-gon | 201 |

3 | rng_58 | 194 |

4 | SecondThread | 193 |

5 | awoo | 187 |

6 | vovuh | 183 |

7 | Um_nik | 182 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 175 |

10 | -is-this-fft- | 171 |

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

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/17/2021 06:35:07 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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

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

but what if graph is a hedgehog

I didn't get what u said

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.

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)

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.