Hello,
Given a grid N x M (N x M <= 100). Your task is to count how many Hamilton cycles in this graph. Are there any algorithms to solve this?
Thanks!
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 24.11.2024 15:00:47 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Considering your name, it's probably solved with Dynamic Programming.
I don't think so :))
hate with dp still an expert wow
I always solve such problems that don't have to use dp
Problem: https://acm.timus.ru/problem.aspx?space=1&num=1519&locale=en You can find solutions to this problem online. In China the approach is known as 'CDQ DP,' if I'm not mistaken (I'm not Chinese). If I remember correctly, the gist of the idea is to perform the broken profile dp with the profile representing a correct bracket sequence. Hashing is also used as you need more than two possibilities for cell state.
I think it's harder version of described problem. In original one there are no single word about obstacles. So it should be doable without broken profile dp. Anyway, thanks for sharing. I was in doubt if this harder version is solvable with same constraints.
I don't think so. Obstacles are rather irrelevant. You just skip transitions whenever there is an obstacle.
You probably didn't get my point. Your approach will work for both versions, but I'm sure that version without obstacles is possible to do with a simpler method. I will think about it in my free time.
Well, maybe. I just get my intuition from the usual broken profile DP applied to board tiling with 1x2 tiles. There is no better solution in realm of competitive programming than using broken profile DP, and this approach is the same if you had a board with obstacles. Note, there is a complex solution to this problem if you look here: https://acm.timus.ru/problem.aspx?space=1&num=1594. But I definitely think it is even harder to come up with a solution for the hamiltonian cycle.
Hmm, can you talk more about the solution using broken profile dp??