Memoization, stress testing & Trace
@memo caching, @alt/@check/@interactor verification, and the visual Trace debugger.
Contest bugs rarely come from the algorithm idea — they come from an edge case you did not construct by hand. CP Lang puts memoization, input generators, brute-force oracles, constructive checkers, and local interactors right inside the same .cp file, then strips all verification code automatically when cpl build emits your submission.
Memoization with @memo
Annotate a pure recursive function with @memo to cache its results over any Index or range parameter tuple:
domain V = 0..20
@memo
fn dp(u: V, used: Bool) -> Int:
if u == V(0): return if used: 1 else: 0
let prev = u.prev!
dp(prev, false) + dp(prev, true)
print(dp(V(19), true))Bare @memo chooses its storage layout automatically (@memo(into: table) exposes a dense table when you want explicit control):
- When every parameter is an algebraic
Indexor range and the total state count is at most2^24,@memoallocates a flat contiguous dense table with zero hashing overhead. - Larger state spaces fall back automatically to a per-process salted open-addressed hash table.
- A
@memo fndeclared inside a function, inside a loop, or below@!multitestresets its cache automatically on every call, iteration, or test case — eliminating stale-table Wrong Answers. @memocan also wrapask(...)or an extern@grader fnso repeated queries with the same arguments cost only one judge query.- If you want manual hash storage instead, declare
var dp = HashMap<Key, Val>().
Try a live cached @memo DP in the playground. Here is a small recursive recurrence you can run directly:
let n: 1..=20 = read()
// Small linear recurrence (see memo_dp.cp for cached @memo DP).
fn f(i: Int) -> Int:
if i == 0:
return 1
f(i - 1) * 3 + i
print(f(n - 1))For input 4, f(3) evaluates to 45.
Assertions and debug
There is one assertion keyword, so a sanity check is never silently stripped in release mode:
assert cond— checked in both local runs and compiled C++17, and also informs range and disjointness checks. Input constraints belong in typedread()bounds,read(gen: f),@gen, and@checkrather than assertions.debug(x, dp)— prints checkpoints during local runs, records structured snapshots incpl run --traceand the playground's Trace button, and replays side by side when stress testing catches a failing case.cpl buildomitsdebug(...)from the final judge C++17, so the compiler rejects anydebug(...)expression that mutates program state (E0312).
Co-located @alt, @check, @interactor, and @gen
Write your slow reference, constructive validator, or interactive judge in the same file as your solution:
let n: 1..=1000 = read()
let a: [0..n]Int = read()
print(a.sum())
@gen
fn make_case(size: Int):
let n = rand(1, size)
print(n)
print([rand(-10, 10) for _ in 0..n])
@alt(main)
fn slow():
var total = 0
for x in a: total += x
print(total)
@check
fn check():
let ans: Int = read_output()
assert ans == a.sum()This complete sum program uses print() inside @gen to produce test input. For an interactive program, use the separate @interactor example in the stress guide; do not combine its protocol with the sum program. Any program that calls ask(...) flushes every print(...) automatically. Every generator draws from a replayable choice stream, enabling automatic structure-aware shrinking of failing tests without writing a custom shrinker.
Pattern and DP structure discovery (std.spec)
When you have a slow @alt solution and want to check whether a sequence obeys a linear recurrence or whether a DP transition satisfies monotonicity, convexity (Aliens/WQS), or the quadrangle inequality (Knuth / divide-and-conquer DP), std.spec and local spec helpers let you test hypotheses empirically on small inputs before writing the fast algorithm:
@memo
fn tilings(n: 0..=12) -> Int:
if n == 0: return 1
if n % 2 == 1: return 0
if n == 2: return 3
4 * tilings(n - 2) - tilings(n - 4)
let small = [tilings(n) for n in 0..12]
for n in 4..12:
assert small[n] == 4 * small[n - 2] - small[n - 4]
print("a[n] = 4 a[n-2] - a[n-4] holds on 0..12")Visual debugging with Trace
Every run in the playground has a Trace button that records every top-level variable change, every print, and every debug(...) call — and runs @alt(main) side by side when the file defines one — then opens the interactive trace viewer.
You can inspect arrays, 2D DP tables, grids, trees, and graphs step by step, scrub backward and forward through execution, and pinpoint the exact step where your fast solution diverges from @alt(main).
Profiling with cpl profile
cpl profile a.cp input.txt runs the program and prints every source line with how many times it ran and its share of the time:
profile of a.cp (interpreter): 1.2 ms
line hits time %
3 1 2.1 us 0% for i in 0..n:
4 1000000 612.0 us 51% s += iTime spent in library code is charged to the line that called it. --native profiles the C++ of cpl build instead, compiled with g++ -O2 and a counter at each statement: the hit counts are the interpreter's, and the times are what the judge sees. --format json gives the same numbers to scripts.
Coverage with cpl cover
cpl cover a.cp runs the program on every case in a.tests/ (or the inputs you name; a directory stands for its .in files) and lists the lines no input reached and every if that went only one way. A sample set that never takes a branch is a test set that cannot catch a bug there.