py-20261005-temporal-cut-minimum-repair

Answer

Done. The verified solution is in ~/solution.md (self-contained: title, root-cause analysis, full code, verification). Supporting artifacts are in ~/work/.

What the diagnosis found

The problem stacks three independently hard requirements: exact, directed, and fully dynamic/adversarial. Dynamic s-t min-cut has no known sub-polynomial exact algorithm, and directed graphs admit no Gomory–Hu/cut-tree compression, so n ≤ 2·10⁵, m ≤ 10⁶ in Python is not reachable by any known exact method. On top of that hardness wall, the concrete bugs that sink naive submissions are all fixable:

1. Recursive Dinic DFS overflows at depth O(n) → replaced with an explicit-stack augmenter.
2. Directed cuts count only S → V\S forward arcs (symmetric difference is wrong) → witness validated by recomputing its cut capacity.
3. Witness must be read from the residual graph, not the original.
4. Parallel arcs must stay distinct; zero-weight arcs kept for stable ids.
5. Queries are independent, so capacities must be reset from base each time.
6. The tempting "cut didn't move, reuse it" hybrid is unsound under adversarial decreases → cache only on identical (s,t,version) state.

The fix

A correct iterative-Dinic engine + residual-reachability witness + exact state-keyed offline memo, with explicit bounds O(q·(m + MF(n,m))) (MF = O(n²m) general, O(m√m) unit-capacity). Section 5 lists exactly which relaxation makes the advertised limits achievable (undirected → Gomory–Hu; insert-only → incremental cut tree; approximation → dynamic max-flow).

Verification (all reproduced)

• test_dinic.py → ALL TESTS PASSED: 400 random graphs × every ordered (s,t) pair, parallel arcs, zero weights, post-update re-checks.
• e2e_test.py → E2E ALL PASSED: 200 cases through the real stdin/stdout pipeline vs. an independent brute-force partition search; asserts value equality, s∈S, t∉S, and cut(S) == value.
• Benchmark: n=5000, m=50000, q=10 in ~0.4s.
• I extracted the Python block from solution.md and re-ran the full E2E + benchmark against it → passed identically.