Fillomino solutions -- are you crazy?!

While the previous two problems are relatively simple, this one is very difficult compared to them. No more brute force; there are $100$ cells, and each cell can hold a number as high as $100$ , so testing $100^{100}$ possibilities is awful.

The trick is that the rectangle has width $1$ . Thus, all the polyominoes generated will also be rectangles of width $1$ . This allows a very nice solution with dynamic programming.

The first idea would most likely be "generalize the problem, to $1 \times n$ , and make a recurrence by considering the last polyomino"; this is similar to a common problem:

A $1 \times n$ rectangle is to be tiled with $1 \times 1$ square tiles and $1 \times 2$ rectangle tiles. How many ways are there to do this?

The attempt might be this: with the original $1 \times n$ rectangle $R$ , remove a $1 \times k$ polyomino $P$ to leave a $1 \times (n-k)$ rectangle $R'$ . Find the number of ways to complete $R'$ , and add up for all possible choices of $k$ . However, the problem is that the last polyomino of $R'$ cannot be $1 \times k$ as well, since it would be adjacent to $P$ .

The fix is simple: we consider both $n$ and the size of the last polyomino. Let $a_{n,k}$ be the number of Fillomino solutions on $1 \times n$ , where the last polyomino (the rightmost) is $1 \times k$ . For example, $a_{2,1} = 0$ (it's impossible to fill a $1 \times 2$ rectangle having a $1 \times 1$ polyomino, since the rest is again a $1 \times 1$ polyomino, but then both have size 1 and are adjacent), but $a_{2,2} = 1$ (just fill the whole thing with a 2-mino).

Thus, we have the simple recurrence relation:

$a_{n,k} = \begin{cases} 1 &\text{if } n = k \\ 0 &\text{if } n < k \\ (a_{n-k,1} + a_{n-k,2} + \ldots + a_{n-k,n-k}) - a_{n-k,k} &\text{if } n > k \end{cases}$

If the last polyomino is $1 \times n$ , then the whole rectangle is not divided at all: there's one such way. If the last polyomino is $1 \times k$ with $k > n$ , it's clearly impossible, since the rectangle won't fit. Otherwise, the number of ways is simply the number of ways to fill $1 \times (n-k)$ , with anything except $1 \times k$ as the last polyomino.

This gives an $O(n^3)$ solution (two-dimensional states contributes $O(n^2)$ , and computing the sum is $O(n)$ ). This still works, but there's a simple speed up: $a_{n-k,1} + a_{n-k,2} + \ldots + a_{n-k,n-k}$ is constant, so we can actually simply store it instead of computing it over and over. This makes all computations $O(1)$ , thus the running time is $O(n^2)$ , easily done even with slow languages (read: Python).

Finally, just program it:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def solve(tgt):
    a = [[0]]
    s = [0]
    for n in range(1, tgt+1):
        a.append([0]*(n+1))
        for k in range(1, n):
            if k*2 <= n:
                a[n][k] = s[n-k] - a[n-k][k]
            else:
                a[n][k] = s[n-k]
        a[n][n] = 1
        s.append(sum(a[n]))
    return s[tgt]

print(solve(100))

In the above, we didn't actually compute $a_{n,k} = 0$ for $n < k$ ; instead, we simply observe if $n-k < k$ , and use a different formula ( a[n][k] = s[n-k] compared to a[n][k] = s[n-k] - a[n-k][k] , corresponding to setting $a_{n-k,k} = 0$ ) if that's the case.

The printed answer is $\boxed{931329647583272532815226}$ .

My take on this problem

H = 100

V = [[] for i in range(H + 1)]

def f(h):
    global V

    if len(V[h]):
        return V[h]

    v = [0]

    for i in range(1, h):
        vv = list(f(h - i))

        if len(vv) > i:
            del vv[i]

        v.append(sum(vv))

    v.append(1)

    V[h] = v

    return v

print(sum(f(H)))