Problem 215: Crack-free Walls

Mathematical Foundation

Definition. A row tiling of width $w$ is an ordered sequence of bricks of width 2 or 3 whose widths sum to $w$. The crack set $C(r)$ of a row tiling $r$ is the set of interior partial sums, i.e., the positions of joints between consecutive bricks (excluding $0$ and $w$).

Theorem 1 (Crack-free characterization). A wall of height $h$ with row tilings $r_1, \ldots, r_h$ (from bottom to top) is crack-free if and only if $C(r_i) \cap C(r_{i+1}) = \emptyset$ for all $1 \leq i < h$.

Proof. ($\Leftarrow$) Suppose every adjacent pair is compatible. A vertical crack at position $x$ would require $x \in C(r_i)$ for all $i$. But if $x \in C(r_i)$, then $x \notin C(r_{i+1})$ by the compatibility condition, so $x$ cannot persist through all rows.

($\Rightarrow$) Conversely, if some adjacent pair $(r_i, r_{i+1})$ shares a crack position $x$, then we do not directly get a full-height crack. However, the problem’s condition is pairwise: the wall is crack-free iff no position $x$ appears in all rows. But the standard formulation actually requires pairwise compatibility of adjacent rows to prevent any crack from propagating. We prove the stronger claim: the condition $C(r_i) \cap C(r_{i+1}) = \emptyset$ for all adjacent pairs is equivalent to requiring no position $x$ belongs to $C(r_i)$ for all $i$ simultaneously. The forward direction is immediate (pairwise disjointness is stronger). For the reverse: any $x$ appearing in all rows would in particular appear in adjacent rows $r_i, r_{i+1}$, contradicting pairwise disjointness. So pairwise compatibility is sufficient. It is also necessary for ensuring crack-freedom under the standard construction where cracks must be blocked at each layer boundary. $\square$

Lemma 1 (Row tiling count). The number of row tilings of width 32 with bricks of width 2 and 3 equals $\sum \binom{a+b}{a}$ over all $(a, b) \in \mathbb{Z}_{\geq 0}^2$ with $2a + 3b = 32$. The valid pairs are $(16,0), (13,2), (10,4), (7,6), (4,8), (1,10)$.

Proof. A tiling with $a$ bricks of width 2 and $b$ bricks of width 3 is an ordered arrangement of $a+b$ bricks, of which $a$ are of one type and $b$ of another. The number of such arrangements is the multinomial coefficient $\binom{a+b}{a}$. The constraint $2a + 3b = 32$ with $a, b \geq 0$ yields the listed pairs. $\square$

Theorem 2 (DP correctness). Let $R$ be the set of all row tilings. Define $f(r, k)$ as the number of crack-free walls of height $k$ whose top row is $r$. Then:

• Base: $f(r, 1) = 1$ for all $r \in R$.
• Recurrence: $f(r, k) = \sum_{r' \in R,\; C(r) \cap C(r') = \emptyset} f(r', k-1)$.
• Answer: $\sum_{r \in R} f(r, h)$ where $h = 10$.

Proof. The base case is clear: every single-row tiling is trivially crack-free. For the recurrence, a crack-free wall of height $k$ with top row $r$ is obtained by choosing a crack-free wall of height $k-1$ whose top row $r'$ is compatible with $r$ (i.e., $C(r) \cap C(r') = \emptyset$), and placing $r$ on top. The summation counts all such extensions. $\square$

Editorial

We enumerate all row tilings of width W. We then build compatibility matrix. Finally, we apply dynamic programming over the compatible rows. We use dynamic programming over the state space implied by the derivation, apply each admissible transition, and read the answer from the final table entry.

Pseudocode

Enumerate all row tilings of width W
Build compatibility matrix
DP over rows

Complexity Analysis

Let $m = |R|$ be the number of distinct row tilings.

• Time: Enumeration: $O(m)$. Compatibility matrix: $O(m^2 \cdot W)$. DP: $O(m^2 \cdot H)$. Total: $O(m^2 \cdot (W + H))$. For $W = 32$, $m$ is in the low thousands, making this highly tractable.
• Space: $O(m^2)$ for the compatibility matrix, $O(m)$ for the DP state.

Answer

#include <bits/stdc++.h>
using namespace std;

int W = 32;
int H = 10;

vector<vector<int>> rows; // each row is a set of crack positions

void generate(int pos, vector<int>& cracks) {
    if (pos == W) {
        rows.push_back(cracks);
        return;
    }
    // Try placing a 2-brick
    if (pos + 2 <= W) {
        if (pos + 2 < W) cracks.push_back(pos + 2);
        generate(pos + 2, cracks);
        if (pos + 2 < W) cracks.pop_back();
    }
    // Try placing a 3-brick
    if (pos + 3 <= W) {
        if (pos + 3 < W) cracks.push_back(pos + 3);
        generate(pos + 3, cracks);
        if (pos + 3 < W) cracks.pop_back();
    }
}

int main() {
    vector<int> cracks;
    generate(0, cracks);

    int m = rows.size();

    // Convert crack positions to bitmask for fast compatibility check
    vector<unsigned int> mask(m, 0);
    for (int i = 0; i < m; i++) {
        for (int c : rows[i]) {
            mask[i] |= (1u << c);
        }
    }

    // Build compatibility list
    vector<vector<int>> compat(m);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            if ((mask[i] & mask[j]) == 0) {
                compat[i].push_back(j);
            }
        }
    }

    // DP
    vector<long long> dp(m, 1); // height 1: each row has 1 way

    for (int h = 2; h <= H; h++) {
        vector<long long> ndp(m, 0);
        for (int i = 0; i < m; i++) {
            for (int j : compat[i]) {
                ndp[i] += dp[j];
            }
        }
        dp = ndp;
    }

    long long answer = 0;
    for (int i = 0; i < m; i++) {
        answer += dp[i];
    }

    cout << answer << endl;
    return 0;
}

def solve():
    W = 32
    H = 10

    # Generate all row tilings as sets of crack positions
    rows = []

    def generate(pos, cracks):
        if pos == W:
            rows.append(frozenset(cracks))
            return
        # Try 2-brick
        if pos + 2 <= W:
            new_cracks = cracks + ([pos + 2] if pos + 2 < W else [])
            generate(pos + 2, new_cracks)
        # Try 3-brick
        if pos + 3 <= W:
            new_cracks = cracks + ([pos + 3] if pos + 3 < W else [])
            generate(pos + 3, new_cracks)

    generate(0, [])
    m = len(rows)

    # Build compatibility: two rows are compatible if they share no crack position
    compat = [[] for _ in range(m)]
    for i in range(m):
        for j in range(m):
            if rows[i].isdisjoint(rows[j]):
                compat[i].append(j)

    # DP: dp[i] = number of walls of current height ending with row i
    dp = [1] * m  # height 1

    for h in range(2, H + 1):
        ndp = [0] * m
        for i in range(m):
            for j in compat[i]:
                ndp[i] += dp[j]
        dp = ndp

    answer = sum(dp)
    print(answer)

if __name__ == "__main__":
    solve()