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!

# | User | Rating |
---|---|---|

1 | Benq | 3796 |

2 | tourist | 3722 |

3 | Radewoosh | 3719 |

4 | ecnerwala | 3578 |

5 | ksun48 | 3462 |

6 | Um_nik | 3456 |

7 | maroonrk | 3445 |

8 | jiangly | 3431 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 207 |

2 | awoo | 186 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 177 |

5 | Radewoosh | 177 |

7 | -is-this-fft- | 176 |

7 | maroonrk | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 170 |

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!

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/15/2021 22:20:32 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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??

Link