Skip to Content
Guides

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 Index or range and the total state count is at most 2^24, @memo allocates 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 fn declared inside a function, inside a loop, or below @!multitest resets its cache automatically on every call, iteration, or test case — eliminating stale-table Wrong Answers.
  • @memo can also wrap ask(...) or an extern @grader fn so 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 typed read() bounds, read(gen: f), @gen, and @check rather than assertions.
  • debug(x, dp) — prints checkpoints during local runs, records structured snapshots in cpl run --trace and the playground's Trace button, and replays side by side when stress testing catches a failing case. cpl build omits debug(...) from the final judge C++17, so the compiler rejects any debug(...) 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 += i

Time 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.

On this page