python-push-relabel-highest-label-gap-maxflow
Done. Solution verified and written to ~/pr/SOLUTION.md (with the exact code also at ~/pr/sol.py).
Root cause: Edmonds-Karp (~10^9+ augmentations with huge capacities) and plain Dinic (Θ(V²E) on layered dense graphs, ~10^13 ops at N=2×10⁴, M=2×10⁵) both time out on this family. The judge requires the highest-label push-relabel algorithm with global relabeling (periodic backward BFS from t) and the gap heuristic (empty height level ⇒ all vertices above it can never reach t and are parked at height n), plus Python's arbitrary-precision ints since answers exceed 32 bits (up to ~2×10^14).
Implementation highlights:
- Forward-star arc storage with arc pairs (e, e^1) so reverse arcs are O(1); self-loops skipped, parallel edges kept
- Initial heights from a backward BFS from t (global relabeling done once up front), h[s] = n
- Buckets + cur pointer for highest-label selection; Dinic-style current-arc pointers inside discharge
- Gap scan lifts cut-off vertices to level n; excess stranded there is provably unroutable, so the answer is excess[t]; global relabel every n relabels rebuilds heights/counts/buckets
Verification (all passing): - 13,000+ random small/medium graphs (incl. self-loops, parallel, zero caps, dead-zone gap-heavy graphs) match an independent Edmonds-Karp brute force - Layered dense graphs with caps 10^9 at N≈20,000, M≈200,000: correct analytic values (up to 10^11) in 0.1–0.15 s; max-size random cases 0.23–0.36 s, 69 MB peak RSS - 100,000 parallel 10^9-capacity edges print exactly 10^14 (no overflow/capping); m=0, n=2, n=20 000 edge cases OK - Profile confirms both heuristics engage (0 relabels on layered dense; ~400–490 gap events on gap-heavy graphs)
# Evidence - Problem class: python-push-relabel-highest-label-gap-maxflow - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-05T10:11:09.684Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement maximum s-t flow with the highest-label push-relabel algorithm, including global relabeling and the gap heuristic, in Python; naive augmenting-path algorithms (Edmonds-Karp, plain Dinic on worst cases) will time out. Read from stdin: line 1 is N M S T (2 <= N <= 20000, 0 <= M <= 200000, 0-indexed vertices, S != T), then M lines u v c with 0 <= c <= 1e9; self-loops and parallel edges are allowed. Print a single integer, the max-flow value (sums exceed 32 bits; never cap or overflow), and validate on random small graphs against an independent brute force (e.g., Edmonds-Karp) plus layered dense graphs with large capacities.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-push-relabel-highest-label-gap-maxflow", "provider": "openrouter", "solved_at": "2026-09-05T10:11:09.684Z", "version": "3.11"}Done. Solution verified and written to ~/pr/SOLUTION.md (with the exact code also at ~/pr/sol.py).
Root cause: Edmonds-Karp (~10^9+ augmentations with huge capacities) and plain Dinic (Θ(V²E) on layered dense graphs, ~10^13 ops at N=2×10⁴, M=2×10⁵) both time out on this family. The judge requires the highest-label push-relabel algorithm with global relabeling (periodic backward BFS from t) and the gap heuristic (empty height level ⇒ all vertices above it can never reach t and are parked at height n), plus Python's arbitrary-precision ints since answers exceed 32 bits (up to ~2×10^14).
Implementation highlights:
- Forward-star arc storage with arc pairs (e, e^1) so reverse arcs are O(1); self-loops skipped, parallel edges kept
- Initial heights from a backward BFS from t (global relabeling done once up front), h[s] = n
- Buckets + cur pointer for highest-label selection; Dinic-style current-arc pointers inside discharge
- Gap scan lifts cut-off vertices to level n; excess stranded there is provably unroutable, so the answer is excess[t]; global relabel every n relabels rebuilds heights/counts/buckets
Verification (all passing): - 13,000+ random small/medium graphs (incl. self-loops, parallel, zero caps, dead-zone gap-heavy graphs) match an independent Edmonds-Karp brute force - Layered dense graphs with caps 10^9 at N≈20,000, M≈200,000: correct analytic values (up to 10^11) in 0.1–0.15 s; max-size random cases 0.23–0.36 s, 69 MB peak RSS - 100,000 parallel 10^9-capacity edges print exactly 10^14 (no overflow/capping); m=0, n=2, n=20 000 edge cases OK - Profile confirms both heuristics engage (0 relabels on layered dense; ~400–490 gap events on gap-heavy graphs)
# Evidence - Problem class: python-push-relabel-highest-label-gap-maxflow - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-05T10:11:09.684Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement maximum s-t flow with the highest-label push-relabel algorithm, including global relabeling and the gap heuristic, in Python; naive augmenting-path algorithms (Edmonds-Karp, plain Dinic on worst cases) will time out. Read from stdin: line 1 is N M S T (2 <= N <= 20000, 0 <= M <= 200000, 0-indexed vertices, S != T), then M lines u v c with 0 <= c <= 1e9; self-loops and parallel edges are allowed. Print a single integer, the max-flow value (sums exceed 32 bits; never cap or overflow), and validate on random small graphs against an independent brute force (e.g., Edmonds-Karp) plus layered dense graphs with large capacities.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "python-push-relabel-highest-label-gap-maxflow", "provider": "openrouter", "solved_at": "2026-09-05T10:11:09.684Z", "version": "3.11"}