Height off the winch

A gliding club sets a cross-country task over squared ground. The wind decides which way the glider travels, so the only figure left is how high the winch has to put it.

The problem

The task map is a rectangle of squares, rows by cols. Each square carries the height the glider gains or loses crossing it: positive where a thermal lifts it, negative where the air sinks. The wind runs from the north-west, so from a square it can push on east or south and nowhere else.

The winch launches it over the north-west square and the task ends over the south-east one. Every square on the route is crossed, first and last, and the glider must read 1 metre or more after each; at zero it is on the ground.

Input. air — a list of rows, each a list of integers, the metres gained or lost over each square.

Output. The smallest whole launch height in metres that leaves some legal route to the south-east square with the glider never below 1 metre.

Example.

air = [[-30, -60,  40],
       [-20, -90, -10],
       [ 10,  30, -70]]   ->  81

Off the winch at 81 it runs south, south, east, east and reads 51, 31, 41, 71 and 1 over the five squares. At 80 it lands in the last one, and no route is kinder.

A second example, where the route that finishes highest is not the route to fly:

air = [[0, -180, 260],
       [-20, -20, -20]]   ->  61

The southern route sinks 20 metres a square and finishes on the metre. East into the 260 metre thermal finishes 240 metres higher, but the sink in front of it demands 181 off the winch.

Constraints.

• 1 <= rows, cols <= 200
• -1000 <= air[i][j] <= 1000

Hints

Approach

Brute force

Fly every route and take the deepest shortfall along each. The routes are the interleavings of the moves: 705432 on a 12 by 12 map, a 119-digit number at the bound.

The insight

Fill the table from the last square backwards: a square demands what the gentler of its two onward squares demands, less the height that square gives, floored at a metre.

Forward the state does not close: two arrivals at a square differ both in the height in hand and in the launch that bought it, and height now can cost more off the winch than it gives back later. Backwards one number per square is enough — the smallest height that survives from there on — and it reads only the squares east and south, settled already.

Algorithm

1. Let need[i][j] be the smallest height the glider may arrive over square (i, j) with, before that square is applied.
2. Sweep rows bottom up, and inside each row columns right to left.
3. Take min(east, south) — a neighbour off the map is unflyable, the exit past the south-east square asks 1.
4. Subtract air[i][j] and floor at 1.
5. need[0][0] is the launch height.

Complexity

Time O(rows · cols) — each square settled once from two neighbours, 40000 of them at the bound. Space O(cols) — one rolling row, swept right to left so the entry not yet overwritten is the square to the south.

Solution

"""Height off the winch — smallest launch that survives a one-way task grid."""


def solve(air):
    """Smallest launch height, in metres, that reaches the south-east square."""
    rows, cols = len(air), len(air[0])
    inf = float("inf")

    # need[j] is what the square below column j demands. The row under the map
    # is unflyable everywhere except past the exit, which asks for the one metre
    # the glider has to finish on.
    need = [inf] * (cols + 1)
    need[cols - 1] = 1

    for i in range(rows - 1, -1, -1):
        for j in range(cols - 1, -1, -1):
            # right to left, so need[j] is still the square to the south while
            # need[j + 1] is this row, to the east: the only two ways onward
            onward = min(need[j], need[j + 1])
            need[j] = max(1, onward - air[i][j])   # invariant: never below a metre
    return need[0]

TESTS = [
    (([[-30, -60, 40], [-20, -90, -10], [10, 30, -70]],), 81),
    (([[0, -180, 260], [-20, -20, -20]],), 61),   # the highest finish is not the cheapest launch
    (([[20, 30], [40, 50]],), 1),                 # nothing on the map takes height away
    (([[-50]],), 51),                             # one square, and it is still crossed
    (([[70]],), 1),
    (([[-20, 60, -90, 10]],), 51),                # one row: no choice of route at all
    (([[-20], [60], [-90], [10]],), 51),          # one column, same reason
    (([[0, 0], [0, 0]],), 1),
]

Pitfalls

• Flying the route that finishes highest. In the second example that is the eastern one: 240 metres better at the finish, 120 worse off the winch.
• Flooring once, at the corner. A route may dip under a metre halfway and climb back, and a single floor at the end passes it: the second example then answers 1, for a glider already on the ground. The floor is a metre at every square, and a metre rather than zero.
• Leaving the last square out. Its figure counts like any other; skip the −70 in the first example and the launch reads 51.

Variants

• Down the lock grid — the same east-or-south grid, where the cost only ever adds up, so the table fills forward from the north-west square.
• Squares in the mosaic — another grid table, settled from the neighbours behind a cell rather than ahead of it.