Cross the most walls on a number line with limited energy

Model. Walls sit at distinct non-zero integer positions. A wall at x > 0 is crossed every time you step between x - 1 and x (in either direction); a wall at x < 0 is crossed every time you step between x + 1 and x. Every step costs 1 energy, and every crossing also costs that wall's cost. You start at 0 with energy E and may stop anywhere. Return the largest number of distinct walls you can cross.

Brute force. Search over states (position, set of walls crossed) with Dijkstra or BFS on energy spent. This is exponential in the number of walls. Candidates who report this problem say a BFS with a visited set passes about half the tests and times out on the rest. It is still the right thing to say first, and it is a good checker for the fast solution.

Key observations.

1. On one side you cannot cross a far wall without first crossing every nearer wall on that side. So the walls you cross are always the i nearest on the right and the j nearest on the left, for some i and j.
2. Let a[i] be the energy needed to walk right and cross the i nearest right walls: the distance to the i-th wall plus the sum of the first i costs. Define b[j] the same way on the left. Both arrays start at 0 and strictly increase, because each wall adds at least one step.
3. An optimal walk turns around at most once. Go out to one side, come back through 0 (crossing that side's walls a second time, at the same cost again), then go out to the other side and stop. Walking a side twice costs exactly 2 * a[i] (or 2 * b[j]), so the trip costs a[i] + b[j] + min(a[i], b[j]): do the cheaper side first. Zig-zagging more often only repeats steps and crossings.

Optimal method. Sort each side by distance and build a and b as prefix sums. Then maximise i + j subject to a[i] + b[j] + min(a[i], b[j]) <= E. That cost increases in both i and j. So as i goes up, the largest feasible j can only go down, and a two-pointer sweep finds the answer in linear time after sorting. (A binary search per i also works, at O(n log n).)

Invariant. During the sweep, j is the largest index with trip(a[i], b[j]) <= E for the current i. Because the feasible j never increases with i, the pointer only moves left, so the sweep does O(n + m) work in total.

from typing import List, Tuple


def reach_costs(walls: List[Tuple[int, int]]) -> List[int]:
    """walls: (distance from 0, cost) pairs, all on one side, any order.

    Returns r where r[k] is the energy to walk out from 0 and cross the
    k nearest walls (r[0] = 0). Strictly increasing: every distance >= 1.
    """
    r = [0]
    paid = 0
    for dist, cost in sorted(walls):
        paid += cost
        r.append(dist + paid)  # dist steps plus every wall cost on the way
    return r


def max_walls(energy: int, positions: List[int], costs: List[int]) -> int:
    right = [(p, c) for p, c in zip(positions, costs) if p > 0]
    left = [(-p, c) for p, c in zip(positions, costs) if p < 0]
    a = reach_costs(right)  # a[i]: go right and cross i walls
    b = reach_costs(left)   # b[j]: go left and cross j walls

    def trip(x: int, y: int) -> int:
        # Cheaper side first: walk it out and back, then the other side once.
        return x + y + min(x, y)

    best = 0
    j = len(b) - 1
    for i in range(len(a)):
        if a[i] > energy:
            break  # a is increasing, so no larger i can work either
        # trip grows with j, and the feasible j only shrinks as i grows.
        while j > 0 and trip(a[i], b[j]) > energy:
            j -= 1
        best = max(best, i + j)
    return best


if __name__ == "__main__":
    assert max_walls(10, [3, -2, 6], [2, 1, 1]) == 2
    assert max_walls(15, [3, -2, 6], [2, 1, 1]) == 3
    assert max_walls(7, [2, -1], [1, 1]) == 2
    assert max_walls(6, [2, -1], [1, 1]) == 1
    assert max_walls(0, [1], [0]) == 0
    assert max_walls(10, [], []) == 0
    print("ok")

• Sorting each side: O(n log n) time for n walls in total.
• Prefix sums and the two-pointer sweep: O(n) time.
• Space: O(n) for the two reach-cost arrays.
• The brute-force state search is O(2^n * span) states. Use it only to check answers on tiny inputs.

• E = 10, walls [3, -2, 6], costs [2, 1, 1] → 2. Going right to 6 costs 6 + 3 = 9. Crossing 3 and -2 costs 5 + 3 + 3 = 11.
• E = 15, same walls → 3. Go left to -2 and back (6), then right to 6 (9): total 15.
• E = 7, walls [2, -1], costs [1, 1] → 2. Left first: 2 * 2 + 3 = 7. Right first would need 2 * 3 + 2 = 8.
• E = 6, same walls → 1. The order of the two sides matters for the answer.
• E = 0, wall [1] with cost 0 → 0. The single step alone costs 1.
• E = 1, wall [1] with cost 0 → 1.
• No walls → 0.
• All walls on one side → the answer is the largest i with a[i] <= E.
• A far wall that is cheap behind a near wall that is expensive: you still must pay the near one. The prefix sum handles this.
• Large values (E and costs up to 10^9, 10^5 walls): Python ints do not overflow. In Java or C++, use 64-bit integers.

1. You must return to 0 at the end. Both sides are then walked twice, so the condition becomes 2 * (a[i] + b[j]) <= E. The same two-pointer sweep works.
2. A wall charges only on the first crossing. Going back over a wall you have already crossed costs only steps. The trip cost becomes a[i] + b[j] + min(d_i, d_j), where d is the distance alone. This is no longer a function of a and b only, so keep the distance arrays as well. The cost is still monotone in i and j, so the two pointers still work.
3. Many energy queries. Precompute, for each i, the best j as a function of E. A simpler route: the answer is monotone in E, so for each query binary-search j per i (O(n log n) per query). Or sort the queries and move the pointers once across all of them.
4. Walls can share a position or have negative cost (a "boost"). Same position: merge the walls into one point with a combined cost, but count each wall. Negative cost breaks monotonicity of a, so the two-pointer argument fails. Fall back to a binary search over a prefix maximum, or to an explicit O(n * m) scan, and explain why.
5. Report the path, not just the count. Store the (i, j) that wins and which side went first. Then output the turn-around point and the final position.

Mid-level (L4)

• Asks how crossing is charged (once or on every pass) and whether you must return to 0.
• Writes the brute-force search or a direct O(n * m) loop over (i, j), and gets it correct.
• Sees that the crossed walls are a contiguous block around 0.

Senior (L5)

• Argues that one turn is enough and that the cheaper side goes first.
• Builds the prefix reach costs and gets to O(n log n) with sorting plus a binary search or two pointers.
• Tests the edge cases: an empty side, zero energy, and the case where the order of the sides changes the answer.

Staff (L6+)

• Proves the monotonicity behind the two-pointer sweep and states the invariant clearly.
• Changes the cost model cleanly for the follow-ups (charge only on first crossing, must return, negative costs) and says which parts of the proof still hold.
• Talks about how to test it: a brute-force checker on small random inputs, overflow in other languages, and many-query batching.