0441MediumTreeDepth-First SearchBinary TreeDP on Trees

Rounds of Unhooking a Light Rig

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 stage crew has rigged a hanging light frame. A single bar hangs from the roof beam, and every bar carries at most two bars below it, one on its left arm and one on its right arm. No bar is ever hung from two arms at once, so the frame branches downward and never joins back up. Each bar is stencilled with a load code, which is negative when the bar is counterweighted.

The frame reaches you as rig, which lists the bars one level at a time from the roof beam downward, left to right inside a level. Slot 0 holds the top bar. Reading the listing from the front, every bar takes the next two slots that no bar has taken yet: the first of the two belongs to its left arm and the second to its right arm. A slot holding null means that arm carries nothing, and an empty arm takes no slots of its own. null slots at the very end of the listing may be left out.

The frame comes down in rounds. In one round the crew unhooks every bar that has nothing at all hanging beneath it as the round begins; a bar that only becomes free part way through the round waits for the next round. Rounds continue until no bar is left.

Return one entry per round, in the order the rounds take place. Each entry lists the load codes unhooked in that round, ordered by the slot the bar occupies in rig.

Examples

Example 1

Input: rig = [10, 20, 30, 40, 50]
Output: [[30, 40, 50], [20], [10]]

Slots 2, 3 and 4 hold bars with empty arms, so those three come off first, in listing order. That leaves the bar in slot 1 free for the second round, and the top bar alone for the third.

Example 2

Input: rig = [4, 2, null, 9]
Output: [[9], [2], [4]]

The top bar has only a left arm, and so does the bar hanging from it, so one bar comes off in each of the three rounds.

Example 3

Input: rig = [5]
Output: [[5]]

The rig is a single bar with both arms empty, so one round clears it.

Example 4

Input: rig = [-100, 100, -100, null, null, 0, 7]
Output: [[100, 0, 7], [-100], [-100]]

In the first round the bars in slots 1, 5 and 6 have nothing beneath them and are unhooked in that order. The bar in slot 2 is then free for the second round, and the top bar for the third.

Constraints

The number of bars in the rig is in the range [1, 100].
-100 <= load code of a bar <= 100
rig[0] holds a bar.
Every slot in rig that is not null was taken by an arm of an earlier bar.

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 dismantle_rounds(rig: list[int | None]) -> list[list[int]]:

Java

public List<List<Integer>> dismantleRounds(Integer[] rig)

The intended approach

Time O(n) in the listing length: the decode, the bottom-up sweep and the bucketing each touch every slot a constant number of times.Space O(n) for the arm tables, the stack and the returned rounds.

Decode the listing once into a table of left and right slot numbers, then give every bar the length of the longest chain of bars hanging below it: zero when both arms are empty, otherwise one more than the larger of its arms. That number is exactly the round the bar comes off in. The values are settled bottom up by a stack that revisits a bar after both its arms, and a closing sweep over the slots in order drops each code into its round, which keeps every round in listing order without extra sorting.

Pythonentry point: dismantle_rounds

def dismantle_rounds(rig):
    # One pass over the listing hands every bar the slot numbers of the bars on
    # its two arms, honouring the rule that an empty arm takes no slots. A bar
    # comes off in the round given by the longest chain of bars hanging below it:
    # a bar with nothing beneath it goes in round 0, and any other bar goes one
    # round after the later of its two arms. Those values are worked out bottom
    # up from an explicit stack that visits a bar again after both its arms, so a
    # rig a hundred bars deep is safe. A final walk over the slots in order fills
    # the rounds, which keeps each round in listing order for free.
    # O(n) time and O(n) space in the listing length n.
    size = len(rig)
    if size == 0 or rig[0] is None:
        return []
    left = [-1] * size
    right = [-1] * size
    free = 1
    for idx in range(size):
        if rig[idx] is None:
            continue
        if free < size:
            if rig[free] is not None:
                left[idx] = free
            free += 1
        if free < size:
            if rig[free] is not None:
                right[idx] = free
            free += 1

    below = [0] * size
    stack = [(0, False)]
    while stack:
        idx, settled = stack.pop()
        if settled:
            deepest = -1
            if left[idx] >= 0 and below[left[idx]] > deepest:
                deepest = below[left[idx]]
            if right[idx] >= 0 and below[right[idx]] > deepest:
                deepest = below[right[idx]]
            below[idx] = deepest + 1
            continue
        stack.append((idx, True))
        if left[idx] >= 0:
            stack.append((left[idx], False))
        if right[idx] >= 0:
            stack.append((right[idx], False))

    rounds = [[] for _ in range(below[0] + 1)]
    for idx in range(size):
        if rig[idx] is None:
            continue
        rounds[below[idx]].append(rig[idx])
    return rounds

The obvious version

Keep a set of the bars still standing and act the dismantling out: each round scans the standing bars in slot order, notes every one whose arms hold nothing still standing, records that round, and only then removes them.

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_dismantle_rounds(rig):
    size = len(rig)
    if size == 0 or rig[0] is None:
        return []
    kids = {}
    free = 1
    for idx in range(size):
        if rig[idx] is None:
            continue
        kids[idx] = []
        for _ in range(2):
            if free < size:
                if rig[free] is not None:
                    kids[idx].append(free)
                free += 1
    standing = set(kids)
    answer = []
    while standing:
        taken = []
        for idx in sorted(standing):
            if all(child not in standing for child in kids[idx]):
                taken.append(idx)
        answer.append([rig[idx] for idx in taken])
        for idx in taken:
            standing.discard(idx)
    return answer

How this problem was checked

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