Summary
algorithmic/problems/145/checker.cpp counts loop solutions with a plain backtracking search
over the 312 grid edges and stops early only once it has found LIMIT = 6 solutions. On weakly
constrained boards (almost every clue a 1 or a 2) the search neither finds six solutions nor
exhausts the space within the judge's checker limit (10 s CPU / 20 s wall,
judge_engine.js:211), so the checker is killed and the case is scored 0 with an empty message.
Effect
Of 14 archived submissions from a recent campaign (2 arms × 8 runs, minus two session
failures), 10 never return (killed at 15 s locally; still 0 solutions after 2,000,000 search
nodes), 3 score normally (needing 69k / 372k / 570k nodes), and 1 is a format error. The
bundled reference answer needs 3,726 nodes and returns in 0.02 s. The restored second case
(2.in, mode 1, PR #171) does not help: 11 of 14 submissions print the same board for both
modes, and the same 10 hang.
Verification
Instrumented copy of the checker (node counter + CHK_BUDGET env var), on the archived boards:
xpcBCfx nodes=68799 sols=6 0.34 s
m5vW4se nodes=372057 sols=6 1.94 s
qCkXWPQ nodes=569553 sols=6 2.88 s
10 others nodes=2000001 sols=0 budget hit (7-13 s), original checker >15 s and counting
Suggested fix
The root cause is the counting algorithm. The file header says the checker "fully reproduces
behavior of the original Python+Z3 checker", but it replaced the SAT solver with a plain
backtracking search (static edge order, local propagation only) whose cost is exponential in
how weakly the clues constrain the board — and weakly constraining clues (many 1s) are exactly
what the task rewards. Two options:
- Proper fix: replace the counter with a profile ("plug") DP over the 12-wide grid. It
counts single loops satisfying all clues exactly and deterministically in milliseconds for
any board (about 4×10⁴ boundary states, 144 cells), so no budget is needed and the verdict
never depends on the checker's algorithm.
- Interim fix: give the backtracking a deterministic node budget (e.g. 1,000,000 nodes,
≈ 6.5 s CPU worst case observed, under the 10 s checker limit) and score an undetermined
count as 0 with an explicit message. Counting nodes rather than wall time keeps verdicts
reproducible. Scoring an undetermined board as the "6 or more" bucket instead would be
exploitable: a board with 55 1 clues that the checker cannot verify would earn
(1 + 9·55/56)/100 ≈ 0.098, above the best real submission (0.061). This option makes
hard-to-verify boards score 0, i.e. it penalises what the task asks to maximise, so it
should be documented in the statement and treated as temporary.
Either can be submitted as a PR; guidance on which the maintainers prefer is welcome.
Summary
algorithmic/problems/145/checker.cppcounts loop solutions with a plain backtracking searchover the 312 grid edges and stops early only once it has found
LIMIT = 6solutions. On weaklyconstrained boards (almost every clue a
1or a2) the search neither finds six solutions norexhausts the space within the judge's checker limit (10 s CPU / 20 s wall,
judge_engine.js:211), so the checker is killed and the case is scored 0 with an empty message.Effect
Of 14 archived submissions from a recent campaign (2 arms × 8 runs, minus two session
failures), 10 never return (killed at 15 s locally; still 0 solutions after 2,000,000 search
nodes), 3 score normally (needing 69k / 372k / 570k nodes), and 1 is a format error. The
bundled reference answer needs 3,726 nodes and returns in 0.02 s. The restored second case
(
2.in, mode 1, PR #171) does not help: 11 of 14 submissions print the same board for bothmodes, and the same 10 hang.
Verification
Instrumented copy of the checker (node counter +
CHK_BUDGETenv var), on the archived boards:Suggested fix
The root cause is the counting algorithm. The file header says the checker "fully reproduces
behavior of the original Python+Z3 checker", but it replaced the SAT solver with a plain
backtracking search (static edge order, local propagation only) whose cost is exponential in
how weakly the clues constrain the board — and weakly constraining clues (many
1s) are exactlywhat the task rewards. Two options:
counts single loops satisfying all clues exactly and deterministically in milliseconds for
any board (about 4×10⁴ boundary states, 144 cells), so no budget is needed and the verdict
never depends on the checker's algorithm.
≈ 6.5 s CPU worst case observed, under the 10 s checker limit) and score an undetermined
count as 0 with an explicit message. Counting nodes rather than wall time keeps verdicts
reproducible. Scoring an undetermined board as the "6 or more" bucket instead would be
exploitable: a board with 55
1clues that the checker cannot verify would earn(1 + 9·55/56)/100 ≈ 0.098, above the best real submission (0.061). This option makeshard-to-verify boards score 0, i.e. it penalises what the task asks to maximise, so it
should be documented in the statement and treated as temporary.
Either can be submitted as a PR; guidance on which the maintainers prefer is welcome.