py-20261008-rollback-dynamic-connectivity-with-parity-constraints
Done. The full solution is written to ~/solution.md, with runnable code in ~/sol.py and tests in test_sol.py / test_perf.py.
Root causes diagnosed
1. Deletions aren't supported online → decompose time with a segment tree over query indices; each edge lifetime is inserted on O(log Q) nodes and undone on DFS exit.
2. Path compression breaks rollback → use union-by-size (no compression), logging every pointer/size/parity mutation.
3. XOR parity drift → maintain xr[x] = parity(x → parent[x]); on merge set the new root's parity to pu ^ pv ^ w.
4. Inconsistent components corrupt rollback state → don't merge on an odd cycle; instead flip a per-root bad flag and log the flip, so the "inconsistency" is itself undoable. Merges propagate bad with its previous value logged.
Key semantic decision: once a component is non-bipartite, parity(u) XOR parity(v) is not unique, so queries return "inconsistent" rather than an arbitrary path value. My first fuzz run "failed" exactly because the brute force BFS and the DSU picked different valid paths in odd-cycle components — that mismatch was the test being ill-defined, not the algorithm.
Verification
- Smoke test: [1, True, False, 1] (including rollback of the bad flag).
- 3000 randomized differential tests vs. a BFS brute force over add/remove/query/query_bad, with self-loops and re-adds of the same edge with a different parity → all pass, zero mismatches.
- Re-introduction test: same edge flipped 0 → 1 → [0, 1, 0, False].
- Scale test n = T = 10^5 → ~0.37 s, O(n + E log Q) storage.
- The Python code embedded in the markdown was extracted, compiled, and executed to confirm the deliverable itself runs.
Complexity: O((E + Q) log Q · log n) time, O(n + E log Q) near-linear memory.
# Evidence - Problem class: py-20261008-rollback-dynamic-connectivity-with-parity-constraints - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-08T17:06:57.830Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Given a stream of edge insertions, removals, and parity constraints, answer connectivity and XOR-consistency queries at arbitrary times, including after rollback checkpoints; the same edge may be reintroduced with a different constraint. Design an offline algorithm with near-linear memory and explain how to handle inconsistent components without corrupting rollback state.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "py-20261008-rollback-dynamic-connectivity-with-parity-constraints", "provider": "openrouter", "solved_at": "2026-10-08T17:06:57.831Z", "version": "3.13"}