0430MediumDynamic Programming

Leading a Two-Pane Transom

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A glazier is re-leading a transom window that stands two panes tall and n panes wide, so the frame holds 2 * n panes arranged in two rows.

Two came shapes are on the bench, and the workshop has an unlimited supply of each:

a bar, which grips two panes sharing an edge: either two neighbours in the same row, or the two panes of a single column;
an elbow, which grips the three panes that remain when one pane is lifted out of a two-by-two square of panes.

Either shape may be rotated freely before it is laid down. Every pane of the frame must end up gripped by exactly one shape, and no shape may reach beyond the frame.

Count the ways to lead the whole transom. Two leadings differ when some pair of panes is gripped by one shape in the first and by two different shapes in the second. The tally climbs steeply with n, so return the remainder it leaves after division by 1000000007.

Examples

Example 1

Input: n = 2
Output: 2

Two leadings cover the four panes: an upright bar in each column, or a sideways bar along each row. Any elbow laid here leaves a single pane that nothing can grip.

Example 2

Input: n = 4
Output: 11

Eleven leadings cover the eight panes. One of them puts an upright bar in the leftmost column and a pair of locked elbows across the other columns.

Example 3

Input: n = 5
Output: 24

Twenty-four leadings cover the ten panes. One lays a sideways bar along each row of the two leftmost columns and locks two elbows into the rest.

Example 4

Input: n = 6
Output: 53

Fifty-three leadings cover the twelve panes, among them an upright bar in each of the first three columns with two locked elbows filling the rest.

Constraints

1 <= n <= 1000
The returned value is the tally reduced modulo 1000000007.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def num_tilings(n: int) -> int:

Java

public int numTilings(int n)

The intended approach

Time O(n): one pass of four constant-time updates per column.Space O(1): four running tallies, no table.

Walk the frame one column at a time and keep four running tallies, one per state of the column about to be entered: neither pane covered, only the upper pane covered, only the lower pane covered, both covered. Advancing a column spreads each tally onto the states the available shapes can produce, and the answer is the 'neither pane covered' tally once all `n` columns are behind us, since nothing may protrude past the frame. Four scalars replace any table, so the sweep is linear and needs no array.

Pythonentry point: num_tilings

def num_tilings(n):
    # Sweep the transom column by column. All a finished column can hand to the
    # column on its right is which of its two panes are already covered, so four
    # running counts -- neither pane, upper only, lower only, both -- carry every
    # partial covering. Each step spreads a count over the shapes that finish the
    # current column. O(n) time, O(1) space.
    MOD = 1000000007
    neither, upper, lower, both = 1, 0, 0, 0
    for _ in range(n):
        nxt_neither = (neither + both) % MOD
        nxt_upper = (neither + lower) % MOD
        nxt_lower = (neither + upper) % MOD
        nxt_both = (neither + upper + lower) % MOD
        neither, upper, lower, both = nxt_neither, nxt_upper, nxt_lower, nxt_both
    return neither

The obvious version

Enumerate every distinct placement of both shapes inside the frame as a set of panes, then recursively cover the first still-empty pane with each placement that contains it, undoing the choice on the way back out. Counting the completed covers directly is exponential but needs no reasoning about column states.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_num_tilings(n):
    MOD = 1000000007
    shapes = [
        [(0, 0), (0, 1)],
        [(0, 0), (1, 0)],
        [(0, 0), (0, 1), (1, 0)],
        [(0, 0), (0, 1), (1, 1)],
        [(0, 0), (1, 0), (1, 1)],
        [(0, 1), (1, 0), (1, 1)],
    ]
    placements = []
    seen = set()
    for row in range(2):
        for col in range(n):
            for shape in shapes:
                cells = [(row + dr, col + dc) for dr, dc in shape]
                if any(rr > 1 or cc >= n for rr, cc in cells):
                    continue
                key = frozenset(cells)
                if key in seen:
                    continue
                seen.add(key)
                placements.append(tuple(sorted(cells)))
    touching = {}
    for place in placements:
        for cell in place:
            touching.setdefault(cell, []).append(place)
    order = [(row, col) for col in range(n) for row in range(2)]
    filled = set()

    def walk():
        target = None
        for cell in order:
            if cell not in filled:
                target = cell
                break
        if target is None:
            return 1
        total = 0
        for place in touching.get(target, []):
            if any(cell in filled for cell in place):
                continue
            filled.update(place)
            total += walk()
            filled.difference_update(place)
        return total

    return walk() % MOD

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in