Gritting the pass

A grit box thrown open at one post salts the road on both sides of it. The crew wants to salt the whole pass and open as few boxes as they can.

The problem

The pass is measured in kilometres from post 0 at the summit gate to post n at the valley gate, and there is a grit box at every post. The box at post i has a throw of reach[i], so opening it salts the road from i - reach[i] to i + reach[i], clipped to the ends of the pass. A box with a throw of 0 is empty: it salts nothing, not even the post it stands on.

The pass is gritted when every metre between post 0 and post n is salted. Find the fewest boxes that manage it, or report that none do.

Input. n — the length of the pass in kilometres. reach — a list of n + 1 non-negative integers, the throw of the box at each post.

Output. The fewest boxes that salt the whole pass, or -1 if none can.

Example.

n = 7, reach = [0, 2, 1, 0, 3, 0, 1, 2]   ->  2

Box 1 salts 0 to 3 and box 4 salts 1 to 7; no single box spans the pass.

A second example, where the pass cannot be finished:

n = 6, reach = [1, 0, 0, 0, 0, 0, 1]   ->  -1

Box 0 salts 0 to 1 and box 6 salts 5 to 6; the five empty boxes between them salt nothing.

Constraints.

• 1 <= n <= 10^4
• len(reach) == n + 1
• 0 <= reach[i] <= 100

Hints

Approach

Brute force

Try every subset of boxes and check whether the union covers the pass: 2ⁿ⁺¹ subsets, a million already at 20 posts.

The insight

Once the road is salted up to kilometre c, the only box worth opening is the one reaching furthest right among those whose stretch starts at or before c.

A box starting after c leaves a bare strip, so it is never legal. Among the legal ones the largest right edge dominates: whatever a rival salts past c already lies inside the chosen box, so the swap loses no coverage and costs no box. The precondition — one unbroken salted stretch — holds because a gap is never skipped.

Algorithm

1. Fill best, an array of length n: for each post i with reach[i] > 0, raise best[max(0, i - reach[i])] to min(n, i + reach[i]).
2. Hold covered = 0 and a cursor that never moves backwards.
3. While covered < n, take the largest of best[0..covered].
4. If it equals covered, nothing crosses the gap: return -1.
5. Otherwise open a box, set covered to it, and repeat.

Complexity

Time O(n) — one pass to build best, and the cursor only advances, so the sweep amortises to one traversal. Space O(n) for best.

Solution

"""Gritting the pass — cover a segment with the fewest intervals, greedily."""


def furthest_from_each_start(n, reach):
    """best[l] = the furthest kilometre salted by any box whose stretch starts at l."""
    best = [0] * n
    for post, throw in enumerate(reach):
        if throw == 0:                    # an empty box salts no length of road
            continue
        left = max(0, post - throw)
        if left < n:
            best[left] = max(best[left], min(n, post + throw))
    return best


def solve(n, reach):
    best = furthest_from_each_start(n, reach)
    boxes = 0
    covered = 0
    cursor = 0                            # never moves back, so the sweep stays O(n)
    while covered < n:
        # invariant: [0, covered] is salted and is one unbroken stretch
        farthest = covered
        while cursor <= covered:
            farthest = max(farthest, best[cursor])
            cursor += 1
        if farthest == covered:           # no box's stretch crosses this metre
            return -1
        covered = farthest
        boxes += 1
    return boxes

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

Pitfalls

• Keying a box by its post instead of by where its stretch starts. The box at post 4 in the first example throws 3, so it starts salting at kilometre 1 and is legal that early. Keyed by post it stays invisible until kilometre 4, and the sweep reports -1.
• Forgetting to clip the left edge at zero. A negative i - reach[i] writes to the far end of best, so a summit box appears to help near the valley.
• Advancing covered when the furthest edge has not grown. That is the "no box crosses this metre" case, and it spins forever instead of returning -1.

Variants

• The single enlarger — the same intervals, keeping as many as fit instead of covering all of them.
• The exchange argument — why swapping a rival box out is a proof and not a hunch.