Randomized Stress Testing for Oracle–Solution Mismatch Detection

Good to see you again. In the previous lesson, you built the first essential component of a stress-testing setup: a deliberately simple brute-force oracle that enumerates the specification’s full small-input search space. Its role is to provide a trustworthy answer, not to meet the original constraints.

Now we add the other two components: a legal random-test generator and an automated comparison loop. By the end of this lesson, you should be able to run thousands of small tests, stop on the first disagreement between oracle and optimized code, reproduce that disagreement, and reduce it to a useful debugging target. This is one of the highest-leverage habits for moving beyond recurring Wrong Answers on Codeforces problems.

Plan for roughly 40 minutes: about 12 minutes of video, then the rest implementing and adapting the stress-testing workflow.

---

The stress-testing contract

A randomized stress test has three programs or components:

1. Generator: produces a small, valid input.
2. Oracle: returns the correct result for that input, usually by brute force.
3. Fast solution: returns the result produced by your intended contest algorithm.

For each generated input $x$, compare:

$$B(x)$$

with

$$F(x),$$

where $B$ is the brute-force oracle and $F$ is the optimized solution.

A mismatch,

$$B(x)\ne F(x),$$

means you have found a concrete counterexample to the claim that the two implementations agree on all legal inputs. That is valuable because “my solution gets Wrong Answer somewhere” becomes:

• this exact input;
• this exact expected output;
• this exact output from the fast code.

It does not automatically prove that the optimized code is wrong. The oracle, generator, or comparison rule could be defective too. But if you have manually sanity-checked the oracle, the fast code is the likely place to investigate.

The basic loop is conceptually simple:

1. Choose a reproducible seed.
2. Generate one legal small test case.
3. Run both implementations on exactly that test case.
4. Compare the required outputs.
5. Stop immediately on the first mismatch and preserve everything needed to replay it.

Stopping matters. A thousand failures are less useful than one small failure you can understand.

---

Watch the complete workflow once

The following segment uses a small example to demonstrate the practical workflow: generate inputs, use a seed, run both programs, compare outputs, and make counterexamples easier to inspect.

The central practical point is that random testing is not “throw large data at the code.” It is a search for a small legal witness of failure.

---

A compact in-process stress harness

For many algorithmic bugs, the fastest setup is an in-process harness: write the oracle and fast solution as separate functions, generate a test case in memory, and compare their returned values directly.

This is especially convenient while developing a solution. It removes file handling and formatting from the debugging loop, so you can focus on the algorithm.

Consider maximum subarray sum, where the subarray must be nonempty. The deliberately buggy fast implementation below initializes best to zero, incorrectly allowing an imaginary empty subarray to beat every negative subarray.

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

using ll = long long;

ll bruteMaxSubarray(const vector<ll>& a) {
    ll best = LLONG_MIN;

    for (int l = 0; l < (int)a.size(); ++l) {
        ll sum = 0;
        for (int r = l; r < (int)a.size(); ++r) {
            sum += a[r];
            best = max(best, sum);
        }
    }

    return best;
}

// Deliberately buggy for all-negative arrays.
ll fastMaxSubarray(const vector<ll>& a) {
    ll best = 0;
    ll cur = 0;

    for (ll x : a) {
        cur = max(x, cur + x);
        best = max(best, cur);
    }

    return best;
}

vector<ll> generateCase(mt19937_64& rng) {
    int n = uniform_int_distribution<int>(1, 8)(rng);
    int kind = uniform_int_distribution<int>(0, 3)(rng);

    vector<ll> a(n);

    if (kind == 0) {
        // Target the all-negative family.
        for (int i = 0; i < n; ++i) {
            a[i] = -uniform_int_distribution<int>(1, 10)(rng);
        }
    } else if (kind == 1) {
        // Small values create many duplicates and ties.
        for (int i = 0; i < n; ++i) {
            a[i] = uniform_int_distribution<int>(-2, 2)(rng);
        }
    } else if (kind == 2) {
        // General mixed-sign arrays.
        for (int i = 0; i < n; ++i) {
            a[i] = uniform_int_distribution<int>(-10, 10)(rng);
        }
    } else {
        // All values equal.
        ll x = uniform_int_distribution<int>(-10, 10)(rng);
        fill(a.begin(), a.end(), x);
    }

    return a;
}

void printCase(const vector<ll>& a) {
    cout << a.size() << '\n';
    for (ll x : a) {
        cout << x << ' ';
    }
    cout << '\n';
}

int main(int argc, char** argv) {
    uint64_t seed;

    if (argc >= 2) {
        seed = stoull(argv[1]);
    } else {
        seed = chrono::steady_clock::now().time_since_epoch().count();
    }

    mt19937_64 rng(seed);

    for (uint64_t iteration = 1; ; ++iteration) {
        vector<ll> a = generateCase(rng);

        ll expected = bruteMaxSubarray(a);
        ll actual = fastMaxSubarray(a);

        if (expected != actual) {
            cout << "Mismatch found\n";
            cout << "Seed: " << seed << '\n';
            cout << "Iteration: " << iteration << '\n';
            cout << "Input:\n";
            printCase(a);
            cout << "Oracle: " << expected << '\n';
            cout << "Fast: " << actual << '\n';
            return 0;
        }
    }
}

Compile and run it with an explicit seed:

g++ -std=c++17 -O2 -Wall stress.cpp -o stress
./stress 1531

The failure should occur quickly because the generator deliberately includes all-negative arrays. For an array such as $[-3,-5]$, the correct answer is $-3$, but the buggy function reports $0$.

Two habits in this template matter far more than the particular random-number syntax:

• Print the seed and the full failing input. The input is sufficient for debugging; the seed makes it possible to replay the full generator sequence.
• Use the same generated object for both functions. Neither version gets a slightly different random case.

What this version tests, and what it does not

An in-process harness is excellent for checking algorithmic logic and most implementation details. However, it usually does not independently test your parsing and output formatting, because both functions receive already-parsed data.

For a final local check of a contest submission, use separate executables as well. Then your optimized solution is run exactly as the judge will run it: reading input from standard input and writing output to standard output.

---

The generator is a test-design problem

A weak generator can run for millions of cases while never producing the structure that breaks your solution. Treat generator design as seriously as you treated the oracle’s search space.

Every generator must satisfy two conditions:

Requirement	Meaning
Legality	Every emitted case follows every condition in the problem statement.
Coverage of patterns	The distribution deliberately includes structures likely to expose wrong assumptions.

For example, if a statement requires a connected simple graph, an arbitrary set of random edges is not a valid generator. If an array must be a permutation, duplicates are invalid. If a task allows negative values, a generator that only emits positive values has silently removed an important part of the input domain.

Why small inputs are often better

Your oracle imposes a small-input limit anyway, but small cases are also better debugging targets.

Suppose an algorithm fails on a path-shaped tree. A completely random tree with thousands of vertices is extraordinarily unlikely to be a path. A generator that sometimes explicitly makes a path of size $2$ through $10$ will find that family immediately.

Likewise, many bugs appear most clearly on:

• minimum valid size;
• one-element or two-element structures;
• all equal values;
• strictly increasing or decreasing arrays;
• duplicate-heavy cases;
• all-negative or all-positive values;
• alternating patterns;
• values at numerical boundaries;
• exactly one special item, edge, or transition;
• a condition that is just barely feasible or just barely infeasible.

The earlier maximum-subarray generator used four modes rather than one uniform distribution. That is intentional. Uniform random values are useful, but they do not reliably hit semantic categories such as “all negative” or “every value is equal.”

A useful generator pattern is:

int kind = uniform_int_distribution<int>(0, 4)(rng);

if (kind == 0) {
    // Minimum-size or boundary family.
} else if (kind == 1) {
    // Structured adversarial family.
} else if (kind == 2) {
    // Duplicate-heavy or tie-heavy family.
} else {
    // Broad random legal family.
}

The exact categories should come from your solution’s assumptions. If you use a two-pointer argument, generate cases near the point where the window condition changes. If you use sorting, generate duplicates and equal keys. If you rely on graph connectivity, generate paths, stars, disconnected graphs only if they are permitted, and dense small graphs where allowed.

---

External stress testing: test the actual submission programs

For Codeforces-style development, it is common to keep three files:

• gen.cpp: emits one valid test input;
• brute.cpp: the trusted oracle;
• fast.cpp: the optimized solution you intend to submit.

The following shell script runs them repeatedly. It assumes that gen accepts a seed as its first command-line argument.

#!/usr/bin/env bash

seed=1

while true; do
    ./gen "$seed" > input.txt

    ./fast < input.txt > fast.out
    fast_status=$?

    if [ "$fast_status" -ne 0 ]; then
        echo "Fast solution crashed on seed $seed"
        cat input.txt
        break
    fi

    ./brute < input.txt > brute.out
    brute_status=$?

    if [ "$brute_status" -ne 0 ]; then
        echo "Oracle crashed on seed $seed"
        cat input.txt
        break
    fi

    if ! diff -w fast.out brute.out > /dev/null; then
        echo "Mismatch on seed $seed"
        echo "Input:"
        cat input.txt
        echo
        echo "Fast output:"
        cat fast.out
        echo
        echo "Oracle output:"
        cat brute.out
        break
    fi

    seed=$((seed + 1))
done

The diff -w comparison ignores whitespace differences. That is appropriate when the judge treats output as whitespace-separated tokens, as most standard numerical-output problems do. Do not use a loose comparison merely to make failures disappear:

• If order matters, preserve order.
• If the output is a string where spaces are meaningful, compare exactly.
• If the problem accepts multiple valid witnesses, raw text comparison is often the wrong test.

For a multiple-witness problem, compare the required property instead. For example, verify that the fast solution’s proposed set is valid and has the same optimal score as the oracle. The oracle may choose indices $\{1,4\}$, while the fast solution chooses $\{2,3\}$; different text can still represent two correct answers.

---

Preserve, replay, and shrink the failure

Finding a mismatch is the beginning of debugging, not the end.

1. Freeze the counterexample

Immediately save:

• the exact input;
• the seed;
• the iteration number, if one seed generates many cases;
• both outputs;
• the source version or Git commit, if you use version control.

Do not continue modifying code while relying on a failure that you cannot reproduce.

First, run both programs manually on the saved input. Confirm that the mismatch is stable.

2. Identify the first plausible failure hypothesis

Avoid changing several things at once. Read the input and formulate one hypothesis:

• “My code treated an empty choice as legal.”
• “I used $0$-based indices in one location and $1$-based indices in another.”
• “I discarded duplicate values while the task distinguishes positions.”
• “The answer overflows int but not long long.”
• “My greedy choice is not safe when two values tie.”
• “The generator permits an invalid input.”
• “The brute-force interpretation differs from the statement.”

Then inspect precisely the code path related to that hypothesis.

For the maximum-subarray example, the failure family is all-negative arrays. The immediate hypothesis is that the fast code has accidentally allowed the empty subarray. best = 0 confirms it.

3. Reduce the input

A random failing test is often larger than necessary. Shrinking it turns a confusing failure into a proof-quality counterexample.

For arrays or strings, try these operations one at a time:

1. Delete a contiguous block.
2. Delete individual elements.
3. Replace values with smaller-magnitude values.
4. Replace several values with one repeated value.
5. Move values toward boundary values such as $0$, $1$, $-1$, or the constraint limits.

After every edit, rerun both implementations. Keep the edit only if the mismatch remains.

For graphs, trees, and permutations, reduction must preserve validity. You cannot delete an arbitrary tree edge and still call the result a valid tree. Instead, remove a leaf, relabel consistently, or regenerate a smaller object of the same structural family.

The target is not necessarily the mathematically smallest counterexample. It is a counterexample small enough that you can trace both programs by hand.

For the example above, reduction reaches:

1
-3

The oracle returns $-3$; the buggy fast code returns $0$. There is no longer any ambiguity about the semantic error.

---

Interpreting “no mismatch found”

Passing many stress tests is evidence, not a correctness proof. It tells you that your solution agrees with the oracle on the part of the legal input space your generator sampled.

If no mismatch appears, ask what your setup might be missing:

Symptom	Likely next check
Small random tests pass, judge fails on large tests	Overflow, asymptotic issue, recursion depth, memory, or large-coordinate behavior
Random tests pass but a known edge family is untested	Add a targeted generator mode
A failure cannot be replayed from the same seed	Hidden nondeterminism, undefined behavior, time-based randomness, or incomplete logging
The oracle times out or crashes	Reduce generator bounds or fix the oracle before trusting results
Outputs differ only for multiple valid constructions	Replace raw comparison with a validity-and-score checker
Both programs agree but your proof has a gap	Return to the proof; shared agreement cannot establish a false criterion

For runtime errors and memory bugs, compile a local debugging build with warnings and sanitizers when available. Stress testing can repeatedly trigger the problematic input, while sanitizers can identify out-of-bounds access or other undefined behavior at the moment it occurs.

---

A contest-ready stress-testing routine

Use this routine during upsolving first, then bring it into contests selectively when a problem has a feasible small oracle.

1. Write the fast solution and a concise proof idea.
2. Build the oracle from the statement, independently of the fast logic.
3. Hand-check the oracle on tiny cases.
4. Set the generator’s bounds according to the oracle, not the original constraints.
5. Add both random and structured legal case families.
6. Run a seeded comparison loop.
7. Stop at the first mismatch and save the input.
8. Replay, reduce, form one failure hypothesis, and fix the relevant code.
9. Rerun the preserved counterexample first.
10. Run a fresh batch of seeds after the fix.

This workflow is especially useful when you have a plausible $1600+$ solution but lack confidence in an edge condition, a greedy implementation, a transition, or index handling. It replaces repeated speculative edits with evidence.

---

Takeaways and next step

Randomized stress testing combines:

• a small, trustworthy brute-force oracle;
• a generator that emits only legal inputs;
• targeted small structures as well as broad randomness;
• deterministic seeds for replay;
• automatic comparison and immediate stopping on disagreement;
• careful reduction of a failing case into a minimal explanation.

A mismatch isolates a concrete counterexample. Your job is then to determine whether it exposes a fast-solution bug, an oracle mistake, invalid generation, or an incorrect output comparison rule. Thousands of matching tests are reassuring, but your correctness proof remains essential.

This completes the module on algorithm selection, proofs, and testing. Next, the course moves into array transformations and contribution counting, beginning with a particularly reusable conversion: turning subarray-equality conditions into repeated prefix-state counting.