Burns and vents

A balloon pilot has a fixed card of manoeuvres and two ways to fly each. The demonstration counts only if the balloon finishes on the marked height.

The problem

The flight card lists manoeuvres in order, each with a strength in metres. Every manoeuvre is flown exactly once, one of two ways: a burn lifts the balloon by its strength, a vent drops it by the same amount. Nothing else changes the height.

The demonstration ends target metres above the starting height — below it, if target is negative. Count the plans finishing exactly there. Two plans differ when any manoeuvre is flown differently, and equal strengths are separate lines on the card, so swapping which is vented gives a different plan.

Input. strengths — a list of non-negative integers, the manoeuvres in card order. target — an integer, the required change in height.

Output. The number of plans ending exactly target metres from the start.

Example.

strengths = [2, 2, 4], target = 4   ->  2

Burn the 4 and one of the 2s, vent the other: 4 + 2 − 2 = 4. Either 2 can be the vented one, so there are two plans.

A second example, ruled out by parity alone:

strengths = [2, 4], target = 3   ->  0

Both strengths are even, so every plan ends on an even height — and parity says so before any search starts.

A third example, with a manoeuvre that moves nothing:

strengths = [0, 2, 3], target = 5   ->  2

The 2 and the 3 must both be burns. The 0 is still a line on the card, flown as a burn or a vent: two plans.

Constraints.

• 1 <= len(strengths) <= 200
• 0 <= strengths[i] <= 1000
• sum(strengths) <= 20000
• -20000 <= target <= 20000

Hints

Approach

Brute force

Try both ways of flying each manoeuvre: 2ⁿ plans. A card of forty runs to 10¹²; this card holds two hundred.

The insight

Burns and vents are not two choices but one: if the burns total p, the vents total total − p, so p − (total − p) = target pins p at (total + target)/2 and the question becomes a plain subset count.

The card total is fixed before any manoeuvre is assigned, which is what makes the substitution legal. It also settles two cases with no work: if total + target is odd, or half of it exceeds total, no split exists and the answer is 0. What remains is one number goal and a count of sub-collections adding to it, in which a zero-strength manoeuvre doubles the count by itself.

Algorithm

1. total = sum(strengths) and shifted = total + target.
2. If shifted is negative or odd, or shifted / 2 > total, return 0.
3. goal = shifted // 2. Make ways of length goal + 1, with ways[0] = 1.
4. For each strength m, walk reached from goal down to m, adding ways[reached - m] into ways[reached]; the answer is ways[goal].

Complexity

Time O(n · goal) — two hundred manoeuvres against at most twenty thousand heights, about 4 · 10⁶ additions. Space O(goal) — one row of counts, reused for every manoeuvre.

Solution

"""Burns and vents — count the plans that land on target, as a subset-sum count."""


def solve(strengths, target):
    total = sum(strengths)
    # burns add p and vents take away total - p, so p - (total - p) = target;
    # a target of the wrong parity, or out of reach, has no split at all
    shifted = total + target
    if shifted < 0 or shifted % 2 or shifted // 2 > total:
        return 0
    goal = shifted // 2

    ways = [0] * (goal + 1)
    ways[0] = 1
    for metres in strengths:
        # descending, so this action is never counted twice in one plan
        for reached in range(goal, metres - 1, -1):
            ways[reached] += ways[reached - metres]
    return ways[goal]

TESTS = [
    (([2, 2, 4], 4), 2),
    (([2, 4], 3), 0),
    (([0, 2, 3], 5), 2),
    (([2, 2, 4], -4), 2),
    (([0], 0), 2),
    (([5], 7), 0),
    (([3, 1, 1, 2], 5), 2),
    (([1, 1, 1, 1, 1, 1], 0), 20),
]

Pitfalls

• Skipping the guard. On [2, 4] with target 3, integer division quietly rounds 9 // 2 to 4 and reports the count for target 2 instead of 0; a target deeper than the card can drop makes total + target negative and builds a row of negative length.
• Walking the row upward. Ascending reached lets a manoeuvre be counted into a plan that already used it, so [2, 2, 4] at target 4 answers more than 2.
• Dropping zero-strength manoeuvres. Each moves nothing yet doubles the plan count: [0] at target 0 has two plans, not one.

Variants

• Blends off the blotter — counting again in one pass, with the whole state in a handful of counters.
• Knapsack — the lesson behind the descending row update that keeps each item to one use.