state 25 of 32 · 6 min

Counting over digits and subsets

Two techniques for problems where brute force is astronomically large and the state space is small enough to enumerate.

Digit dynamic programming

"How many numbers between 1 and 10^18 have no two equal adjacent digits?"

Iterating is impossible. Build the number a digit at a time instead, and track only what matters:

python

from functools import lru_cache

def count(limit):
    digits = list(map(int, str(limit)))

    @lru_cache(maxsize=None)
    def go(pos, last, tight, started):
        if pos == len(digits):
            return 1 if started else 0
        total = 0
        top = digits[pos] if tight else 9
        for d in range(0, top + 1):
            if started and d == last:
                continue                          # the rule
            total += go(pos + 1, d,
                        tight and d == top,
                        started or d > 0)
        return total

    return go(0, -1, True, False)

Three pieces of state beyond the position:

tight: are we still on the prefix of the limit? Once a smaller digit is chosen, every later digit is free.

started: have we placed a non zero digit? Needed so leading zeroes are not treated as real digits.

last: whatever the specific rule needs to remember.

The state space is about 18 x 10 x 2 x 2, a few hundred, against 10^18 numbers.

Bitmask dynamic programming

A subset becomes an array index.

python

def tsp(dist, n):
    FULL = (1 << n) - 1
    best = [[float('inf')] * n for _ in range(1 << n)]
    best[1][0] = 0                                   # started at city 0

    for mask in range(1 << n):
        for i in range(n):
            if best[mask][i] == float('inf'): continue
            for j in range(n):
                if mask & (1 << j): continue         # already visited
                nxt = mask | (1 << j)
                cost = best[mask][i] + dist[i][j]
                if cost < best[nxt][j]:
                    best[nxt][j] = cost

    return min(best[FULL][i] + dist[i][0] for i in range(1, n))

The mask alone is insufficient: two routes covering the same cities can end somewhere different, and from those positions the cheapest completion differs. So the state is the pair.

The final line adds the trip home. Taking min(best[FULL]) without it optimises for finishing somewhere convenient, which is a standard wrong answer.

Reading the bound

The input size is the strongest hint about which applies:

Bound	Technique
numbers up to 10^18	digit DP
n up to 20	bitmask, `2^n` states
n up to 15, with submask loops	`3^n`
n up to 5,000	quadratic

Seeing n <= 20 in a statement is close to being told to use a mask.