Как решить эту задачу? Заранее спасибо. https://codeforces.me/edu/course/2/lesson/8/4/practice/contest/290943/problem/D
Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 5 | atcoder_official | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.09.2024 16:58:46 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
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 you work with edges and use degrees to calculate, then u subtract pairs who are adjacent, that is u counted wrong pairs and you should search for 3 size cycles and subtract all members of that 3 size cycles. About complexity I don't know why it actually passed, the thing is only cycle checking is confusing, probably it can be easily done with dfs (linearly).
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.