progress

~/problems / Advanced DP / Bitmask DP

Count Hamiltonian routes

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard ~35 min

There are n cities numbered 1..n and a list of one-way flights (a, b). Count the routes that start in city 1, end in city n, and visit every city exactly once. Return the count modulo 10**9 + 7.

Write count_routes(n: int, flights: list[tuple[int, int]]) -> int.

  • Flights are directed. The same flight may appear more than once; each copy counts as a different way to fly that leg, so it multiplies the number of routes.
  • Constraints: 2 <= n <= 16, up to a few thousand flights.
count_routes(4, [(1, 2), (2, 3), (3, 4), (1, 3), (3, 2), (2, 4)])
# 2: 1-2-3-4 and 1-3-2-4

count_routes(3, [(1, 2), (1, 2), (2, 3)])
# 2: the two copies of 1->2 give two different routes

count_routes(3, [(1, 3), (3, 2)])
# 0: every route must end at city 3

⭐ Bonus: enumerating paths one by one passes small cases; a speed test on a complete graph of 16 cities (billions of routes) earns a star at about O(2^n · n²).

Show hint

Two partial routes that have visited the same set of cities and stand at the same city can be finished in exactly the same ways, so count them together. City n may only be entered last.

Topic: Bitmask DP. dp[mask][last] over subsets (n <= ~20): TSP, assignment.

0:00
Ctrl ' run · Ctrl ↵ submit
esc