iv. Debugging and Stress Testing

Most lost contests come from bugs you could not see, not from algorithms you did not know. What works: sanitizers, a stress test, and a fixed checklist, used in that order.

Compile flags

g++ -std=c++20 -O2 -DLOCAL -Wall -Wextra -Wshadow -Wconversion \
    -fsanitize=address,undefined -fno-sanitize-recover -D_GLIBCXX_DEBUG -g sol.cpp -o sol

Flag	Catches
`-fsanitize=address`	out-of-bounds, use-after-free, stack overflow, with the exact line
`-fsanitize=undefined`	signed overflow, shifts $\geq$ width, null deref, misaligned access
`-D_GLIBCXX_DEBUG`	`vector[i]` out of range, invalid iterators, non-strict comparators
`-Wshadow`	an inner `i` or `n` shadowing the outer one
`-Wall -Wextra`	uninitialized variables, missing returns, signed/unsigned comparisons

Turning on sanitizers usually finds the cause of an RE or WA in under a minute. Keep this alias as your default local build.

Debug macro

#ifdef LOCAL
template<class T> void _p(const T& x);
void _p(const string& s) { cerr << '"' << s << '"'; }
void _p(char c) { cerr << '\'' << c << '\''; }
template<class A, class B> void _p(const pair<A, B>& p) { cerr << '('; _p(p.first); cerr << ", "; _p(p.second); cerr << ')'; }
template<class T> void _p(const T& x) {
    if constexpr (requires { x.begin(); }) { cerr << '{'; bool f = 1; for (auto& e : x) { if (!f) cerr << ", "; f = 0; _p(e); } cerr << '}'; }
    else cerr << x;
}
void _print() { cerr << '\n'; }
template<class T, class... V> void _print(const T& t, const V&... v) { _p(t); if (sizeof...(v)) cerr << ", "; _print(v...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "] = ", _print(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

It prints any nested container, for example dbg(g, dist). Output goes to cerr, which the judge ignores, but it still costs time on big outputs.

assert is cheap and turns a silent WA into an RE at the exact place where an invariant breaks. Leave asserts in unless they sit in the hottest loop.

Stress testing

You need three programs: sol (fast), brute (obviously correct, exponential is fine), and gen (random small tests seeded by argv[1]).

// gen.cpp
int main(int argc, char** argv) {
    mt19937 rng(atoi(argv[1]));
    auto r = [&](int l, int h) { return int(rng() % (h - l + 1)) + l; };
    int n = r(1, 8);
    cout << n << '\n';
    for (int i = 0; i < n; i++) cout << r(1, 10) << " \n"[i == n - 1];
}

for ((i = 1; ; i++)); do
    ./gen $i > in; ./sol < in > o1; ./brute < in > o2
    if ! cmp -s o1 o2; then echo "seed $i"; cat in; echo "got:"; cat o1; echo "want:"; cat o2; break; fi
done

Keep the tests tiny. With $n \leq 8$ and values $\leq 10$ , a bug that appears at $n = 1 0^{5}$ almost always appears at $n = 6$ , and a 6-element case can be traced by hand. Large random tests find bugs you then can’t diagnose.
Vary the generator’s shape: many duplicates (values in $[1, 3]$ ), sorted, all equal, a path, a star, a disconnected graph, $n = 1$ .
Several valid answers: write a checker that validates the output and compares only the score with the brute force.
No brute force: write a second, different solution (two different wrong solutions rarely agree), a validator for constructive output, assert the invariants inside the solution, compare against a slow exact DP on tiny $n$ (optimisation problems), or brute-force by enumerating all $2^{n}$ / $n!$ possibilities (counting problems).
Shrink the failing case: drop one element or decrease one value at a time, keeping the change while it still fails.
TLE hunting: build worst cases on purpose: maximum $n$ , path graph (recursion depth), star (degree), all-equal (amortized structures), sorted (naive quicksort or BST), anti-hash input, and grids that break SPFA.

Verdict to likely cause

Verdict	Look at
WA on test 1	misread statement, output format, wrong test-case loop
WA on a later test	edge cases. Stress test
WA only on big tests	overflow, uncleared globals, wrong array size
WA on test 2+ in multitest	state not reset between tests
TLE	complexity, `endl`, slow I/O, `map` in hot loop, per-test `memset` of MAXN
TLE on one test	adversarial worst case: SPFA, hash, recursion
MLE	`ll` table, `vector<vector>` overhead, persistent nodes, recursion
RE	out of bounds, division by zero, stack overflow, failed assert, bad comparator
Idleness limit	did not flush (interactive)
PE	spaces, newlines, `YES` vs `Yes`

The checklist before submitting

All samples pass, including the ones in the notes section.
Edge cases: $n = 1$ , $n = 0$ if allowed, all equal, all negative, max values, disconnected, impossible answer.
long long wherever a product or sum can exceed $2 \cdot 1 0^{9}$ . Any int * int?
Modulus after every + and *; subtraction normalised: (a - b + M) % M.
Globals and per-test structures reset (only the used part).
Indexing consistent; arrays sized n + 1 where needed.
Recursion depth fine for a path of length $n$ .
Output format: precision, separators, -1 sentinel, case labels.
Complexity and memory checked against the true worst case.

Topic-specific traps

Area	Trap
Binary search	predicate not monotone; bounds don’t contain the answer; `(l + r) / 2` with negative bounds rounds toward zero (use `l + (r - l) / 2` or `>> 1`)
Real binary search	`while (r - l > eps)` can loop forever at $1 0^{18}$ ; use a fixed count (100 iterations)
Dijkstra	silently wrong with negative edges; forgetting the stale-entry check makes it $O (E^{2})$ in bad cases
Bridges	skip the parent edge id, not the parent vertex, or parallel edges break it
Directed cycle detection	needs three colours
0/1 knapsack	weights loop downward (upward is the unbounded knapsack)
Coin change	coins outer gives combinations; amount outer gives permutations
DP	unreachable states must be $\pm \infty$ , not 0
Hashing	fixed base and mod $1 0^{9} + 7$ is hackable; use a random base mod $2^{61} - 1$
Rollback DSU	path compression breaks rollback
Mo’s algorithm	expand before shrinking, or the window can go negative
Point in polygon	half-open $y$ ranges at vertices
Geometry	`acos` of $1 + 1 0^{- 16}$ is NaN, so clamp; prefer `atan2(cross, dot)`
Floating output	`-0.000000`: add `0.0` or clamp near zero
`__builtin_clz(0)`	undefined

When stuck

Re-read the statement, especially what the samples say that the text doesn’t.
Explain the algorithm out loud, line by line. The bug usually shows up mid-sentence.
Print intermediate state for the smallest failing case and compare with a hand trace.
Suspect the “obviously correct” parts: input reading, the reset between tests, the output.
Two WAs on the same idea: stop resubmitting tweaks and stress test.
For anything longer than a few minutes, a real debugger (gdb, or the IDE’s) beats print statements — a watchpoint on the variable that goes wrong finds the write directly. Print debugging wins on speed of setup, not on power.

Checklists by topic

Narrower than the general checklist above: the questions specific to each problem shape, worth running through once the general checklist passes and the bug is still there.

Graph	DP	Binary search	Geometry
Directed or undirected?	What exactly is the state — complete and minimal?	Predicate defined precisely	Integers wherever possible; squared distances for comparisons
Weighted, unweighted, negative weights?	Transitions acyclic (valid evaluation order)?	Monotone — verify against a brute force if unsure	One epsilon, scaled to the coordinate magnitude
Connected or multiple components?	Unreachable states $\pm \infty$ , not 0?	Bounds provably contain the answer	Degenerate cases: collinear, duplicate points, $n \leq 2$ , zero-length segments
Self-loops or parallel edges?	Modulus required?	First-true or last-true chosen deliberately	Orientation convention fixed (CCW positive), polygons normalised
Tree, DAG, bipartite, or general?	Max, min, count, or probability — order matters (over/under-counting)?	Real-valued search uses a fixed iteration count, not an epsilon	Cross products checked for overflow
Is $n$ or $m$ the binding constraint?	Knapsack: weight loop downward for 0/1, upward for unbounded; coins outside for combinations, amount outside for permutations	—	—
—	Can the state be compressed? Memory within limits?	—	—

whoashish's cp notes

Directory