A run with exactly the vertical

A race course has to be homologated at an exact vertical drop. The piste map either holds a descent of that size or it does not.

The problem

A ski area is mapped as segments. One segment starts at the summit station. A segment either forks into two segments below it, forks into one, or ends at a lift station at the bottom. Each segment carries its own vertical drop in metres.

A descent starts at the summit segment and follows segments downhill until it reaches one that ends at a lift station. Its vertical is the sum of the drops of the segments on it. Half a descent is not a descent: a run that stops at a fork does not count, because the skier cannot get off there.

Say whether some descent has a vertical of exactly vertical metres.

Input. plan — the segments in level order from the summit, None where a segment does not fork that way. vertical — the metres wanted.

Output. True if some descent totals exactly that, False otherwise.

Example.

plan = [60, 30, 90, 20, None, None, 40], vertical = 190   ->  True

The summit segment drops 60 and forks into 30 and 90. Segment 30 runs on into 20, which ends at a station; segment 90 runs on into 40, which also ends at one. The two descents are 60 + 30 + 20 = 110 and 60 + 90 + 40 = 190.

A second example, on the same map, which stops halfway:

plan = [60, 30, 90, 20, None, None, 40], vertical = 90   ->  False

60 + 30 is 90, but segment 30 is a fork, not a station. Only 110 and 190 are real descents.

Constraints.

• 0 <= number of segments <= 5 x 10^3
• 1 <= drop <= 10^3
• 1 <= vertical <= 10^6
• An empty map has no descent at all

Hints

Approach

Brute force

Walk the map collecting every summit-to-station descent as a list of drops, then add each list up. Every one of up to n / 2 descents copies a list up to h long, so a 5 x 10^3-segment map that leans can move on the order of 10^7 numbers to answer a yes-or-no question.

The insight

Carry the metres still owed down the map instead of carrying the route back up.

A sum does not care in what order it was accumulated, so everything above a segment can be summarised by one number: the vertical left to find. Subtract the segment's own drop from it, hand the result to both forks, and the question at a station is a single comparison against zero. Nothing is allocated, and the first descent that works ends the search — or stops at its first true branch.

The other half of the insight is where the comparison goes. A descent ends at a segment with no fork under it at all, which is not the same as running out of map on one side of a segment that has a fork on the other.

Algorithm

1. Build the segments; an empty map returns False.
2. Call descend(summit, vertical).
3. In descend(node, owed): an absent segment returns False.
4. Subtract node.drop from owed.
5. If the segment has no fork on either side, return owed == 0.
6. Otherwise return descend(left, owed) or descend(right, owed).

Complexity

Time O(n) — each segment is visited at most once, and the walk stops early when a descent matches. Space O(h) for the stack, up to 5 x 10^3 frames on a map that never forks.

Solution

"""A run with exactly the vertical — carry the remaining metres down, decide at a station."""

import sys
from collections import deque

sys.setrecursionlimit(20000)   # a piste that never forks is one frame per segment


class Piste:
    __slots__ = ("drop", "left", "right")

    def __init__(self, drop):
        self.drop = drop
        self.left = None
        self.right = None


def build(plan):
    """Level-order piste map from the summit, None where a piste does not fork that way."""
    if not plan or plan[0] is None:
        return None
    root = Piste(plan[0])
    queue = deque([root])
    i = 1
    while queue and i < len(plan):
        node = queue.popleft()
        if i < len(plan):
            drop = plan[i]
            i += 1
            if drop is not None:
                node.left = Piste(drop)
                queue.append(node.left)
        if i < len(plan):
            drop = plan[i]
            i += 1
            if drop is not None:
                node.right = Piste(drop)
                queue.append(node.right)
    return root


def solve(plan, vertical):
    root = build(plan)

    def descend(node, owed):
        """`owed` is the vertical still to be found below everything above `node`."""
        if node is None:
            return False               # a fork that is not there is not a run
        owed -= node.drop
        if node.left is None and node.right is None:
            return owed == 0           # a lift station: the run ends here or nowhere
        return descend(node.left, owed) or descend(node.right, owed)

    return descend(root, vertical)

TESTS = [
    (([60, 30, 90, 20, None, None, 40], 190), True),
    (([60, 30, 90, 20, None, None, 40], 120), False),
    (([60, 30, 90, 20, None, None, 40], 90), False),
    (([60, 30, 90, 20, None, None, 40], 110), True),
    (([60, 60, None], 60), False),
    (([60, 60, None], 120), True),
    (([50], 50), True),
    (([], 0), False),
]

Pitfalls

• Answering at the empty side of a one-fork segment, by writing if node is None: return owed == 0. On plan = [60, 60, None] with vertical = 60 the walk falls off the missing right fork with nothing owed and reports True, though the only descent drops 120.
• Returning True as soon as owed hits zero. That is the second example: it reports a 90-metre descent that ends at a fork nobody can ski off.
• Returning True for an empty map when vertical is 0. No segments means no descent, and a descent needs at least one segment.

Variants

• The best repeater run — a path that may turn once, so one number carried down is no longer enough.
• The bracket, first round first — the same map read across in rows instead of down in routes.