0281MediumDynamic ProgrammingTreeDepth-First SearchBinary TreeDP on Trees

Bonus Pool Without Direct Reports

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 firm's reporting lines form a binary chart: every person has at most two direct reports, one recorded on their left and one on their right.

The chart arrives as chart, a level-by-level listing. chart[0] is the chief. After that, every person already listed contributes two entries in turn, their left direct report then their right direct report, with null where that report does not exist. A null contributes nothing further, and null entries at the very end of the listing are left off. Each entry is the discretionary bonus recorded for that person, which is never negative.

The board will pay a selection of these bonuses in one round, under a single rule: if a person is paid, neither of their direct reports may be paid in that round.

Return the largest total the board can pay out.

Examples

Example 1

Input: chart = [0, 1, 7, 10]
Output: 17

Pay the person recorded as 7 and the person recorded as 10. Neither is a direct report of the other, and the two bonuses come to 17.

Example 2

Input: chart = [3, 4, 5]
Output: 9

The chief's two direct reports hold 4 and 5. Neither reports to the other, so both may be paid in the same round, for 9.

Example 3

Input: chart = [5]
Output: 5

The chief is the only person on the chart, and paying them comes to 5.

Constraints

The number of people in the chart is in the range [1, 10^4].
0 <= bonus <= 10^4

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

Java

public int bestBonusPool(Integer[] chart)

The intended approach

Time O(n)Space O(n)

Rebuild the chart as child index tables, then hold two figures for each person: the best their branch can pay when they are paid, and when they are not. Paying a person adds each direct report's not-paid figure; leaving a person out lets each report contribute whichever of its two figures is larger. The level-order listing lists a person before their reports, so walking that discovery order in reverse settles reports before the people above them, without recursion. The answer is the larger of the chief's two figures.

Pythonentry point: best_bonus_pool

def best_bonus_pool(chart):
    # Turn the listing into child index tables, then settle two figures per person:
    # the best total for their branch when they are paid, and when they are not.
    # Paying someone rules out both direct reports, so it adds each report's
    # not-paid figure; leaving someone out lets each report take whichever of its
    # two figures is larger.  Discovery order always lists a person before their
    # reports, so walking that order backwards settles every report first and no
    # recursion is needed even for a chart shaped as a 10000-person chain.
    # Time: O(n).  Space: O(n) for the child tables and the two figure tables.
    n = len(chart)
    left = [-1] * n
    right = [-1] * n
    order = [0]
    head = 0
    i = 1
    while head < len(order) and i < n:
        node = order[head]
        head += 1
        if i < n:
            if chart[i] is not None:
                left[node] = i
                order.append(i)
            i += 1
        if i < n:
            if chart[i] is not None:
                right[node] = i
                order.append(i)
            i += 1
    paid = [0] * n
    unpaid = [0] * n
    for k in range(len(order) - 1, -1, -1):
        node = order[k]
        take = chart[node]
        drop = 0
        for child in (left[node], right[node]):
            if child >= 0:
                take += unpaid[child]
                drop += paid[child] if paid[child] > unpaid[child] else unpaid[child]
        paid[node] = take
        unpaid[node] = drop
    return paid[0] if paid[0] > unpaid[0] else unpaid[0]

The obvious version

Enumerate every subset of the people with a bitmask, discard any subset holding both a person and one of their direct reports, and keep the largest surviving total.

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_best_bonus_pool(chart):
    n = len(chart)
    left = [-1] * n
    right = [-1] * n
    order = [0]
    head = 0
    i = 1
    while head < len(order) and i < n:
        node = order[head]
        head += 1
        if i < n:
            if chart[i] is not None:
                left[node] = i
                order.append(i)
            i += 1
        if i < n:
            if chart[i] is not None:
                right[node] = i
                order.append(i)
            i += 1
    slot = {}
    for k in range(len(order)):
        slot[order[k]] = k
    m = len(order)
    best = 0
    for mask in range(1 << m):
        total = 0
        ok = True
        for k in range(m):
            if not (mask >> k & 1):
                continue
            v = order[k]
            total += chart[v]
            for c in (left[v], right[v]):
                if c >= 0 and (mask >> slot[c] & 1):
                    ok = False
                    break
            if not ok:
                break
        if ok and total > best:
            best = total
    return best

How this problem was checked

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