Stress testing with a brute force

Why this matters when you build with AI

An AI tool can give you a fast solution in seconds. It can also give you one that is wrong on a case you did not think of. You cannot tell which, because the code looks equally confident in both cases. Reading the code carefully helps, but a careful reading of a 60-line solution misses things, and a sample test with five numbers misses most of them.

Stress testing is a way to check a fast solution automatically. You keep a second program that is slow but simple enough to trust. You generate many small random inputs, run both programs on each one, and compare the outputs. If they ever differ, you have a concrete input that breaks the fast solution. Then you make that input as small as you can, so you can see the cause.

The method does not prove that a solution is correct. It only shows that the two programs agree on the cases you tried. Its strength is that it tries thousands of cases in a minute, many more than you would write by hand. This lesson is C++17 for the programs and Python for the test loop.

The idea: four parts

A stress test has four parts.

1. The brute force. A slow program that solves the problem by trying every possibility. It must be simple enough that you can check it by reading. Its speed does not matter, because the inputs are small.

2. The fast solution. The program you want to test. It is the one you would submit.

3. The generator. A program that prints one random small input each time it runs. The seed, a number that sets the random sequence, decides the input, so a failing case can be printed again later.

4. The checker. A loop that runs the generator, runs both solutions on the same input, and stops when the outputs differ. It also stops when a solution crashes or takes too long.

A word on terms. A brute force is a program that checks every candidate answer, often with nested loops. An oracle is the program whose answer you trust, here the brute force. A planted bug is a deliberate error that you put into a copy of the fast solution, so you know a stress test should find it.

Why small inputs are enough

Many bugs in fast solutions also show up on small inputs. An off-by-one error in a loop bound fails with three elements just as it fails with three million. Some bugs need a large input, such as an overflow (see the lesson on integer overflow and modulo arithmetic). For those, stress testing with small inputs will not help, and you need a different test with large values.

Keep the inputs small but varied. Use small values, so that ties and equal values appear often. Ties are the usual source of boundary bugs, such as < where <= was meant.

Worked example: lamp row windows

Here is an original problem written for this lesson.

A row has n lamps. Lamp i has brightness b_i. You are given an integer k. Count the pairs (l, r) with l < r such that the segment of lamps from l to r, both included, has largest brightness minus smallest brightness at most k. The first line holds n and k. The second line holds the n brightness values. Constraints: 2 <= n <= 200000, 0 <= k <= 10^9, 0 <= b_i <= 10^9.

Read the problem twice. A segment must have at least two lamps, so l < r. The answer can be as large as about 2 × 10^10, so the output must use a 64-bit type.

For the sample input:

5 2
1 3 2 6 4

The valid segments are [1, 3], [3, 2], [6, 4], and [1, 3, 2]. Each has a spread (largest minus smallest) of at most 2. The answer is 4. We checked the sample by hand before running code.

The brute force

The brute force checks every segment with a full scan. That makes it slow, about n³ steps, but each step is simple. It is the program we trust.

#include <bits/stdc++.h>
using namespace std;
// Count pairs (l, r) with l < r whose max - min is at most k.
// Brute force: scan every segment fully.
int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> b(n);
    for (auto& x : b) cin >> x;
    long long count = 0;
    for (int l = 0; l < n; l++)
        for (int r = l + 1; r < n; r++) {
            long long mx = LLONG_MIN, mn = LLONG_MAX;
            for (int i = l; i <= r; i++) {
                mx = max(mx, b[i]);
                mn = min(mn, b[i]);
            }
            if (mx - mn <= k) count++;
        }
    cout << count << '\n';
}

The loop over l and r covers every segment with at least two lamps. The inner loop finds the largest and smallest value in the segment. The check mx - mn <= k is the condition from the statement.

The fast solution

The fast method uses two pointers. A pointer l marks the left end of a window, and r moves right one step at a time. The window [l, r] always has a spread of at most k. To find the largest and the smallest value in the window quickly, we keep two monotone deques. A deque is a queue that can add and remove at both ends. Each deque keeps the indices of values that could still be the maximum (or minimum), in order, so the front is always the current answer.

When r moves right, we add r to both deques. If the spread is now above k, we move l right until it is at most k again. For each r, the segments that end at r and are valid are those starting at any l' from l to r - 1. There are r - l of them, and we add that count.

#include <bits/stdc++.h>
using namespace std;
// Two pointers with two monotone deques. Amortised O(n).
int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> b(n);
    for (auto& x : b) cin >> x;
    deque<int> mxq, mnq;      // indices; values decrease in mxq and increase in mnq
    int l = 0;
    long long count = 0;
    for (int r = 0; r < n; r++) {
        while (!mxq.empty() && b[mxq.back()] <= b[r]) mxq.pop_back();
        mxq.push_back(r);
        while (!mnq.empty() && b[mnq.back()] >= b[r]) mnq.pop_back();
        mnq.push_back(r);
        while (b[mxq.front()] - b[mnq.front()] > k) {
            l++;
            while (!mxq.empty() && mxq.front() < l) mxq.pop_front();
            while (!mnq.empty() && mnq.front() < l) mnq.pop_front();
        }
        count += r - l;
    }
    cout << count << '\n';
}

Each index enters and leaves each deque at most once, and l only moves right. So the total work is O(n), plus the cost of reading the input.

Compile both with the sanitizer flags from the lesson on contest templates:

g++ -std=c++17 -O2 -Wall -Wextra -Wshadow -Wconversion -fsanitize=address,undefined -fno-sanitize-recover=all brute.cpp -o brute
g++ -std=c++17 -O2 -Wall -Wextra -Wshadow -Wconversion -fsanitize=address,undefined -fno-sanitize-recover=all fast.cpp -o fast

Both programs print 4 on the sample. Here is the real output of our run:

input: 5 2 / 1 3 2 6 4     brute: 4     fast: 4

We also compared them on 400 random inputs with n from 1 to 60, k up to 10^9, and values up to 3, 10 or 10^9. All 400 agreed. We also ran fast on a random input with n = 200000. It finished in about 0.1 seconds on our machine. Your timing will differ.

The generator

The generator prints one small random case. The seed is the command-line argument, so the same seed always gives the same input. We keep values between 0 and 5, so that equal values appear often, and k between 1 and 4, so that a spread exactly equal to k happens often. (We come back to the choice of k below.)

import random, sys
 
seed = int(sys.argv[1])
rnd = random.Random(seed)
n = rnd.randint(1, 8)
k = rnd.randint(1, 4)
b = [rnd.randint(0, 5) for _ in range(n)]
print(n, k)
print(*b)

The generator can produce n = 1. That case is valid input, and its answer is 0.

The checker loop

The checker runs the generator for seed 1, then seed 2, and so on. For each seed it runs the brute force and the solution under test, and compares their outputs. It stops at the first difference, at the first crash, or at the first run that takes too long.

import subprocess, sys
 
# usage: python3 stress.py <solution> <max_iterations>
sol = sys.argv[1]
limit = int(sys.argv[2])
for seed in range(1, limit + 1):
    inp = subprocess.run(["python3", "gen.py", str(seed)],
                         capture_output=True, text=True, timeout=10).stdout
    want = subprocess.run(["./brute"], input=inp,
                          capture_output=True, text=True, timeout=10)
    try:
        got = subprocess.run([sol], input=inp,
                             capture_output=True, text=True, timeout=2)
    except subprocess.TimeoutExpired:
        print(f"seed {seed}: solution did not finish in 2 seconds")
        print(inp, end="")
        break
    if got.returncode != 0:
        print(f"seed {seed}: solution exited with code {got.returncode}")
        print(inp, end="")
        break
    if got.stdout.split() != want.stdout.split():
        print(f"seed {seed}: MISMATCH brute={want.stdout.strip()} solution={got.stdout.strip()}")
        print(inp, end="")
        break
else:
    print(f"no difference in {limit} cases")

Three details matter here. The loop runs the programs with subprocess, which starts each one without a shell, so the input is passed exactly. The comparison uses split(), so trailing spaces and line endings do not cause a false alarm. The timeout stops a solution that loops forever, which a plain run would not stop. The loop prints the failing input, so you can copy it.

Run it on the correct solution first:

python3 stress.py ./fast 3000

Our run printed no difference in 3000 cases. A passing run is not a proof. It only tells you that this fast solution agreed with the brute force on 3000 small inputs.

The planted bug

Now we test the checker on a solution that is wrong. Copy fast.cpp to fast_bug.cpp and change one character in the shrinking loop. The > becomes >=:

        while (b[mxq.front()] - b[mnq.front()] >= k) {

This makes the window shrink when its spread is exactly k, even though k is allowed. A segment with spread exactly k is valid, so the buggy version undercounts. Compile it without sanitizers, since we want to see the raw behaviour:

g++ -std=c++17 -O2 fast_bug.cpp -o fast_bug

Run the checker on it:

python3 stress.py ./fast_bug 3000

Our run printed:

seed 3: MISMATCH brute=5 solution=1
4 2
2 4 3 5

The brute force says 5 and the buggy solution says 1. The first failing input is the four-lamp row with k = 2. Your seed and output may differ if you change the generator, but the mismatch will appear.

Why the k = 0 case is different

We first let the generator use k from 0 to 4. The checker then reported a different failure:

seed 2: solution did not finish in 2 seconds
1 0
0

With k = 0 and a single lamp, the shrinking loop keeps removing elements until both deques are empty. Then it reads the front of an empty deque, which is undefined behaviour, and in our run the program never stopped. This is a real bug in the planted version, and the checker found it. We keep k from 1 to 4 in the main test so that the mismatch shows first. Check the k = 0 case separately with a hand-written input. Do not hide it.

Shrinking the failing input

A failing input of four lamps is hard to reason about. Shrinking means you remove parts of the input one at a time and keep the change only if the outputs still differ. Shrinking gives you the smallest case, which points to the cause.

Here is the sequence from our run. Each line is an input, then the answers of the brute force and the buggy solution. We checked each one by hand, too.

4 2 / 2 4 3 5     brute 5, buggy 1    (start)
2 2 / 2 4         brute 1, buggy 0    (removed 3 and 5, and n = 2)
3 1 / 0 1 1       brute 3, buggy 1    (changed the values and k, with n = 3)
2 1 / 0 1         brute 1, buggy 0    (removed one lamp)
1 1 / 0           brute 0, buggy 0    (no longer fails)

The failing case that remains is 2 1 with brightness 0 1. The spread is exactly 1, which equals k. The segment should count, but the buggy version does not count it. That tells you the cause: the comparison with k is wrong at the boundary.

Shrink by hand with three moves: remove elements from the ends, reduce the values towards 0, and reduce n. After each move, run both programs again. Keep the change only if they still differ.

Common mistakes

The brute force is wrong too. The checker trusts the brute force. If both programs read the input the same wrong way, they agree and the test passes for the wrong reason. Test the brute force on the sample, and by hand on one or two small cases, before you trust the loop.

Forgetting to rebuild. The symptom is that a fix seems to have no effect. The checker runs the old binary. Rebuild after every change to a source file, and use the same name each time.

Generator values that are too spread out. If values are random between 0 and 10^9, equal values almost never occur, and the boundary bug never shows. Use small values, and check that your generator makes ties.

Stopping at the first failure without shrinking. A 60-element failing input is hard to read. Always shrink before you look for the cause.

Missing the crash and timeout cases. A program that crashes gives a non-zero exit code with no output, and a program that loops forever gives no output at all. The checker above handles both, but a simpler loop that only compares text does not.

Assuming a passing run means correct. Three thousand passing cases with n up to 8 say nothing about n = 200000. Use large tests for performance, and the large-input checks from the other lessons for overflow.

Brute and fast solutions that share the same misunderstanding. If you read the statement wrongly, an AI tool may write both programs with the same wrong reading. Read the sample and write its answer by hand before you trust either program.

Checklist

• Write the brute force first, and make it obviously correct, even if it is slow.
• Check the brute force by hand on the sample and on one small case.
• Generate small inputs with many ties and with the boundary values of the statement.
• Keep the generator seeded, so a failing input can be printed again.
• Run the checker with a timeout and with exit-code checks.
• Rebuild the binary after every change.
• When the checker finds a difference, shrink the input by hand before you look for the cause.
• Test the smallest valid inputs too: n = 1, k = 0, all values equal.
• Remember that a passing loop is evidence, not proof.

Hands-on exercise

Work in a new folder on your machine. Save the brute force as brute.cpp and the fast solution as fast.cpp. Save the generator as gen.py and the checker as stress.py. Build fast_bug from fast.cpp, changing > to >= in the shrinking loop.

1. Run python3 stress.py ./fast 3000. Record the result.
2. Run python3 stress.py ./fast_bug 3000. Record the first failing input and the two answers.
3. Shrink the failing input by hand until no smaller input fails. Write down each step, with both answers.
4. Run brute and fast_bug on the smallest failing input you found, to confirm it.
5. Change gen.py so that k starts at 0. Run the checker on fast_bug again. Record what happens, and explain why.

Show the answer

Step 1 should print no difference in 3000 cases. Step 2 should find a mismatch. Our run gave seed 3, with the four-lamp input 4 2 / 2 4 3 5, where the brute force says 5 and the buggy solution says 1. Step 3 should end at 2 1 / 0 1, where the brute force says 1 and the buggy solution says 0. You should not be able to remove a lamp or lower a value from that case and keep the failure. Step 5 gives the timeout from the lesson: with k = 0, the buggy version reads an empty deque and does not stop. The fast correct solution does not hang on that input.

Practice problems

Work each problem by hand first, then check it in code.

Practice 1: a brute force. Write a brute force that counts subarrays of length exactly 3 that are strictly increasing, meaning each value is larger than the one before. Input: n, then n integers. Test it on 6 and 1 2 3 2 3 4.

Hint: a subarray of length 3 starts at each index i from 0 to n - 3. Check three values in one line.

Show the answer

Count the windows starting at each index and check that a[i] < a[i+1] < a[i+2]. For 1 2 3 2 3 4, the windows starting at index 0 and index 3 are increasing, so the answer is 2. Check your code with this sample.

Practice 2: find the smallest failing input. The planted bug from this lesson fails on a valid input with two lamps. Find the smallest input with n = 2 and k = 1 that makes fast_bug and brute disagree.

Hint: the boundary case is a spread exactly equal to k.

Show the answer

Use the brightness 0 1 with k = 1. The brute force counts the segment, so it prints 1. The buggy solution prints 0. Any input with n = 2 and a spread of exactly k shows the bug.

Practice 3: a generator that favours ties. Change the generator so that values are chosen from {0, 1} only, and k is 1. Explain in one paragraph why this generator finds the planted bug sooner than the one in the lesson.

Hint: think about how often a segment has a spread of exactly 1.

Show the answer

With values only 0 and 1, any segment containing both values has a spread of exactly 1, which equals k. The buggy comparison >= then changes the count on many inputs, so the checker finds the difference after a few seeds. The general generator also finds it, but it needs more seeds, because k must match the spread by chance.

Practice 4: when the test cannot help. Name one bug that the stress test in this lesson would not find, and explain why.

Hint: think about the size of the values and the size of n.

Show the answer

An integer overflow that happens only when values are near 10^9 and n is large. The generator uses values up to 5 and n up to 8, so no sum comes close to the 32-bit limit. A large test with values near the limit, as in the lesson on integer overflow, is the right check for this kind of bug.

Python notes

The checker in this lesson is written in Python, because it is short to write and easy to change. The brute force and the fast solution are C++, because they must run quickly. You can also write the brute force in Python for small inputs. A Python brute force is slower, but for n up to 8 it is fast enough.

Calling a separate process for each generated input costs time. For thousands of cases, it is faster to generate the inputs inside the checker with the same random seed, and to run the programs once per case. The structure does not change.

Summary

A stress test runs a fast solution against a trusted brute force on many small random inputs and stops at the first difference. Shrink that input by hand to find the cause, and remember that a passing run is evidence, not proof.