0834HardDynamic ProgrammingPrefix Sum

Steady Punch Card Layouts

Tracked in this browser only

Trains the technique from

LeetCode 3130Find All Possible Stable Binary Arrays II

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 punch card is a single row of cells. Every cell is either a blank or a mark. A card is steady when all three hold:

it carries exactly zero blanks;
it carries exactly one marks;
no run of limit + 1 cells in a row is all blanks or all marks.

Two cards are different when some position carries a different kind of cell. Return how many steady cards exist, taken modulo 1000000007.

Examples

Example 1

Input: zero = 1, one = 2, limit = 1
Output: 1

With a cap of one, no two neighbouring cells may match. Only the card reading mark, blank, mark satisfies that while carrying one blank and two marks.

Example 2

Input: zero = 2, one = 2, limit = 1
Output: 2

A cap of one forces the kinds to alternate, so the card either opens with a blank or opens with a mark, giving two steady cards.

Example 3

Input: zero = 3, one = 3, limit = 2
Output: 14

Cards such as blank, blank, mark, blank, mark, mark are steady, since no three cells in a row match. Counting every such card gives this many.

Constraints

1 <= zero <= 1000
1 <= one <= 1000
1 <= limit <= 1000

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 steady_layouts(zero: int, one: int, limit: int) -> int:

Java

public int steadyLayouts(int zero, int one, int limit)

The intended approach

Time O(zero * one * limit): each of the two entries per shape sums up to `limit` earlier entries.Space O(zero * one) for the table.

Read a card as alternating runs of blanks and marks, each run at most the cap long. Count cards by how many cells of each kind they use and by the kind their last run is made of. A card ending in blanks is built by taking any card of the same shape with fewer blanks that ends in marks, and appending a run of blanks up to the cap; the same argument gives the cards ending in marks. Filling the table in increasing order of cells used means every entry it needs is already settled, and the answer is the sum of the two entries for the full shape.

Pythonentry point: steady_layouts

def steady_layouts(zero, one, limit):
    MOD = 10 ** 9 + 7
    # settle[a][b][t] counts layouts using a blanks and b marks whose last run is
    # of type t, 0 for blanks and 1 for marks; runs never exceed the cap
    settle = [[[0, 0] for _ in range(one + 1)] for _ in range(zero + 1)]
    for a in range(zero + 1):
        for b in range(one + 1):
            if a == 0 and b == 0:
                continue
            if b == 0:
                settle[a][b][0] = 1 if a <= limit else 0
                continue
            if a == 0:
                settle[a][b][1] = 1 if b <= limit else 0
                continue
            # a layout ending in blanks: peel off its final run of blanks
            total = 0
            for run in range(1, min(limit, a) + 1):
                total += settle[a - run][b][1]
            settle[a][b][0] = total % MOD
            total = 0
            for run in range(1, min(limit, b) + 1):
                total += settle[a][b - run][0]
            settle[a][b][1] = total % MOD
    return (settle[zero][one][0] + settle[zero][one][1]) % MOD

The obvious version

Enumerate every way to choose which positions hold the blanks, then walk each row measuring its longest run of equal cells and keep the rows whose runs all fit the cap. Exponential, but it applies the definition literally.

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_steady_layouts(zero, one, limit):
    MOD = 10 ** 9 + 7
    import itertools
    count = 0
    total = zero + one
    for spots in itertools.combinations(range(total), zero):
        row = [1] * total
        for s in spots:
            row[s] = 0
        ok = True
        run = 1
        for i in range(1, total):
            if row[i] == row[i - 1]:
                run += 1
                if run > limit:
                    ok = False
                    break
            else:
                run = 1
        if ok and limit < 1:
            ok = False
        if ok:
            count += 1
    return count % MOD

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 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