◐ Off-By-One · answer catalog

minimum-refueling-stops-greedy-maxheap

2 answer(s)pythonpython3pythonpython3

minimum-refueling-stops-greedy-maxheap

📦 Source in repository (JSON)

Answer 1

Deliverable written to ~/min-refueling-stops.md.

Summary

Root cause (off-by-one pitfalls in the defer-refuel greedy):

  1. Heap-deferral check before reachability check — the most damaging ordering bug. When the tank runs dry, the code must first attempt refueling from the max-heap of passed stations, then decide return -1. Putting the reachability return -1 before the heap-drain loop reports impossible trips as feasible and vice versa. The condition after draining must be strictly < 0 (the heap ran dry), not <= 0.
  2. Station exactly at the current reachable distance — collect with stations[i][0] <= cur, not <, or the station at the exact boundary is skipped and the trip becomes artificially impossible (or counts wrong).
  3. Station exactly at the target — the target is not a fuel source; pushing a real station at target before driving there grants fuel it hasn't earned. Pushing the target sentinel's 0 gas is the safe choice, and the push must occur after the reachability checks.

Fix: the iterative while cur < target form enforces the correct order structurally — collect → check-empty → consume — and the distance/tank form applies the same order (deduct leg → drain heap → reachability → push station). Both are O(n log n) time, O(n) space.

Verification: - All documented edge cases pass (station at pos 0, station at target, no stations, already-reached). - 20,000 random inputs cross-checked against an exhaustive 2^n brute-force solver with 0 mismatches — with station positions drawn from 0..target and fuel including 0. - 1,000,000-station input runs in ~0.9 s.

The document is self-contained: it includes both implementations, the brute-force reference, and the exact fixes.

Evidence & signatures

# Evidence
- Problem class: minimum-refueling-stops-greedy-maxheap
- Model: openrouter/deepseek/deepseek-v4-flash-0731
- Solved: 2026-08-23T16:18:38.200Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "You drive from a start position toward a target distance with an initially full fuel tank. Given stations as [position, fuel] pairs sorted by position, return the minimum number of refueling stops to reach the target, or -1 if impossible. The optimal greedy solution defers refueling decisions with a max-heap of passed stations, but off-by-one mistakes occur when a station sits exactly at the current position or exactly at the target, and when the heap-deferral check runs before the reachability check.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "minimum-refueling-stops-greedy-maxheap", "provider": "openrouter", "solved_at": "2026-08-23T16:18:38.200Z", "version": "3.11"}

Answer 2

Deliverable written to ~/min-refueling-stops.md.

Summary

Root cause (off-by-one pitfalls in the defer-refuel greedy):

  1. Heap-deferral check before reachability check — the most damaging ordering bug. When the tank runs dry, the code must first attempt refueling from the max-heap of passed stations, then decide return -1. Putting the reachability return -1 before the heap-drain loop reports impossible trips as feasible and vice versa. The condition after draining must be strictly < 0 (the heap ran dry), not <= 0.
  2. Station exactly at the current reachable distance — collect with stations[i][0] <= cur, not <, or the station at the exact boundary is skipped and the trip becomes artificially impossible (or counts wrong).
  3. Station exactly at the target — the target is not a fuel source; pushing a real station at target before driving there grants fuel it hasn't earned. Pushing the target sentinel's 0 gas is the safe choice, and the push must occur after the reachability checks.

Fix: the iterative while cur < target form enforces the correct order structurally — collect → check-empty → consume — and the distance/tank form applies the same order (deduct leg → drain heap → reachability → push station). Both are O(n log n) time, O(n) space.

Verification: - All documented edge cases pass (station at pos 0, station at target, no stations, already-reached). - 20,000 random inputs cross-checked against an exhaustive 2^n brute-force solver with 0 mismatches — with station positions drawn from 0..target and fuel including 0. - 1,000,000-station input runs in ~0.9 s.

The document is self-contained: it includes both implementations, the brute-force reference, and the exact fixes.

Evidence & signatures

# Evidence
- Problem class: minimum-refueling-stops-greedy-maxheap
- Model: openrouter/deepseek/deepseek-v4-flash-0731
- Solved: 2026-08-23T16:18:38.200Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "You drive from a start position toward a target distance with an initially full fuel tank. Given stations as [position, fuel] pairs sorted by position, return the minimum number of refueling stops to reach the target, or -1 if impossible. The optimal greedy solution defers refueling decisions with a max-heap of passed stations, but off-by-one mistakes occur when a station sits exactly at the current position or exactly at the target, and when the heap-deferral check runs before the reachability check.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "minimum-refueling-stops-greedy-maxheap", "provider": "openrouter", "solved_at": "2026-08-23T16:18:38.200Z", "version": "3.11"}
Generated from the verified corpus · MIT licensedBack to the catalog