Summary
algorithmic/problems/11/chk.cc formats its verdict into a fixed 30-byte stack buffer:
char mes[30];
sprintf(mes, "Ratio: %lf, RatioUnbounded: %lf", pnt, unbounded_pnt); // lines 80-81
quitp(pnt, "%s", mes);
"Ratio: 1.000000, RatioUnbounded: 1.000000" is 41 characters plus the terminator. With the
judge's -O2 build glibc's fortified sprintf detects the overflow and aborts before quitp
runs.
Effect
This line is only reached by outputs that are a valid palindrome path covering every blank
cell and ending at the target, i.e. only correct answers crash the checker. Wrong answers
take the earlier quitp(0.0, ...) paths and get a clean 0; the three cases whose answer is
-1 go through quitf(_ok, ...) and score 1. The best any submission can reach is therefore
3/10 = 0.300, and in our archived runs 15 of 16 submissions sit exactly at 0.300 with the judge
message *** buffer overflow detected ***.
Side note, not part of the fix: on line 73 op.size() - bound is evaluated in size_t, so for
any path shorter than bound the subtraction wraps and RatioUnbounded is reported as about
-5.7e13. The score is unaffected; only the unbounded figure in the message is garbage.
Verification
Feeding the shipped testdata/1.ans back to the checker as contestant output:
$ ./chk 1.in 1.ans 1.ans
*** buffer overflow detected ***: terminated (exit 134)
$ ./chk 7.in 7.ans 7.ans # answer is -1
ok Correct.
With the fix below all ten shipped answers score points 1.0.
A remark on scoring once the crash is gone
bound = 12 * blank * max(n, m) is about 300,000 moves on the shipped 30×30 cases, while the
shipped .ans paths are 26k–65k moves and every archived agent path is 3k–11k. The checker
never reads .ans. So after the fix every valid answer scores exactly 1.0 and "minimize the
number of moves" is not measured at all; the problem is effectively pass/fail. Whether to
tighten bound (e.g. to the reference length, or a best-known length) is a separate design
decision for the maintainers — this issue only asks for the crash to be fixed.
Suggested fix
Enlarge the buffer:
Summary
algorithmic/problems/11/chk.ccformats its verdict into a fixed 30-byte stack buffer:"Ratio: 1.000000, RatioUnbounded: 1.000000"is 41 characters plus the terminator. With thejudge's
-O2build glibc's fortifiedsprintfdetects the overflow and aborts beforequitpruns.
Effect
This line is only reached by outputs that are a valid palindrome path covering every blank
cell and ending at the target, i.e. only correct answers crash the checker. Wrong answers
take the earlier
quitp(0.0, ...)paths and get a clean 0; the three cases whose answer is-1go throughquitf(_ok, ...)and score 1. The best any submission can reach is therefore3/10 = 0.300, and in our archived runs 15 of 16 submissions sit exactly at 0.300 with the judge
message
*** buffer overflow detected ***.Side note, not part of the fix: on line 73
op.size() - boundis evaluated insize_t, so forany path shorter than
boundthe subtraction wraps andRatioUnboundedis reported as about-5.7e13. The score is unaffected; only the unbounded figure in the message is garbage.Verification
Feeding the shipped
testdata/1.ansback to the checker as contestant output:With the fix below all ten shipped answers score
points 1.0.A remark on scoring once the crash is gone
bound = 12 * blank * max(n, m)is about 300,000 moves on the shipped 30×30 cases, while theshipped
.anspaths are 26k–65k moves and every archived agent path is 3k–11k. The checkernever reads
.ans. So after the fix every valid answer scores exactly 1.0 and "minimize thenumber of moves" is not measured at all; the problem is effectively pass/fail. Whether to
tighten
bound(e.g. to the reference length, or a best-known length) is a separate designdecision for the maintainers — this issue only asks for the crash to be fixed.
Suggested fix
Enlarge the buffer: