Stress Testing — Generator, Brute Force & Comparator Scripts

June 2026 · 22 min read

You stare at the verdict: Wrong Answer on test 37. You've traced through your logic three times and everything looks correct. The samples all pass. You can't see the bug.

This is where stress testing saves you. Instead of reasoning about correctness in your head, you prove it empirically: generate thousands of random inputs, run them through both your optimized solution and a simple brute-force, and find the exact test case where they disagree. It is the single most powerful debugging technique in competitive programming.

What Is Stress Testing?

Stress testing automatically compares your solution's output against a known-correct (but slow) solution on randomly generated inputs:

1. Generate a random test case
2. Feed it to your brute-force solution (slow but certainly correct)
3. Feed the same input to your optimized solution
4. Compare the outputs — if they differ, you have the exact failing input
5. Repeat thousands of times

Most CP bugs are edge cases and off-by-one errors invisible when tracing manually. A stress test running 10,000 random inputs per second finds them within seconds.

When to Stress Test

• You get WA and can't find the bug by inspection
• Your solution is complex (multiple cases, tricky math)
• The problem has a simple brute-force you're confident in
• High penalty for wrong submissions (ICPC-style)
• You've implemented a data structure from scratch

The Three Components

A stress test consists of three programs working together through the file system or pipes:

gen.cpp takes a seed as a command-line argument and outputs a single random test case to stdout. brute.cpp reads stdin and computes the answer using the simplest possible algorithm — correctness is paramount, speed doesn't matter. sol.cpp is your actual optimized solution. The comparator loops: generate → run both → compare → stop on mismatch.

for each iteration i:
    gen i       →  input.txt
    brute       <  input.txt  →  expected.txt
    sol         <  input.txt  →  actual.txt
    diff expected.txt actual.txt
    if different: print input, stop

Writing a Random Test Generator

The generator is the most important component. It needs to produce valid, varied, and small inputs. Small inputs let the brute force run quickly and are easier to debug.

Core Random Utilities

Always use mt19937 seeded from a command-line argument for reproducibility:

#include <bits/stdc++.h>
using namespace std;

mt19937 rng;

int randint(int a, int b) {
    return uniform_int_distribution<int>(a, b)(rng);
}

string randstr(int len, char lo = 'a', char hi = 'z') {
    string s(len, ' ');
    for (char &c : s) c = lo + randint(0, hi - lo);
    return s;
}

vector<int> randperm(int n) {
    vector<int> p(n);
    iota(p.begin(), p.end(), 1);
    shuffle(p.begin(), p.end(), rng);
    return p;
}

int main(int argc, char* argv[]) {
    rng = mt19937(atoi(argv[1]));

    int n = randint(1, 10);  // small n for stress testing!
    cout << n << "\n";
    for (int i = 0; i < n; i++) {
        cout << randint(-100, 100);
        if (i + 1 < n) cout << " ";
    }
    cout << "\n";
}

Generating Random Trees

For each node i (2 ≤ i ≤ n), pick a random parent from [1, i−1]:

int n = randint(2, 12);
cout << n << "\n";
for (int i = 2; i <= n; i++) {
    int parent = randint(1, i - 1);
    cout << parent << " " << i << "\n";
}

Generating Random Connected Graphs

int n = randint(2, 8);
int m = randint(n - 1, min(n * (n - 1) / 2, n + 5));
set<pair<int,int>> edges;

// Spanning tree first to ensure connectivity
vector<int> order(n);
iota(order.begin(), order.end(), 1);
shuffle(order.begin(), order.end(), rng);
for (int i = 1; i < n; i++) {
    int u = order[randint(0, i - 1)], v = order[i];
    if (u > v) swap(u, v);
    edges.insert({u, v});
}
// Add random edges until m total
while ((int)edges.size() < m) {
    int u = randint(1, n), v = randint(1, n);
    if (u == v) continue;
    if (u > v) swap(u, v);
    edges.insert({u, v});
}

cout << n << " " << (int)edges.size() << "\n";
for (auto [u, v] : edges)
    cout << u << " " << v << "\n";

The Comparator Script

The comparator ties everything together. Here are complete, working scripts.

Bash Script (Linux / macOS)

#!/bin/bash
# stress.sh — Usage: bash stress.sh [num_tests]
set -e
NUM=${1:-10000}

echo "Compiling..."
g++ -O2 -o gen gen.cpp
g++ -O2 -o brute brute.cpp
g++ -O2 -o sol sol.cpp

for ((i = 1; i <= NUM; i++)); do
    ./gen $i > input.txt
    ./brute < input.txt > expected.txt
    ./sol   < input.txt > actual.txt

    if ! diff -q expected.txt actual.txt > /dev/null 2>&1; then
        echo "MISMATCH on test $i!"
        echo "--- Input ---";   cat input.txt
        echo "--- Expected ---"; cat expected.txt
        echo "--- Actual ---";  cat actual.txt
        exit 1
    fi
    (( i % 100 == 0 )) && echo "Passed $i tests..."
done
echo "All $NUM tests passed!"

Single-File C++ Stress Tester

For the fastest contest setup — put generator, brute force, and comparison all in one file. No shell script needed:

// stress_inline.cpp — Everything in one file
#include <bits/stdc++.h>
using namespace std;

mt19937 rng;
int randint(int a, int b) {
    return uniform_int_distribution<int>(a, b)(rng);
}

string gen(int seed) {
    rng = mt19937(seed);
    ostringstream out;
    int n = randint(1, 10);
    out << n << "\n";
    for (int i = 0; i < n; i++) {
        out << randint(1, 100);
        if (i + 1 < n) out << " ";
    }
    out << "\n";
    return out.str();
}

// Brute-force: read from stream, return answer as string
string brute(istringstream &in) {
    int n; in >> n;
    vector<int> a(n);
    for (int &x : a) in >> x;
    int ans = *max_element(a.begin(), a.end());
    ostringstream out;
    out << ans << "\n";
    return out.str();
}

// Your optimized solution (potentially buggy)
string solve(istringstream &in) {
    int n; in >> n;
    vector<int> a(n);
    for (int &x : a) in >> x;
    int ans = a[0];
    for (int i = 1; i < n; i++)
        ans = max(ans, a[i]);
    ostringstream out;
    out << ans << "\n";
    return out.str();
}

int main() {
    for (int i = 1; i <= 100000; i++) {
        string input = gen(i);
        istringstream in1(input), in2(input);
        string expected = brute(in1);
        string actual = solve(in2);
        if (expected != actual) {
            cerr << "MISMATCH on test " << i << "!\n";
            cerr << "Input:\n" << input;
            cerr << "Expected:\n" << expected;
            cerr << "Actual:\n" << actual;
            return 1;
        }
        if (i % 10000 == 0)
            cerr << "Passed " << i << " tests...\n";
    }
    cerr << "All tests passed!\n";
}

Advanced Generators

A naive generator might never produce the specific structure that triggers your bug. Here are generators for tricky input types.

Uniform Random Trees via Prüfer Sequence

The parent-based method is biased toward tall trees. For a uniform distribution over all labeled trees:

vector<pair<int,int>> prufer_tree(int n) {
    if (n <= 2) return (n == 2) ? vector<pair<int,int>>{{1,2}} : vector<pair<int,int>>{};
    // Random Prüfer sequence of length n-2
    vector<int> code(n - 2);
    for (int &x : code) x = randint(1, n);

    // Decode to edge list
    vector<int> deg(n + 1, 1);
    for (int x : code) deg[x]++;

    vector<pair<int,int>> edges;
    set<int> leaves;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 1) leaves.insert(i);

    for (int x : code) {
        int leaf = *leaves.begin();
        leaves.erase(leaves.begin());
        edges.push_back({leaf, x});
        deg[x]--;
        if (deg[x] == 1) leaves.insert(x);
    }
    vector<int> rem(leaves.begin(), leaves.end());
    edges.push_back({rem[0], rem[1]});
    return edges;
}

Trees with Controlled Shape

Target specific tree shapes to catch different bugs:

enum TreeShape { RANDOM, CHAIN, STAR, BINARY };

void gen_tree(int n, TreeShape shape) {
    cout << n << "\n";
    if (n == 1) return;
    switch (shape) {
        case CHAIN:   // 1-2-3-...-n (worst for many tree algos)
            for (int i = 2; i <= n; i++)
                cout << i - 1 << " " << i << "\n";
            break;
        case STAR:    // Node 1 connected to all others
            for (int i = 2; i <= n; i++)
                cout << 1 << " " << i << "\n";
            break;
        case BINARY:  // Complete binary tree
            for (int i = 2; i <= n; i++)
                cout << i / 2 << " " << i << "\n";
            break;
        default:      // Random tree
            for (int i = 2; i <= n; i++)
                cout << randint(1, i - 1) << " " << i << "\n";
    }
}

Constrained Random Strings

// Random palindrome of length n
string rand_palindrome(int n, int alpha = 26) {
    string s(n, ' ');
    for (int i = 0; i <= (n - 1) / 2; i++) {
        s[i] = 'a' + randint(0, alpha - 1);
        s[n - 1 - i] = s[i];
    }
    return s;
}

// Random balanced bracket sequence of length 2n
string rand_brackets(int n) {
    string s;
    int open = 0, close = 0;
    while (open + close < 2 * n) {
        if (open == n) { s += ')'; close++; }
        else if (open == close) { s += '('; open++; }
        else if (randint(0, 1)) { s += '('; open++; }
        else { s += ')'; close++; }
    }
    return s;
}

// Random string with exactly k distinct characters
string rand_k_distinct(int len, int k) {
    string s(len, ' ');
    for (int i = 0; i < k; i++) s[i] = 'a' + i;
    for (int i = k; i < len; i++) s[i] = 'a' + randint(0, k - 1);
    shuffle(s.begin(), s.end(), rng);
    return s;
}

Biased Random for Edge Cases

// Frequently generates boundary values
int biased_randint(int a, int b) {
    int r = randint(0, 9);
    if (r < 2) return a;       // 20% minimum
    if (r < 4) return b;       // 20% maximum
    if (r < 5) return (a+b)/2; // 10% midpoint
    return randint(a, b);       // 50% uniform
}

Debugging with Stress Tests

The stress test found a mismatch on test 847. Now what? The test case might still be too complex to debug easily. Here's a systematic approach.

Step 1: Reproduce and Verify

./gen 847 > fail.txt
cat fail.txt
./brute < fail.txt    # verify brute answer by hand
./sol < fail.txt      # see your wrong output

Step 2: Minimize the Test Case

Binary search on test size to find the smallest n that triggers the bug:

// minimize.cpp — Find the smallest failing n
#include <bits/stdc++.h>
using namespace std;
mt19937 rng;
int randint(int a, int b) {
    return uniform_int_distribution<int>(a, b)(rng);
}

// Paste brute() and solve() here (same as inline stress tester)

string gen_fixed_n(int n, int seed) {
    rng = mt19937(seed);
    ostringstream out;
    out << n << "\n";
    for (int i = 0; i < n; i++) {
        out << randint(1, 100);
        if (i + 1 < n) out << " ";
    }
    out << "\n";
    return out.str();
}

int main() {
    for (int n = 1; n <= 20; n++) {
        for (int seed = 1; seed <= 100000; seed++) {
            string input = gen_fixed_n(n, seed);
            istringstream in1(input), in2(input);
            if (brute(in1) != solve(in2)) {
                cerr << "FAIL at n=" << n << " seed=" << seed << "\n";
                cerr << "Input:\n" << input;
                return 1;
            }
        }
        cerr << "n=" << n << " OK\n";
    }
}

Step 3: Categorize the Bug

Step 4: Debug with Trace Output

// Debug macros — compile with g++ -O2 -DLOCAL sol.cpp
#ifdef LOCAL
#define dbg(x) cerr << #x << " = " << (x) << "\n"
#define dbg_arr(a, n) { cerr << #a << " = ["; \
    for(int _i=0;_i<(n);_i++) cerr<<(a)[_i]<<(_i+1<(n)?", ":""); \
    cerr<<"]\n"; }
#else
#define dbg(x)
#define dbg_arr(a, n)
#endif

// Usage:
dbg(n);            // prints: n = 5
dbg(dp[i][j]);     // prints: dp[i][j] = 42
dbg_arr(a, n);     // prints: a = [3, 1, 4, 1, 5]

Stress Testing During Contests

Stress testing during a live contest is a calculated gamble: it takes time to set up, but can save you from 30+ minutes of fruitless manual debugging.

The 2-Minute Setup

1. Copy your solution to sol.cpp
2. Write brute.cpp — simplest possible O(n²) or O(2ⁿ) approach
3. Write gen.cpp — adapt the template for the input format, keep n ≤ 15
4. Run the one-liner and wait for a mismatch

Pre-prepare these minimal template files in your contest directory:

// gen.cpp — Quick-start, just fill in main()
#include <bits/stdc++.h>
using namespace std;
mt19937 rng;
int R(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
int main(int argc, char** argv) {
    rng = mt19937(atoi(argv[1]));
    int n = R(1, 10);
    cout << n << "\n";
    for (int i = 0; i < n; i++)
        cout << R(1, 100) << " \n"[i==n-1];
}

When Is It Worth the Time?

Contest Checklist

• ✓ Brute force passes all sample inputs
• ✓ Generator output matches input format exactly
• ✓ Test sizes small enough for brute force (n ≤ 15)
• ✓ Right indexing (1-indexed vs 0-indexed)
• ✓ Special values covered: n=1, all equal, sorted, reverse sorted

for((i=1;;i++));do ./g $i>in;./be;./sa;diff -q e a>/dev/null||{ echo "FAIL $i";cat in e a;break;};((i%500==0))&&echo $i;done