0720HardArrayBreadth-First SearchGraph Theory

Ration Packs From Nested Crates

Tracked in this browser only

Trains the technique from

LeetCode 1298Maximum Candies You Can Get from Boxes

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 relief depot holds n crates labelled 0 through n - 1. For crate i:

unlocked[i] is 1 when its clasp is already free and 0 when the clasp is sealed;
rations[i] is how many ration packs are inside it;
keycards[i] lists the labels of the crates whose clasps the keycards inside crate i will free;
nested[i] lists the labels of the crates packed inside crate i.

You arrive holding exactly the crates listed in startCrates. You may open a crate you are holding when its clasp is free, either because it started that way or because you have picked up a keycard for it. Opening a crate hands you all of its ration packs, all of its keycards and all of the crates packed inside it, and those crates are then in your hands too.

A keycard is never used up: once you hold the keycard for a crate, that crate's clasp counts as free from then on, including for a crate that has been sitting in your hands unopened. You may open crates in any order you like and you take nothing out of a crate you never open.

Return the largest number of ration packs you can end up with.

Examples

Example 1

Input: unlocked = [0, 1, 0], rations = [5, 2, 9], keycards = [[], [0], []], nested = [[], [], []], startCrates = [0, 1]
Output: 7

Crate 1 arrives with a free clasp, so opening it banks 2 packs and hands over a keycard for crate 0. Crate 0 is already in hand, and with its clasp now free it opens for 5 more packs. Crate 2 is never in hand, so its 9 packs stay in the depot.

Example 2

Input: unlocked = [1, 0, 1, 1], rations = [1, 2, 4, 8], keycards = [[], [], [], []], nested = [[1], [2], [3], []], startCrates = [0]
Output: 1

Crate 0 opens for 1 pack and yields crate 1, whose clasp is sealed and for which no keycard exists anywhere, so crate 1 is never opened and crates 2 and 3 packed below it are never in hand.

Example 3

Input: unlocked = [1], rations = [7], keycards = [[]], nested = [[]], startCrates = []
Output: 0

You arrive holding no crates at all, so there is nothing to open and no packs to collect.

Constraints

1 <= unlocked.length <= 1000
rations.length == unlocked.length
keycards.length == unlocked.length
nested.length == unlocked.length
0 <= unlocked[i] <= 1
1 <= rations[i] <= 1000
0 <= keycards[i].length <= 1000
0 <= keycards[i][j] <= 999
0 <= nested[i].length <= 1000
0 <= nested[i][j] <= 999
0 <= startCrates.length <= 1000
0 <= startCrates[i] <= 999
Every label listed in keycards[i], in nested[i] and in startCrates is a valid crate label, and no label is repeated inside any one of those lists.
No crate is packed inside more than one crate, and no crate is packed inside itself either directly or through a chain of crates.

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 max_rations(unlocked: list[int], rations: list[int], keycards: list[list[int]], nested: list[list[int]], startCrates: list[int]) -> int:

Java

public int maxRations(int[] unlocked, int[] rations, int[][] keycards, int[][] nested, int[] startCrates)

The intended approach

Time O(n + K + C) for n crates, K keycard entries and C nesting entries.Space O(n) for the three per-crate flags plus the piles.

Track three things as the visit proceeds: which crates are in hand, which clasps are free, and which crates have been opened. Crates in hand with a free clasp go on a ready pile; crates in hand with a sealed clasp go on a waiting shelf. Opening a crate off the ready pile banks its packs, marks each of its keycards' targets as free and moves any of those targets off the waiting shelf onto the ready pile, then puts the crates it contained on whichever of the two piles matches their clasp. Each crate joins the ready pile at most once per event that could free it, so the whole sweep is linear in the input, and the order crates are opened in cannot change the final total because nothing is ever given up.

Pythonentry point: max_rations

def max_rations(unlocked, rations, keycards, nested, startCrates):
    # Grow the set of crates in hand and the set of clasps that can be released.
    # A crate in hand whose clasp is still sealed goes on a waiting shelf; the
    # moment a keycard for it turns up it is moved onto the ready pile, so a
    # keycard found late still reaches a crate picked up early.
    # Time O(n + total keycards + total nesting entries).  Space O(n).
    n = len(rations)
    holding = [False] * n
    releasable = [unlocked[i] == 1 for i in range(n)]
    opened = [False] * n
    ready = []
    waiting = set()
    for crate in startCrates:
        if not holding[crate]:
            holding[crate] = True
            if releasable[crate]:
                ready.append(crate)
            else:
                waiting.add(crate)
    collected = 0
    while ready:
        crate = ready.pop()
        if opened[crate]:
            continue
        opened[crate] = True
        collected += rations[crate]
        for card in keycards[crate]:
            if not releasable[card]:
                releasable[card] = True
                if card in waiting:
                    waiting.discard(card)
                    ready.append(card)
        for inner in nested[crate]:
            if not holding[inner]:
                holding[inner] = True
                if releasable[inner]:
                    ready.append(inner)
                else:
                    waiting.add(inner)
    return collected

The obvious version

Keep a set of crates in hand and a set of freed clasps, then sweep every crate in hand over and over, opening whatever is openable and folding in its keycards and contents, until a full sweep changes nothing. Sum the packs of the crates that ended up open.

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_max_rations(unlocked, rations, keycards, nested, startCrates):
    n = len(rations)
    holding = set(startCrates)
    cards = set(i for i in range(n) if unlocked[i] == 1)
    opened = set()
    changed = True
    while changed:
        changed = False
        for crate in sorted(holding):
            if crate in opened or crate not in cards:
                continue
            opened.add(crate)
            changed = True
            for card in keycards[crate]:
                cards.add(card)
            for inner in nested[crate]:
                holding.add(inner)
    total = 0
    for crate in opened:
        total += rations[crate]
    return total

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