1000组随机测试全过程序却是错的我给三个有序数组的距离题写了一个本地判题器原本想确认线性算法是否正确。结果最值得记下来的不是又跑了多少组 AC而是一个反例把正确程序中的改成它在本轮1000 组无重复值的随机输入上全过放进允许重复值的小规模穷举却失败了 843 次。问题不是随机测试没执行而是生成器从来不问算法最薄弱的那一类问题。1. 先说判的是什么这是我最初遇到的非原始408题面从非空、非降序的 A、B、C 各选一个元素最小化D|a-b||b-c|。注意它没有|c-a|把两道题共用一个距离函数会得到一个看起来很稳定、实际判错题的工具。输出约定为D a b c。这比只输出距离多了一项责任三个数必须确实来自对应数组。要检查的东西只比最小距离会漏掉什么输出格式少输出一行、混入调试文本元素归属报出不在数组里的三元组得分一致三元组不对却伪造一个正确的 D最优性合法但不够好的答案多解接受正确答案不必和标准程序选同一个三元组这里有一个很好手算的用例A[1,3], B[2], C[1,3]。2 1 2 1与2 3 2 3都对。如果 checker 逐字比较输出至少会冤枉其中一个。2. 参考答案不要复刻被测算法被测 C 程序固定 b用单调指针找最近值。我没有再写一个同样的指针版本当标准答案而是在小输入上直接枚举所有三元组function bruteForce({ A, B, C }) { const abs x x 0n ? -x : x; let best null; for (const a of A) for (const b of B) for (const c of C) { const d abs(BigInt(a) - BigInt(b)) abs(BigInt(b) - BigInt(c)); if (best null || d best) best d; } return best; }它慢但只有三层循环和题目定义不依赖“最近位置会单调移动”的结论。输入限制足够小慢就不是问题结构和待测程序不同才是它的价值。这仍不意味着 oracle 自动正确。我另外核对了手算用例、交换 A/C 不改变答案、共同平移不改变距离等性质。整数极值也单独检查ac2147483647,b-2147483648的 D 是8589934590。C 里必须先把操作数提升到足够宽的类型再减JavaScript oracle 使用 BigInt。不要先用窄类型算坏了再给结果套一个宽类型。3. 故意制造一个“有道理”的错误变异只改一处/* 正确版本会跨过距离相等的平台。 */ while (i 1 n distance_between(a[i 1], b[t]) distance_between(a[i], b[t])) { i; }将换成不是明显的语法错误而是很容易写出的优化条件。我先用固定种子生成 1000 组每个数组内元素唯一的随机用例这个变异程序全部通过。然后枚举值域{-1,0,1}内、长度1到3的全部非降序数组共19个数组三个数组的组合为19^36859组再加10组小边界用例。被测程序用例集合本轮结果变异版本1000组无重复随机输入0次失败正确版本6859组穷举10组边界0次失败变异版本同样6869组输入843次失败第一个失败输入很小A[1,1,4], B[4], C[4]。变异版停在第一个1输出3 1 4 4而0 4 4 4才是最优解。这让失败有了原因不只是一个 WA 标签。这里还要区分“距离相等”和“重复值挡住指针”。例如A[-1,1,2], b0停在-1也没有错-1与1都已是最近值但[1,1,4], b4的两个1只是通往更好值4之前的平台。生成器只生成数组内互异值正好避开了后一类故障。843是这个固定用例集合里该变异的失败次数不是算法在所有实际输入中的“错误率”。换一个生成分布数字就可能不同不能只把随机次数加大却始终排除触发错误的条件。4. 工具本身也需要坏答案我还直接给 checker 喂了两种伪答案输入A[1,1,4], B[4], C[4] 0 99 99 99 - 元素不属于对应数组拒绝 0 1 4 4 - 声称D0但三元组实际D3拒绝这些测试检查的是“裁判有没有认真核对”不是算法有没有找到答案。除此之外编译失败、非零退出、超时应分别报告 CE、RE、TLE输入不合法应报告判题配置错误而不是怪参赛程序答错。本地实现将首个失败用例保存为failure.in同时记下种子、组别、期望值和实际输出。种子帮助追溯但原始失败输入才是不依赖生成器后续版本的证据。当前工具没有自动缩减所有反例也没有容器级隔离不能直接开放给陌生人上传执行 C 代码超时限制不等于安全沙箱。5. 我真正改变的是测试顺序现在我会先问有没有重复值有没有多解有无整数边界参考程序与待测程序是否共享同一个假设再决定随机跑多少次。这次穷举只覆盖一个很小的有限域当然不是完整正确性证明1000组随机全过也只是当前分布下未发现反例。证明说明算法为什么对测试帮助发现证明或实现哪里没覆盖两者不能互相替代。这篇的 C 正确版与变异版、oracle、checker 都来自同一轮真实执行而不是事后编造的测试数字。复现材料为experiments/2026-10-03-candidates/verify-local.mjs与原题的solution.c、problem.mjs完整独立复现文件见下方附录无需等待托管仓库。附录完整复现文件下面三个文件放在同一个新建目录用Windows上的Node.js 22与GCC运行node verify-local.mjs。GCC需在PATH中或通过BLOG_CC指定完整路径。程序只编译固定的solution.c及其严格小于变异不提供陌生代码上传执行能力不是安全沙箱。这是从原始实验中抽出的判题部分不再要求TinyCC和代理实验依赖。结果与首个失败输入写入随机run目录里的results.json首个失败对象同时包含输入、期望值和实际输出不依赖种子重建。原始完整工作台另外提供failure.in导出两者不要混淆。solution.c#include inttypes.h #include stdint.h #include stdio.h #include stdlib.h typedef struct { int64_t distance; int32_t a, b, c; } Answer; static int64_t distance_between(int32_t x, int32_t y) { int64_t delta (int64_t)x - (int64_t)y; return delta 0 ? delta : -delta; } static Answer solve(const int32_t *a, size_t n, const int32_t *b, size_t m, const int32_t *c, size_t k) { size_t i 0, j 0; Answer best {INT64_MAX, 0, 0, 0}; for (size_t t 0; t m; t) { /* Advance through ties, including duplicate elements. */ while (i 1 n distance_between(a[i 1], b[t]) distance_between(a[i], b[t])) { i; } while (j 1 k distance_between(c[j 1], b[t]) distance_between(c[j], b[t])) { j; } int64_t d distance_between(a[i], b[t]) distance_between(b[t], c[j]); if (d best.distance) best (Answer){d, a[i], b[t], c[j]}; } return best; } static int read_array(int32_t *values, size_t length) { for (size_t i 0; i length; i) { if (scanf(% SCNd32, values[i]) ! 1) return 0; if (i 0 values[i] values[i - 1]) return 0; } return 1; } int main(void) { size_t n, m, k; int count; /* A single case is valid; repeated cases support local batch checking. */ while ((count scanf(%zu%zu%zu, n, m, k)) ! EOF) { if (count ! 3 || n 0 || m 0 || k 0 || n 200000 || m 200000 || k 200000) return 1; int32_t *a malloc(n * sizeof(*a)); int32_t *b malloc(m * sizeof(*b)); int32_t *c malloc(k * sizeof(*c)); if (a NULL || b NULL || c NULL) { free(a); free(b); free(c); return 1; } if (!read_array(a, n) || !read_array(b, m) || !read_array(c, k)) { free(a); free(b); free(c); return 1; } Answer result solve(a, n, b, m, c, k); printf(% PRId64 % PRId32 % PRId32 % PRId32 \n, result.distance, result.a, result.b, result.c); free(a); free(b); free(c); } return 0; }problem.mjsimport assert from node:assert/strict; export const id three-arrays-distance; export const minimum -2147483648; export const maximum 2147483647; export function validateCase({ A, B, C }) { for (const values of [A, B, C]) { assert.ok(Array.isArray(values) values.length 0 values.length 200000, Array length out of bounds); values.forEach((x, i) { assert.ok(Number.isInteger(x) x minimum x maximum, Expected int32 element); assert.ok(i 0 || values[i - 1] x, Array must be sorted); }); } } const abs x x 0n ? -x : x; export function bruteForce({ A, B, C }) { if (A.length * B.length * C.length 2000000) throw new Error(Case too large for brute-force oracle); let best null; for (const a of A) for (const b of B) for (const c of C) { const d abs(BigInt(a) - BigInt(b)) abs(BigInt(b) - BigInt(c)); if (best null || d best) best d; } return best; } export function serialize(test) { validateCase(test); return ${test.A.length} ${test.B.length} ${test.C.length}\n${test.A.join( )}\n${test.B.join( )}\n${test.C.join( )}\n; } export function parseInput(input) { const tokens input.trim().split(/\s/); if (!input.trim()) throw new Error(Input is empty); if (!tokens.every(x /^-?\d$/.test(x))) throw new Error(Only integer tokens are allowed); let at 0; const cases []; while (at tokens.length) { const sizes tokens.slice(at, at 3).map(Number); at 3; if (sizes.length ! 3 || sizes.some(n !Number.isInteger(n) || n 1 || n 200000)) throw new Error(Invalid lengths); const values sizes.map(n { if (at n tokens.length) throw new Error(Incomplete array); const result tokens.slice(at, at n).map(Number); at n; return result; }); const test { label: custom-${cases.length 1}, A: values[0], B: values[1], C: values[2] }; validateCase(test); cases.push(test); } return cases; } export function checkAnswer(test, line, expected) { const fields line.trim().split(/\s/); if (fields.length ! 4 || fields.some(x !/^-?\d$/.test(x))) return Expected four integers: D a b c; const [d, a, b, c] fields.map(BigInt); const belongs (values, value) values.some(x BigInt(x) value); if (!belongs(test.A, a) || !belongs(test.B, b) || !belongs(test.C, c)) return Selected values do not belong to the corresponding arrays; const computed abs(a - b) abs(b - c); if (d ! computed) return Reported distance does not match selected values; if (d ! expected) return Distance is not optimal: expected ${expected}, got ${d}; return null; } function randomGenerator(seed) { let state seed 0; return () { state (state 0x6D2B79F5) 0; let x Math.imul(state ^ (state 15), 1 | state); x ^ x Math.imul(x ^ (x 7), 61 | x); return ((x ^ (x 14)) 0) / 4294967296; }; } function sortedArrays(alphabet, maxLength) { const all []; function extend(prefix, from) { if (prefix.length) all.push(prefix); if (prefix.length maxLength) return; for (let i from; i alphabet.length; i) extend([...prefix, alphabet[i]], i); } extend([], 0); return all; } export function generateCases({ seed 408, randomCount 2000, exhaustive true } {}) { const cases []; const add (label, A, B, C, expected) cases.push({ label, A, B, C, ...(expected undefined ? {} : { expected: String(expected) }) }); add(sample, [1, 4, 8], [5, 10], [2, 6, 12]); add(duplicates-block-A, [1, 1, 4], [4], [4]); add(duplicates-block-C, [4], [4], [1, 1, 4]); add(all-equal, [2, 2], [2, 2], [2, 2]); add(equal-distance, [1, 3], [2], [1, 3]); add(query-right-of-arrays, [-9, -5], [10, 10], [-7, -1]); add(query-left-of-arrays, [5, 9], [-10], [2, 8]); add(negative, [-9, -4, -1], [-5, -2], [-6, -3]); add(int32-extreme-sum, [maximum], [minimum], [maximum]); add(extreme-exact-match, [minimum, maximum], [minimum, maximum], [minimum, maximum]); if (exhaustive) { const arrays sortedArrays([-1, 0, 1], 3); for (const A of arrays) for (const B of arrays) for (const C of arrays) add(exhaustive, A, B, C); } const random randomGenerator(seed); const int max Math.floor(random() * max); for (let i 0; i randomCount; i) { const array () Array.from({ length: 1 int(12) }, () { const mode int(20); return mode 0 ? minimum : mode 1 ? maximum : int(101) - 50; }).sort((a, b) a - b); const test { A: array(), B: array(), C: array() }; add(random-${i}, test.A, test.B, test.C); if (i % 5 0) { const expected bruteForce(test); add(swap-A-C-${i}, test.C, test.B, test.A, expected); const duplicate values [...values, values[int(values.length)]].sort((a, b) a - b); add(duplicate-${i}, duplicate(test.A), duplicate(test.B), duplicate(test.C), expected); if ([...test.A, ...test.B, ...test.C].every(x x -50 x 50)) { add(translate-${i}, test.A.map(x x 17), test.B.map(x x 17), test.C.map(x x 17), expected); add(scale-${i}, test.A.map(x x * 3), test.B.map(x x * 3), test.C.map(x x * 3), expected * 3n); } } } // Large cases use a known optimum witnessed by a value shared by all arrays. add(large-shared-zero, Array(200000).fill(0), Array(200000).fill(0), Array(200000).fill(0), 0); const increasing Array.from({ length: 200000 }, (_, i) i); add(large-full-traversal, increasing, [199999], increasing, 0); return cases; }verify-local.mjsimport { readFile, writeFile, mkdir, readdir } from node:fs/promises; import { spawnSync, spawn } from node:child_process; import { once } from node:events; import { createServer } from node:http; import { fileURLToPath } from node:url; import assert from node:assert/strict; import * as problem from ./problem.mjs; const base fileURLToPath(new URL(., import.meta.url)).replaceAll(\\,/).replace(/\/$/,); const blogRoot fileURLToPath(new URL(../../, import.meta.url)).replaceAll(\\,/).replace(/\/$/,); const run ${base}/run-${Date.now()}; await mkdir(run); const evidence { run, checks: [], commands: [] }; function check(name, value) { assert.ok(value, name); evidence.checks.push(name); } function command(exe, args, cwdrun, input, envprocess.env) { const r spawnSync(exe, args, { cwd, input, env, encoding:utf8, timeout:30000, windowsHide:true }); assert.ok(!r.error, String(r.error)); const row { exe, args, cwd, status:r.status, stdout:r.stdout, stderr:r.stderr }; evidence.commands.push(row); return row; } const source await readFile(${base}/solution.c,utf8); await writeFile(${run}/good.c,source); await writeFile(${run}/strict.c,source.replaceAll( distance_between, distance_between)); const gccprocess.env.BLOG_CC || gcc; const env{...process.env}; for (const name of [good,strict]) check(${name}: compile, command(gcc,[-stdc11,-O2,-Wall,-Wextra,${run}/${name}.c,-o,${run}/${name}.exe],run,undefined,env).status0); function compare(name,cases) { const rcommand(${run}/${name}.exe,[],run,cases.map(problem.serialize).join(),env); check(${name}: normal exit,r.status0); const linesr.stdout.trim().split(/\r?\n/); assert.equal(lines.length,cases.length); const failurescases.flatMap((t,i){ const expectedproblem.bruteForce(t), reasonproblem.checkAnswer(t,lines[i],expected); return reason?[{input:t,expected:String(expected),actual:lines[i],reason}]:[]; }); return {count:cases.length,failures:failures.length,firstFailure:failures[0]}; } let state408; const random(){ state(Math.imul(state,1664525)1013904223)0; return state; }; const distinct()Array.from(new Set(Array.from({length:1random()%6},()random()%21-10))).sort((a,b)a-b); const uniqueArray.from({length:1000},()({A:distinct(),B:distinct(),C:distinct()})); evidence.uniquecompare(strict,unique); check(strict passes unique-only generator,evidence.unique.failures0); const smallproblem.generateCases({randomCount:0}).filter(tt.A.length*t.B.length*t.C.length2000000); evidence.goodcompare(good,small); evidence.strictcompare(strict,small); check(correct implementation passes small exhaustive cases,evidence.good.failures0); check(strict mutation is caught with duplicates,evidence.strict.failures0); const duplicate{A:[1,1,4],B:[4],C:[4]}; const tie{A:[1,3],B:[2],C:[1,3]}; check(checker accepts first optimal witness,problem.checkAnswer(tie,2 1 2 1,2n)null); check(checker accepts alternate optimal witness,problem.checkAnswer(tie,2 3 2 3,2n)null); check(checker rejects invented witness,Boolean(problem.checkAnswer(duplicate,0 99 99 99,0n))); check(checker rejects forged score,Boolean(problem.checkAnswer(duplicate,0 1 4 4,0n))); check(extreme score uses BigInt,problem.bruteForce({A:[2147483647],B:[-2147483648],C:[2147483647]})8589934590n); evidence.statuspassed; await writeFile(${run}/results.json,JSON.stringify(evidence,null,2)); console.log(JSON.stringify({checks:evidence.checks.length,unique:evidence.unique,good:evidence.good,strict:evidence.strict,run})); 
长河君 · 2026/10/13 3:13:45 · 阅读 1.2k 1000组随机测试全过，程序却是错的：我怎样验证自己的判题器
1000组随机测试全过程序却是错的我给三个有序数组的距离题写了一个本地判题器原本想确认线性算法是否正确。结果最值得记下来的不是又跑了多少组 AC而是一个反例把正确程序中的改成它在本轮1000 组无重复值的随机输入上全过放进允许重复值的小规模穷举却失败了 843 次。问题不是随机测试没执行而是生成器从来不问算法最薄弱的那一类问题。1. 先说判的是什么这是我最初遇到的非原始408题面从非空、非降序的 A、B、C 各选一个元素最小化D|a-b||b-c|。注意它没有|c-a|把两道题共用一个距离函数会得到一个看起来很稳定、实际判错题的工具。输出约定为D a b c。这比只输出距离多了一项责任三个数必须确实来自对应数组。要检查的东西只比最小距离会漏掉什么输出格式少输出一行、混入调试文本元素归属报出不在数组里的三元组得分一致三元组不对却伪造一个正确的 D最优性合法但不够好的答案多解接受正确答案不必和标准程序选同一个三元组这里有一个很好手算的用例A[1,3], B[2], C[1,3]。2 1 2 1与2 3 2 3都对。如果 checker 逐字比较输出至少会冤枉其中一个。2. 参考答案不要复刻被测算法被测 C 程序固定 b用单调指针找最近值。我没有再写一个同样的指针版本当标准答案而是在小输入上直接枚举所有三元组function bruteForce({ A, B, C }) { const abs x x 0n ? -x : x; let best null; for (const a of A) for (const b of B) for (const c of C) { const d abs(BigInt(a) - BigInt(b)) abs(BigInt(b) - BigInt(c)); if (best null || d best) best d; } return best; }它慢但只有三层循环和题目定义不依赖“最近位置会单调移动”的结论。输入限制足够小慢就不是问题结构和待测程序不同才是它的价值。这仍不意味着 oracle 自动正确。我另外核对了手算用例、交换 A/C 不改变答案、共同平移不改变距离等性质。整数极值也单独检查ac2147483647,b-2147483648的 D 是8589934590。C 里必须先把操作数提升到足够宽的类型再减JavaScript oracle 使用 BigInt。不要先用窄类型算坏了再给结果套一个宽类型。3. 故意制造一个“有道理”的错误变异只改一处/* 正确版本会跨过距离相等的平台。 */ while (i 1 n distance_between(a[i 1], b[t]) distance_between(a[i], b[t])) { i; }将换成不是明显的语法错误而是很容易写出的优化条件。我先用固定种子生成 1000 组每个数组内元素唯一的随机用例这个变异程序全部通过。然后枚举值域{-1,0,1}内、长度1到3的全部非降序数组共19个数组三个数组的组合为19^36859组再加10组小边界用例。被测程序用例集合本轮结果变异版本1000组无重复随机输入0次失败正确版本6859组穷举10组边界0次失败变异版本同样6869组输入843次失败第一个失败输入很小A[1,1,4], B[4], C[4]。变异版停在第一个1输出3 1 4 4而0 4 4 4才是最优解。这让失败有了原因不只是一个 WA 标签。这里还要区分“距离相等”和“重复值挡住指针”。例如A[-1,1,2], b0停在-1也没有错-1与1都已是最近值但[1,1,4], b4的两个1只是通往更好值4之前的平台。生成器只生成数组内互异值正好避开了后一类故障。843是这个固定用例集合里该变异的失败次数不是算法在所有实际输入中的“错误率”。换一个生成分布数字就可能不同不能只把随机次数加大却始终排除触发错误的条件。4. 工具本身也需要坏答案我还直接给 checker 喂了两种伪答案输入A[1,1,4], B[4], C[4] 0 99 99 99 - 元素不属于对应数组拒绝 0 1 4 4 - 声称D0但三元组实际D3拒绝这些测试检查的是“裁判有没有认真核对”不是算法有没有找到答案。除此之外编译失败、非零退出、超时应分别报告 CE、RE、TLE输入不合法应报告判题配置错误而不是怪参赛程序答错。本地实现将首个失败用例保存为failure.in同时记下种子、组别、期望值和实际输出。种子帮助追溯但原始失败输入才是不依赖生成器后续版本的证据。当前工具没有自动缩减所有反例也没有容器级隔离不能直接开放给陌生人上传执行 C 代码超时限制不等于安全沙箱。5. 我真正改变的是测试顺序现在我会先问有没有重复值有没有多解有无整数边界参考程序与待测程序是否共享同一个假设再决定随机跑多少次。这次穷举只覆盖一个很小的有限域当然不是完整正确性证明1000组随机全过也只是当前分布下未发现反例。证明说明算法为什么对测试帮助发现证明或实现哪里没覆盖两者不能互相替代。这篇的 C 正确版与变异版、oracle、checker 都来自同一轮真实执行而不是事后编造的测试数字。复现材料为experiments/2026-10-03-candidates/verify-local.mjs与原题的solution.c、problem.mjs完整独立复现文件见下方附录无需等待托管仓库。附录完整复现文件下面三个文件放在同一个新建目录用Windows上的Node.js 22与GCC运行node verify-local.mjs。GCC需在PATH中或通过BLOG_CC指定完整路径。程序只编译固定的solution.c及其严格小于变异不提供陌生代码上传执行能力不是安全沙箱。这是从原始实验中抽出的判题部分不再要求TinyCC和代理实验依赖。结果与首个失败输入写入随机run目录里的results.json首个失败对象同时包含输入、期望值和实际输出不依赖种子重建。原始完整工作台另外提供failure.in导出两者不要混淆。solution.c#include inttypes.h #include stdint.h #include stdio.h #include stdlib.h typedef struct { int64_t distance; int32_t a, b, c; } Answer; static int64_t distance_between(int32_t x, int32_t y) { int64_t delta (int64_t)x - (int64_t)y; return delta 0 ? delta : -delta; } static Answer solve(const int32_t *a, size_t n, const int32_t *b, size_t m, const int32_t *c, size_t k) { size_t i 0, j 0; Answer best {INT64_MAX, 0, 0, 0}; for (size_t t 0; t m; t) { /* Advance through ties, including duplicate elements. */ while (i 1 n distance_between(a[i 1], b[t]) distance_between(a[i], b[t])) { i; } while (j 1 k distance_between(c[j 1], b[t]) distance_between(c[j], b[t])) { j; } int64_t d distance_between(a[i], b[t]) distance_between(b[t], c[j]); if (d best.distance) best (Answer){d, a[i], b[t], c[j]}; } return best; } static int read_array(int32_t *values, size_t length) { for (size_t i 0; i length; i) { if (scanf(% SCNd32, values[i]) ! 1) return 0; if (i 0 values[i] values[i - 1]) return 0; } return 1; } int main(void) { size_t n, m, k; int count; /* A single case is valid; repeated cases support local batch checking. */ while ((count scanf(%zu%zu%zu, n, m, k)) ! EOF) { if (count ! 3 || n 0 || m 0 || k 0 || n 200000 || m 200000 || k 200000) return 1; int32_t *a malloc(n * sizeof(*a)); int32_t *b malloc(m * sizeof(*b)); int32_t *c malloc(k * sizeof(*c)); if (a NULL || b NULL || c NULL) { free(a); free(b); free(c); return 1; } if (!read_array(a, n) || !read_array(b, m) || !read_array(c, k)) { free(a); free(b); free(c); return 1; } Answer result solve(a, n, b, m, c, k); printf(% PRId64 % PRId32 % PRId32 % PRId32 \n, result.distance, result.a, result.b, result.c); free(a); free(b); free(c); } return 0; }problem.mjsimport assert from node:assert/strict; export const id three-arrays-distance; export const minimum -2147483648; export const maximum 2147483647; export function validateCase({ A, B, C }) { for (const values of [A, B, C]) { assert.ok(Array.isArray(values) values.length 0 values.length 200000, Array length out of bounds); values.forEach((x, i) { assert.ok(Number.isInteger(x) x minimum x maximum, Expected int32 element); assert.ok(i 0 || values[i - 1] x, Array must be sorted); }); } } const abs x x 0n ? -x : x; export function bruteForce({ A, B, C }) { if (A.length * B.length * C.length 2000000) throw new Error(Case too large for brute-force oracle); let best null; for (const a of A) for (const b of B) for (const c of C) { const d abs(BigInt(a) - BigInt(b)) abs(BigInt(b) - BigInt(c)); if (best null || d best) best d; } return best; } export function serialize(test) { validateCase(test); return ${test.A.length} ${test.B.length} ${test.C.length}\n${test.A.join( )}\n${test.B.join( )}\n${test.C.join( )}\n; } export function parseInput(input) { const tokens input.trim().split(/\s/); if (!input.trim()) throw new Error(Input is empty); if (!tokens.every(x /^-?\d$/.test(x))) throw new Error(Only integer tokens are allowed); let at 0; const cases []; while (at tokens.length) { const sizes tokens.slice(at, at 3).map(Number); at 3; if (sizes.length ! 3 || sizes.some(n !Number.isInteger(n) || n 1 || n 200000)) throw new Error(Invalid lengths); const values sizes.map(n { if (at n tokens.length) throw new Error(Incomplete array); const result tokens.slice(at, at n).map(Number); at n; return result; }); const test { label: custom-${cases.length 1}, A: values[0], B: values[1], C: values[2] }; validateCase(test); cases.push(test); } return cases; } export function checkAnswer(test, line, expected) { const fields line.trim().split(/\s/); if (fields.length ! 4 || fields.some(x !/^-?\d$/.test(x))) return Expected four integers: D a b c; const [d, a, b, c] fields.map(BigInt); const belongs (values, value) values.some(x BigInt(x) value); if (!belongs(test.A, a) || !belongs(test.B, b) || !belongs(test.C, c)) return Selected values do not belong to the corresponding arrays; const computed abs(a - b) abs(b - c); if (d ! computed) return Reported distance does not match selected values; if (d ! expected) return Distance is not optimal: expected ${expected}, got ${d}; return null; } function randomGenerator(seed) { let state seed 0; return () { state (state 0x6D2B79F5) 0; let x Math.imul(state ^ (state 15), 1 | state); x ^ x Math.imul(x ^ (x 7), 61 | x); return ((x ^ (x 14)) 0) / 4294967296; }; } function sortedArrays(alphabet, maxLength) { const all []; function extend(prefix, from) { if (prefix.length) all.push(prefix); if (prefix.length maxLength) return; for (let i from; i alphabet.length; i) extend([...prefix, alphabet[i]], i); } extend([], 0); return all; } export function generateCases({ seed 408, randomCount 2000, exhaustive true } {}) { const cases []; const add (label, A, B, C, expected) cases.push({ label, A, B, C, ...(expected undefined ? {} : { expected: String(expected) }) }); add(sample, [1, 4, 8], [5, 10], [2, 6, 12]); add(duplicates-block-A, [1, 1, 4], [4], [4]); add(duplicates-block-C, [4], [4], [1, 1, 4]); add(all-equal, [2, 2], [2, 2], [2, 2]); add(equal-distance, [1, 3], [2], [1, 3]); add(query-right-of-arrays, [-9, -5], [10, 10], [-7, -1]); add(query-left-of-arrays, [5, 9], [-10], [2, 8]); add(negative, [-9, -4, -1], [-5, -2], [-6, -3]); add(int32-extreme-sum, [maximum], [minimum], [maximum]); add(extreme-exact-match, [minimum, maximum], [minimum, maximum], [minimum, maximum]); if (exhaustive) { const arrays sortedArrays([-1, 0, 1], 3); for (const A of arrays) for (const B of arrays) for (const C of arrays) add(exhaustive, A, B, C); } const random randomGenerator(seed); const int max Math.floor(random() * max); for (let i 0; i randomCount; i) { const array () Array.from({ length: 1 int(12) }, () { const mode int(20); return mode 0 ? minimum : mode 1 ? maximum : int(101) - 50; }).sort((a, b) a - b); const test { A: array(), B: array(), C: array() }; add(random-${i}, test.A, test.B, test.C); if (i % 5 0) { const expected bruteForce(test); add(swap-A-C-${i}, test.C, test.B, test.A, expected); const duplicate values [...values, values[int(values.length)]].sort((a, b) a - b); add(duplicate-${i}, duplicate(test.A), duplicate(test.B), duplicate(test.C), expected); if ([...test.A, ...test.B, ...test.C].every(x x -50 x 50)) { add(translate-${i}, test.A.map(x x 17), test.B.map(x x 17), test.C.map(x x 17), expected); add(scale-${i}, test.A.map(x x * 3), test.B.map(x x * 3), test.C.map(x x * 3), expected * 3n); } } } // Large cases use a known optimum witnessed by a value shared by all arrays. add(large-shared-zero, Array(200000).fill(0), Array(200000).fill(0), Array(200000).fill(0), 0); const increasing Array.from({ length: 200000 }, (_, i) i); add(large-full-traversal, increasing, [199999], increasing, 0); return cases; }verify-local.mjsimport { readFile, writeFile, mkdir, readdir } from node:fs/promises; import { spawnSync, spawn } from node:child_process; import { once } from node:events; import { createServer } from node:http; import { fileURLToPath } from node:url; import assert from node:assert/strict; import * as problem from ./problem.mjs; const base fileURLToPath(new URL(., import.meta.url)).replaceAll(\\,/).replace(/\/$/,); const blogRoot fileURLToPath(new URL(../../, import.meta.url)).replaceAll(\\,/).replace(/\/$/,); const run ${base}/run-${Date.now()}; await mkdir(run); const evidence { run, checks: [], commands: [] }; function check(name, value) { assert.ok(value, name); evidence.checks.push(name); } function command(exe, args, cwdrun, input, envprocess.env) { const r spawnSync(exe, args, { cwd, input, env, encoding:utf8, timeout:30000, windowsHide:true }); assert.ok(!r.error, String(r.error)); const row { exe, args, cwd, status:r.status, stdout:r.stdout, stderr:r.stderr }; evidence.commands.push(row); return row; } const source await readFile(${base}/solution.c,utf8); await writeFile(${run}/good.c,source); await writeFile(${run}/strict.c,source.replaceAll( distance_between, distance_between)); const gccprocess.env.BLOG_CC || gcc; const env{...process.env}; for (const name of [good,strict]) check(${name}: compile, command(gcc,[-stdc11,-O2,-Wall,-Wextra,${run}/${name}.c,-o,${run}/${name}.exe],run,undefined,env).status0); function compare(name,cases) { const rcommand(${run}/${name}.exe,[],run,cases.map(problem.serialize).join(),env); check(${name}: normal exit,r.status0); const linesr.stdout.trim().split(/\r?\n/); assert.equal(lines.length,cases.length); const failurescases.flatMap((t,i){ const expectedproblem.bruteForce(t), reasonproblem.checkAnswer(t,lines[i],expected); return reason?[{input:t,expected:String(expected),actual:lines[i],reason}]:[]; }); return {count:cases.length,failures:failures.length,firstFailure:failures[0]}; } let state408; const random(){ state(Math.imul(state,1664525)1013904223)0; return state; }; const distinct()Array.from(new Set(Array.from({length:1random()%6},()random()%21-10))).sort((a,b)a-b); const uniqueArray.from({length:1000},()({A:distinct(),B:distinct(),C:distinct()})); evidence.uniquecompare(strict,unique); check(strict passes unique-only generator,evidence.unique.failures0); const smallproblem.generateCases({randomCount:0}).filter(tt.A.length*t.B.length*t.C.length2000000); evidence.goodcompare(good,small); evidence.strictcompare(strict,small); check(correct implementation passes small exhaustive cases,evidence.good.failures0); check(strict mutation is caught with duplicates,evidence.strict.failures0); const duplicate{A:[1,1,4],B:[4],C:[4]}; const tie{A:[1,3],B:[2],C:[1,3]}; check(checker accepts first optimal witness,problem.checkAnswer(tie,2 1 2 1,2n)null); check(checker accepts alternate optimal witness,problem.checkAnswer(tie,2 3 2 3,2n)null); check(checker rejects invented witness,Boolean(problem.checkAnswer(duplicate,0 99 99 99,0n))); check(checker rejects forged score,Boolean(problem.checkAnswer(duplicate,0 1 4 4,0n))); check(extreme score uses BigInt,problem.bruteForce({A:[2147483647],B:[-2147483648],C:[2147483647]})8589934590n); evidence.statuspassed; await writeFile(${run}/results.json,JSON.stringify(evidence,null,2)); console.log(JSON.stringify({checks:evidence.checks.length,unique:evidence.unique,good:evidence.good,strict:evidence.strict,run}));