| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 7 | cnnfls_csy | 3569 |
| 9 | ecnerwala | 3494 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | maomao90 | 160 |
| 3 | -is-this-fft- | 159 |
| 4 | atcoder_official | 158 |
| 4 | awoo | 158 |
| 4 | cry | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 151 |
| 9 | maroonrk | 151 |
can anyone please provide me with a hint to solve this problem
basically we need to find all the cliques in the graph but in short time.
Update : I tried Bron-Kerbosch algorithm but it takes exponential time and the time limit for the problem is 1 sec with maximum of 128 vertices.
https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm
it takes exponential time and in the problem the time limit is 1 sec with 128 vertices.
Except you're allowed to terminate the algorithm once you find 1000 cliques. I already got accepted on this problem with the above algorithm, believe me, it's fine. If you're getting TLE you're doing something wrong, my implementation runs in 0.08s on the Kattis servers.
EDIT: Additionally, you're not going to find subexponential algorithms for this problem, it's NP-Complete.
EDIT2: iirc, you do need to implement the advanced techniques mentioned on the wiki (pivoting and vertex ordering).