Debugging and Stress Testing

Stress testing — the most valuable habit

Compare a fast solution against a brute force on many small random inputs. It finds wrong answers in seconds that would otherwise cost a contest.

#!/bin/bash
for i in $(seq 1 100000); do
    ./gen $i > in.txt
    ./brute < in.txt > out1.txt
    ./fast  < in.txt > out2.txt
    if ! diff -q out1.txt out2.txt > /dev/null; then
        echo "FAIL on seed $i"
        cat in.txt
        break
    fi
done

// gen.cpp — a generator seeded from argv[1]
int main(int argc, char** argv) {
    srand(atoi(argv[1]));
    int n = rand() % 8 + 1;                       // SMALL
    printf("%d\n", n);
    for (int i = 0; i < n; i++) printf("%d ", rand() % 10 + 1);
}

Keep the random inputs tiny. $n\le 8$ with values $\le 10$ finds bugs faster than large inputs, and the failing case is small enough to read.

When the outputs may legitimately differ (multiple valid answers), write a checker that validates the fast solution’s output instead of comparing.

Finding the failing case

Once a failure is found, shrink it: repeatedly try removing an element or reducing a value, keeping the change if the test still fails. A three-line loop does this and usually reduces a 20-element case to 3.

Compiler flags — turn them on

g++ -std=c++17 -O2 -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
-fsanitize=undefined	signed overflow, bad shifts, null deref
-D_GLIBCXX_DEBUG	STL misuse — invalid iterators, bad comparators
-Wall -Wextra	uninitialised variables, unused results
-Wshadow	a local shadowing a global (a classic silent bug)
-Wconversion	implicit narrowing

-D_GLIBCXX_DEBUG catches the “comparator is not a strict weak ordering” crash with a clear message instead of a segfault. Use these locally; they are too slow for submission.

Debug printing

#ifdef LOCAL
#define dbg(x) cerr << #x << " = " << (x) << endl
#else
#define dbg(x)
#endif

Compile locally with -DLOCAL. Printing to cerr keeps the output stream clean, so you can leave the statements in while testing against a judge’s sample.

A variadic version that prints containers is worth having in your template.

Assertions

assert(0 <= i && i < n);
assert(cur >= 0);

Cheap, and they turn a silent wrong answer into an obvious runtime error. On most judges a failed assertion reports as RE rather than WA, which tells you where the problem is. Leave them in unless they are in the hottest loop.

The systematic checklist

When something fails and you do not know why:

1. Re-read the statement. Especially the output format and the constraints.
2. Test the samples, including any in the notes.
3. Test the edges: $n=0$, $n=1$, all equal, all negative, maximum values, disconnected input.
4. Check for overflow — is any int multiplied?
5. Check the modulus — applied after every operation?
6. Check globals — cleared between test cases?
7. Check indexing — 0-based or 1-based, consistently?
8. Stress test against a brute force.
9. Print intermediate state for the smallest failing case.
10. Explain the algorithm out loud. The error usually surfaces mid-sentence.

Verdict → likely cause

Verdict	Look at
WA on test 1	misread the statement, or the output format
WA on a later test	an edge case; stress test
WA only on large tests	overflow, or an uncleared global
TLE	complexity, or slow I/O (sync_with_stdio)
TLE on one test	a worst case for your algorithm (SPFA, hashing, quicksort)
MLE	array size, or a recursion-heavy structure
RE	out of bounds, division by zero, stack overflow, failed assert
RE on deep input	recursion depth
Idleness limit (interactive)	forgot to flush
Presentation error	trailing spaces, missing newline

Interactive problems

cout << "? " << x << endl;                     // endl FLUSHES
// or: cout << "? " << x << "\n" << flush;
cin >> response;

Flush after every query. Forgetting is the single most common cause of an idleness-limit verdict. Write a local interactor to test against.

Performance debugging

Symptom	Check
Slow, right complexity	I/O, endl, unordered_map, map where a vector would do
A hot inner loop	cache locality — iterate the last index innermost
Slow recursion	convert to iteration, or add memoization
Slow modular arithmetic	reduce lazily; avoid % in the innermost loop
Slow allocation	preallocate; avoid push_back in hot paths

Profile by timing sections with chrono rather than guessing — the bottleneck is frequently not where it feels like it is.

See also: Common Pitfalls · Contest Checklist · Constant Factor Optimization