Stress Testing

The single most reliable way to find a wrong answer you cannot see. Three files and a loop.

The setup

File	Role
main.cpp	the fast solution you believe is right
brute.cpp	an obviously-correct exponential solution
gen.cpp	a random small test generator

Run them against each other until the outputs differ, then look at the tiny failing case.

The generator

#include <bits/stdc++.h>
using namespace std;
int main(int argc, char** argv) {
    mt19937_64 rng(atoll(argv[1]));                 // seed from the command line
    auto rnd = [&](long long l, long long r) {
        return (long long)(rng() % (r - l + 1)) + l;
    };
    int n = rnd(1, 8);                              // KEEP IT SMALL
    printf("%d\n", n);
    for (int i = 0; i < n; i++) printf("%lld ", rnd(1, 10));
    printf("\n");
}

Small tests, always

$n\le 8$ and values $\le 10$. A bug that only appears at $n=10^5$ almost always also appears at $n=6$, and a 6-element counterexample can be traced by hand. Large random tests find bugs you cannot then diagnose.

The runner — bash

#!/usr/bin/env bash
g++ -O2 -o main main.cpp && g++ -O2 -o brute brute.cpp && g++ -O2 -o gen gen.cpp || exit 1
for ((i = 1; ; i++)); do
    ./gen $i > in.txt
    ./main  < in.txt > out1.txt
    ./brute < in.txt > out2.txt
    if ! diff -qbw out1.txt out2.txt > /dev/null; then
        echo "FAILED on test $i"; cat in.txt
        echo "--- got ---";      cat out1.txt
        echo "--- expected ---"; cat out2.txt
        break
    fi
    echo -ne "passed $i\r"
done

The runner — Windows batch

@echo off
for /L %%i in (1,1,10000) do (
    gen.exe %%i > in.txt
    main.exe  < in.txt > out1.txt
    brute.exe < in.txt > out2.txt
    fc out1.txt out2.txt > nul || (echo FAILED on %%i & type in.txt & exit /b)
    echo test %%i
)

Multiple valid answers

diff fails when any of several outputs is acceptable — “print any valid path”, “any optimal matching”. Write a checker instead: it reads the input and your output and verifies the answer is valid and its score matches the brute force’s.

// checker.cpp:  ./checker in.txt out1.txt out2.txt  ->  exit 0 if out1 is acceptable

For optimisation problems, checking only that the score matches is usually enough and much easier to write.

Stress testing for TLE

The same harness with a large generator and time finds performance problems:

./gen_big > in.txt
time ./main < in.txt > /dev/null

Construct the worst case deliberately rather than randomly: sorted input for quicksort, a star graph for tree algorithms, all-equal values for a segment tree with amortised bounds, anti-hash strings for hashing. Random tests rarely hit the adversarial case.

When there is no brute force

Sometimes the problem has no obvious slow-but-correct solution. Alternatives:

Situation	Substitute for a brute force
Constructive output	a validator that checks the constraints hold
Optimisation	compare against a slow exact DP on tiny $n$
Two independent solutions	write the problem twice, differently, and diff them
Invariants known	assert them inside the fast solution
Counting	brute-force by enumerating all $2^n$ or $n!$ possibilities

The two-independent-implementations trick is the fallback when no brute force exists: two different wrong solutions rarely agree.

Why it works

A stress test converts “my solution is wrong somewhere” — an unbounded search — into a concrete 6-element input you can trace by hand in two minutes. It is nearly always faster than re-reading the code, and it is the difference between fixing a bug in five minutes and losing the contest to it.

See also: Debugging · Debug Macros · Contest Checklist