### IHateDynamicProgramming's blog

By IHateDynamicProgramming, history, 6 days ago,

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!

• +6

 » 6 days ago, # |   +11 Considering your name, it's probably solved with Dynamic Programming.
•  » » 5 days ago, # ^ |   0 I don't think so :))
•  » » » 5 days ago, # ^ |   -13 hate with dp still an expert wow
•  » » » » 5 days ago, # ^ |   0 I always solve such problems that don't have to use dp
 » 5 days ago, # | ← Rev. 2 →   +3 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.
•  » » 5 days ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 days ago, # ^ |   0 I don't think so. Obstacles are rather irrelevant. You just skip transitions whenever there is an obstacle.
•  » » » » 5 days ago, # ^ |   0 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.
•  » » » » » 5 days ago, # ^ | ← Rev. 3 →   +6 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.
•  » » 5 days ago, # ^ | ← Rev. 2 →   0 Hmm, can you talk more about the solution using broken profile dp??
 » 5 days ago, # |   0