0340MediumDynamic ProgrammingPrefix Sum

Settled Control Tapes

Tracked in this browser only

Trains the technique from

LeetCode 3129Find All Possible Stable Binary Arrays I

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 machine writes a control tape one cell at a time. Each cell ends up holding either the value 0 or the value 1, and the finished tape must hold exactly zero cells of value 0 and exactly one cells of value 1, so its length is always zero + one.

The reader that consumes the tape loses synchronisation if it ever passes a long stretch of identical cells. A tape is therefore called settled when every maximal block of equal neighbouring cells holds at most limit cells; equivalently, nowhere on the tape do limit + 1 consecutive cells carry the same value.

Two tapes are different when they differ in at least one position. Count the settled tapes and report that count as a remainder after division by 1000000007.

Examples

Example 1

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

Writing a tape as its run of cell values, the settled tapes are `0101` and `1010`. Every block in each one holds a single cell, which is within `limit = 1`.

Example 2

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

The seven settled tapes are `01011`, `01101`, `10011`, `10101`, `10110`, `11001` and `11010`. Each holds two `0` cells and three `1` cells, and no block in any of them is longer than two.

Example 3

Input: zero = 4, one = 3, limit = 7
Output: 35

`limit = 7` is at least the tape length, so no arrangement can violate the block rule and every ordering of four `0` cells and three `1` cells counts.

Constraints

1 <= zero <= 200
1 <= one <= 200
1 <= limit <= 200

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

Java

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

The intended approach

Time O(zero * one)Space O(zero * one) for the two tables

Tabulate two counts for every pair (i zero-cells used, j one-cells used): the number of settled tapes whose last cell is `0`, and the number whose last cell is `1`. Summing over the length of the final block turns into a sliding total, so each entry is the previous two entries minus the one entry that has just fallen out of the window of width `limit`. The row where a tape is made only of `0` cells (or only of `1` cells) is seeded directly from the block rule.

Pythonentry point: number_of_stable_arrays

MOD = 1000000007


def number_of_stable_arrays(zero, one, limit):
    # end0[i][j] counts settled tapes built from i zero-cells and j one-cells
    # whose last cell is 0; end1 is the mirror image.  Extending a tape by one
    # more 0 telescopes into a fixed-width difference, so each table entry is
    # filled in constant time.
    # Time O(zero * one).  Space O(zero * one) for the two tables.
    end0 = [[0] * (one + 1) for _ in range(zero + 1)]
    end1 = [[0] * (one + 1) for _ in range(zero + 1)]
    for i in range(1, zero + 1):
        end0[i][0] = 1 if i <= limit else 0
    for j in range(1, one + 1):
        end1[0][j] = 1 if j <= limit else 0
    for i in range(1, zero + 1):
        row_i = end0[i]
        row_im1 = end0[i - 1]
        prev1 = end1[i - 1]
        cut0 = end1[i - limit - 1] if i - limit - 1 >= 0 else None
        for j in range(1, one + 1):
            v = row_im1[j] + prev1[j]
            if cut0 is not None:
                v -= cut0[j]
            row_i[j] = v % MOD
            w = end1[i][j - 1] + end0[i][j - 1]
            if j - limit - 1 >= 0:
                w -= end0[i][j - limit - 1]
            end1[i][j] = w % MOD
    return (end0[zero][one] + end1[zero][one]) % MOD

The obvious version

Fill the tape position by position, keeping a dictionary of states (zeros placed, ones placed, value of the last cell, length of the block in progress) and refusing any step that would push the running block past `limit`. Sum the states that used up both quotas.

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_settled_tapes(zero, one, limit):
    MOD = 1000000007
    # Walk the tape cell by cell, carrying the length of the block in progress.
    layer = {}
    layer[(1, 0, 0, 1)] = 1
    layer[(0, 1, 1, 1)] = 1
    if zero == 0:
        del layer[(1, 0, 0, 1)]
    if one == 0:
        del layer[(0, 1, 1, 1)]
    for _ in range(zero + one - 1):
        nxt = {}
        for (zu, ou, last, run), cnt in layer.items():
            if zu < zero:
                r = run + 1 if last == 0 else 1
                if r <= limit:
                    key = (zu + 1, ou, 0, r)
                    nxt[key] = (nxt.get(key, 0) + cnt) % MOD
            if ou < one:
                r = run + 1 if last == 1 else 1
                if r <= limit:
                    key = (zu, ou + 1, 1, r)
                    nxt[key] = (nxt.get(key, 0) + cnt) % MOD
        layer = nxt
    total = 0
    for (zu, ou, last, run), cnt in layer.items():
        if zu == zero and ou == one:
            total = (total + cnt) % MOD
    return total

How this problem was checked

Reference solution executed against 10 test cases — 10 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