I've encountered a problem that wants to find any Hamiltonian cycle (it ends where it starts). The graph given has undirected edges (which is different than this problem from CSES), and the number of vertices are $$$4 * 10^3$$$. I've been doing some search online for a while now, but eventually none of the solution seems to be better than $$$O(2^n * n)$$$. Do you have any ideas? I'm glad if some (pseudo) codes are provided, if possible. Thank you.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 03:55:50 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
https://en.wikipedia.org/wiki/Hamiltonian_path
Chances are there's some special property of the graph in the problem that you mentioned that makes it solvable in polynomial time.
I hate to tell you this, but it seems that there is no special property mentioned in the problem statement, and I'm pretty certain about that.
do you have a link to this problem
I do, but it's entirely in Vietnamese, and you have to join the Graph Marathon (which is in fact just a problemset and not a "real" contest, perhaps DMOJ doesn't have such feature?), which I'm afraid will make it difficult.
This is the problem anyway. To view it, create an account, then go back to the home page and click on the Graph Marathon (which shows as currently running), join it, and click the link to the problem.
Disclaimer: It's possible that I've misunderstood something in the statement because I don't speak Vietnamese, I just copy pasted it into Google translate.
I have a feeling this task requires heuristics for the following reasons:
Doing some Googling, there are a number of heuristics for Hamiltonian cycles that exist. For example, this link claims that if the graph is dense enough, with all degrees at least $$$n / 2$$$, a cycle always exists and you can find one in $$$O(n^2)$$$ (the link talks about paths since that was the original question, but the proof mentions cycles). Also, since the problem doesn't provide instructions on what to do if there's no solution, you can deduce the test cases always guarantee at least one cycle exists, so the graphs are probably somewhat dense because author had to write a generator that generates valid test cases somehow, and that's much easier with dense graphs.
I think my hunch was right, I implemented the simple $$$O(n^2)$$$ heuristic I mentioned above (described in more detail on Wikipedia), which gets around 34/40 (results are not always consistent since I use seed based on clock time). With a bit more tweaking you can probably get it to 40/40.
https://ideone.com/rIeQ5B
I think this problem is a Hail Mary at this point. I have been tweaking the Warnsdorff's heuristic for a while but couldn't get more than 28 cases correct.
If you don't mind, you can send me the problem statement, because I'm Vietnamese too, anh I can read it