# MyAlgorithmProblems

> 192 algorithm problems with Chinese and English statements and editorials, C++17 solutions, and reproducible Python generators. Selected research covers translation matching in induced four-neighbor, diagonal-only, and eight-neighbor grid forests, together with tree-extension obstructions in the first two models and a four/eight-neighbor extension allowing independently blocked edges.

Research notation: n is board side length, N is road vertex count (N <= n^2), m is actual move count, and W is total individual candidate checks. Candidate-list filtering occurs only at previously unseen relative displacements.

The current proof gives W <= (5n-3)N and time O(n^2+m+nN), hence O(n^3+m), for general induced grid forests. The matching worst-case lower bound for m >= n-1 concerns this candidate-list algorithm, not all possible algorithms. The old logarithmic bound is valid but weaker.

The tree-extension counterexamples retain fixed grid positions and every induced four-neighbor edge, permitting only vertex addition. They remain obstructions on larger boards, and do not disprove reductions that change those rules. They do not imply supercubic matching work.

With diagonal-only adjacency and movement (+/-1,+/-1), the two coordinate-sum parity classes separately map to orthogonal grids of side at most n. Answers and candidate checks add exactly, preserving W <= (5n-3)N and the cubic worst-case order. Tree-extension obstructions transfer within a parity class; different classes are never connectable. This corollary excludes eight-neighbor movement and side-cell corner-cutting restrictions.

With all eight orthogonal and diagonal directions retained, the full induced road graph must still be a forest. A separate proof extends direction words to the rank-four free group and preserves the finite second-axis lemma and the 1+1+2 charging budgets. Thus W <= (5n-3)N and O(n^3+m) time still hold, with matching worst-case order for the candidate-list algorithm when m >= n-1. The parity reduction is not used. This result does not establish eight-neighbor tree-extension obstructions, and the C++ reference program remains four-directional.

With independently blocked static undirected edges, require only the actual traversable graph to be a forest. In both four- and eight-neighbor models, check edge openness when discovering a new vertex, skip previously traversed edges, and clear all candidates in constant time if a new edge closes a query cycle. Intersections must retain only edges open in both translated copies. The modified algorithm retains W <= (5n-3)N, O(n^3+m) time, and its matching worst-case order for m >= n-1. The unmodified C++ program does not implement this model; no new tree-extension claim is made.

Direction A's connected-resource-union disjointness conjecture is false. The current proof uses bounded resource-assignment capacity instead. Historical finite experiments and the earlier capacity draft have limited scope. A repository status of current_proof means a written proof is available; it is not a claim of external peer review or formal verification.

## Result summaries

- [Cubic bound, English](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/cubic-bound.en.md): Model, exact bound, proof outline, reproduction, and citation.
- [三次方上界，中文](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/cubic-bound.zh.md): 模型、准确结论、证明思路、复核与引用。
- [Tree-extension obstructions, English](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/tree-extension.en.md): Small and scalable counterexamples under fixed-position induced vertex addition.
- [补树障碍，中文](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/tree-extension.zh.md): 小反例、两条长路径及线性数量大分量的两两障碍。
- [Diagonal-only extension, English](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/diagonal-only.en.md): Full parity-isomorphism proof, exact check bound, transferred lower bound and tree obstructions, and finite verification scope.
- [仅对角邻接，中文](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/diagonal-only.zh.md): 奇偶拆分与完整证明、复杂度上下界、补树障碍及复核说明。
- [Eight-neighbor extension, English](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/eight-neighbor.en.md): Full proof transfer using rank-four direction words, unchanged exact bound, stripe lower bound, and finite charging certificates.
- [八邻接拓展，中文](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/eight-neighbor.zh.md): 四对方向符号、有限第二轴引理迁移、复杂度上下界和完整收费复核。
- [Vertex and edge obstacles, English](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/edge-obstacles.en.md): Four/eight-neighbor model, revised revisit rule, common open-edge proof, matching lower bound, and finite evidence.
- [顶点与路径障碍，中文](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/edge-obstacles.zh.md): 实际开放边森林、闭环判零、交域与收费证明迁移、下界及复核结果。
- [Result and status index](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/research-index.json): Machine-readable assumptions, conclusions, current and historical statuses, proof paths, and verification commands. Paths are relative to repository root.

## Full proofs and reproduction

- [General cubic proof](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/proofs/cubic-bound.en.md): Complete-history charging, finite second-axis lemma, capacity-two bins, and lower bound.
- [Tree-extension proof](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/examples/tree-extension.en.md): Coordinates, forbidden separators, and proofs for arbitrary parameters.
- [Algorithm editorial](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/solution.en.md): Algorithm and implementation details.
- [Research directory and verification commands](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/README.md): Bilingual reading map, Python checks, and optional C++ comparisons. Finite verification supplements mathematical proofs.
- [Citation guide](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/CITATION.md): Separate research-note citations and immutable proof URLs, using each result's own publication commit.

## Optional

- [All problems](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/README.md): Topic index for the full bilingual problem collection.
- [Research history](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/complexity-research.en.md): Development of the logarithm-removal route.
- [Opposite early arms and historical draft](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/proofs/reference-capacity.en.md): Refutation of direction A and the earlier capacity argument; the general theorem is in the current cubic proof.
- [Comb candidate counts](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/examples/comb-candidates.en.md): Quadratically many survivors after linearly many effective scans do not imply supercubic total work.

## Website and current result catalog

- [Website](https://occamgc.github.io/MyAlgorithmProblems/): Human-readable pages with mathematics and bilingual navigation.
- [Research directory](https://occamgc.github.io/MyAlgorithmProblems/research/): Current and historical statuses.
- [四邻接网格森林平移匹配的三次方复杂度上界](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/cubic-bound.zh.md): current_proof; ID grid-forest-matching-cubic-bound.
- [A cubic time bound for translation matching in four-neighbor grid forests](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/cubic-bound.en.md): current_proof; ID grid-forest-matching-cubic-bound.
- [诱导四邻接网格森林不一定能通过补点扩充成树](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/tree-extension.zh.md): current_proof; ID induced-grid-forest-tree-extension-obstructions.
- [Induced four-neighbor grid forests need not extend to trees by adding vertices](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/tree-extension.en.md): current_proof; ID induced-grid-forest-tree-extension-obstructions.
- [仅对角邻接的网格森林：奇偶拆分与三次方界](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/diagonal-only.zh.md): current_proof; ID grid-forest-matching-diagonal-only.
- [Diagonal-only grid forests: parity decomposition and cubic bounds](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/diagonal-only.en.md): current_proof; ID grid-forest-matching-diagonal-only.
- [八邻接诱导森林：三次方复杂度仍然成立](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/eight-neighbor.zh.md): current_proof; ID grid-forest-matching-eight-neighbor.
- [Eight-neighbor induced forests retain the cubic bound](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/eight-neighbor.en.md): current_proof; ID grid-forest-matching-eight-neighbor.
- [顶点与路径障碍：四邻接、八邻接仍有三次方界](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/edge-obstacles.zh.md): current_proof; ID grid-forest-matching-edge-obstacles.
- [Vertex and edge obstacles: cubic bounds for four and eight neighbors](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/results/edge-obstacles.en.md): current_proof; ID grid-forest-matching-edge-obstacles.
- [线性轮筛选后仍有平方候选的单棵梳形树](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/examples/comb-candidates.zh.md): current_proof; ID grid-forest-matching-comb-candidates.
- [A single comb tree retaining quadratically many candidates after linearly many scans](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/examples/comb-candidates.en.md): current_proof; ID grid-forest-matching-comb-candidates.
- [方向 A 的连通资源并集不交猜想已被否定](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/proofs/reference-capacity.zh.md): refuted_conjecture; ID grid-forest-matching-direction-a.
- [Direction A's connected-resource-union disjointness conjecture is false](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/proofs/reference-capacity.en.md): refuted_conjecture; ID grid-forest-matching-direction-a.
- [较早的带对数因子复杂度上界](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/complexity.zh.md): historical_upper_bound; ID grid-forest-matching-logarithmic-bound.
- [The earlier upper bound with a logarithmic factor](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/complexity.en.md): historical_upper_bound; ID grid-forest-matching-logarithmic-bound.
- [方向 A 的早期有限验证记录](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/examples/reference-components.zh.md): historical_experiment; ID grid-forest-matching-direction-a-finite-search.
- [Early finite checks of direction A](https://raw.githubusercontent.com/OccamGC/MyAlgorithmProblems/main/topics/simulation/grid-forest-matching/research/examples/reference-components.en.md): historical_experiment; ID grid-forest-matching-direction-a-finite-search.