SyntaxPilot
Courses/Competitive Programming/Lesson 5
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 5 of 90

Stress testing: brute force + random generator + checker

queued

These are the notes for Competitive Programming episode 5. A fast solution to an original problem, Chai Stall Ledger, passes both samples and then fails a hidden test. Instead of staring at the code, you build a small machine: a slow solution you trust (the brute force), a random generator of small inputs, and a loop that compares the two. It hands you the failing input in under a second. You also see the classic four-file setup with a shell script, a generator trap that makes the machine blind, and checkers for problems with many valid answers. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The problem: Chai Stall Ledger

Problem E · Chai Stall Ledger (written for this course). A chai stall's ledger has the profit for each of n days, a[1..n]. A rainy day can make a loss, so profits may be negative. Find the largest total profit of a non-empty run of consecutive days.

1 ≤ n ≤ 2·10^5, |a[i]| ≤ 10^9.

Sample input Sample output Why
6
3 -5 4 -1 2 -7
5 days 3..5: 4 − 1 + 2
4
-2 4 -9 3
4 the single day with 4

Fast idea: walk once. cur is the best run that ends today: either extend yesterday's run (cur + x) or start fresh (x), whichever is bigger. best is the largest cur seen.

The fast solution (as first submitted)

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

ll fast(vector<ll> &a) {
    ll best = 0, cur = 0;
    for (ll x : a) {
        cur = max(cur + x, x);
        best = max(best, cur);
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    cout << fast(a) << '\n';
    return 0;
}

Sample 1 → 5, sample 2 → 4. Both correct. The judge says Wrong answer on test 14, and test 14 is hidden.

Why stress testing

You can't see the failing test, and staring at eight lines that look right wastes the contest. So you make your own tests, thousands of them, and let the computer find one where your answer is wrong. To know an answer is wrong, you need a trusted right answer: a brute force.

Real-life example: a cricket bowling machine.

At the nets In stress testing
The bowling machine throws ball after ball, every line and length Generator: random small inputs
An old coach, slow but never wrong Brute force: obviously correct, allowed to be slow
The umpire compares and raises a finger, showing the exact ball Compare / checker: stop at the first mismatch, print the input
generator ──▶ input ──▶ brute ──▶ answer 1 ─┐
                  └───▶ fast  ──▶ answer 2 ─┴─▶ equal? ── no ──▶ print the input, stop
                                                  └── yes ──▶ next round

Piece 1: the brute force

Try every run: every start l, every end r. Keep a running sum while r moves right.

ll brute(vector<ll> &a) {
    int n = a.size();
    ll best = LLONG_MIN;
    for (int l = 0; l < n; l++) {
        ll sum = 0;
        for (int r = l; r < n; r++) {
            sum += a[r];
            best = max(best, sum);
        }
    }
    return best;
}

On sample 1 it prints 5. It is O(n²), about 2·10^10 steps at n = 2·10^5: far too slow to submit, but instant on n ≤ 5. Rule: the brute force must be dumb. If it uses the same clever idea as your solution, it can share the same bug.

LLONG_MIN (from <climits>, included by bits/stdc++.h) is the smallest long long, so any real sum beats it.

Piece 2: the random generator

mt19937 rng(42);                      // Mersenne Twister engine, seed 42
int n = rng() % 5 + 1;                // n in 1..5
x = (int)(rng() % 11) - 5;            // x in -5..5
  • mt19937 is a fast, good-quality pseudo-random engine. Each rng() call returns a new unsigned number.
  • The seed (42) is where the sequence starts. A fixed seed gives the same tests every run, so a failure is reproducible.
  • % 11 gives 0..10; the cast to int keeps the subtraction signed; - 5 gives −5..5.
  • Keep n and the values small. A failing test with 1 or 2 numbers can be solved by hand. One with 2·10^5 numbers is useless for debugging.

Piece 3: the stress loop, in one file

This is what ran live in the SyntaxPilot compiler:

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

ll fast(vector<ll> &a) {
    ll best = 0, cur = 0;
    for (ll x : a) {
        cur = max(cur + x, x);
        best = max(best, cur);
    }
    return best;
}

ll brute(vector<ll> &a) {
    int n = a.size();
    ll best = LLONG_MIN;
    for (int l = 0; l < n; l++) {
        ll sum = 0;
        for (int r = l; r < n; r++) {
            sum += a[r];
            best = max(best, sum);
        }
    }
    return best;
}

int main() {
    mt19937 rng(42);
    for (int it = 1; it <= 1000; it++) {
        int n = rng() % 5 + 1;
        vector<ll> a(n);
        for (auto &x : a) x = (int)(rng() % 11) - 5;
        if (fast(a) != brute(a)) {
            cout << "Mismatch on test " << it << ": n = " << n << ", a =";
            for (ll x : a) cout << ' ' << x;
            cout << "\nbrute = " << brute(a) << ", fast = " << fast(a) << '\n';
            return 0;
        }
    }
    cout << "All 1000 tests passed\n";
    return 0;
}

Real output:

Mismatch on test 9: n = 1, a = -5
brute = -5, fast = 0

Why it failed

One day with profit −5. The only legal run is that day, so the answer is −5. But best starts at 0, and −5 never beats 0. Zero is the profit of picking no days, which the statement forbids. The samples always had a profitable day, so they never showed it. Test 14 was a week of losses.

Fix: start below every possible answer.

    ll best = LLONG_MIN, cur = 0;

Run the machine again:

All 1000 tests passed

A generator trap: the machine goes blind

A friend writes the values as "profits are 1 to 10 rupees":

        for (auto &x : a) x = rng() % 10 + 1;

With the buggy fast still inside, the output is:

All 1000 tests passed

Every value is positive, so every test has a profitable day and best = 0 is never wrong. The one kind of input that breaks the code never appears. The generator must cover everything the constraints allow: negative values, n = 1, equal values, the extremes. Print a few generated tests and look at them.

The classic 4-file setup (on your own computer)

Keep the solution file exactly as you will submit it.

gen.cpp: prints one random test, seeded by its argument.

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

int main(int argc, char *argv[]) {
    mt19937 rng(atoi(argv[1]));
    int n = rng() % 5 + 1;
    cout << n << '\n';
    for (int i = 0; i < n; i++) cout << (int)(rng() % 11) - 5 << ' ';
    cout << '\n';
}

brute.cpp: reads a test, prints the trusted answer.

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

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    ll best = LLONG_MIN;
    for (int l = 0; l < n; l++) {
        ll sum = 0;
        for (int r = l; r < n; r++) {
            sum += a[r];
            best = max(best, sum);
        }
    }
    cout << best << '\n';
}

sol.cpp: your submission (here, the buggy version with best = 0).

stress.sh:

g++ -O2 -std=c++17 gen.cpp -o gen
g++ -O2 -std=c++17 brute.cpp -o brute
g++ -O2 -std=c++17 sol.cpp -o sol
for i in $(seq 1 1000); do
    ./gen $i > in.txt
    ./sol < in.txt > out1.txt
    ./brute < in.txt > out2.txt
    if ! cmp -s out1.txt out2.txt; then
        echo "Mismatch on seed $i"
        cat in.txt
        echo "sol: $(cat out1.txt)  brute: $(cat out2.txt)"
        exit 1
    fi
done
echo "All 1000 tests passed"

Real output with the buggy sol.cpp:

Mismatch on seed 1
1
-2 
sol: 0  brute: -2

cmp -s compares two files silently and fails if they differ. On Windows, use the same loop in a .bat file or run it in WSL; or simply use the one-file version above.

Checkers: when many answers are correct

Some problems say "print any valid answer". Comparing text then gives false mismatches: like an exam question "write any prime greater than 10", where 11 and 13 are both correct. A teacher checks the rule, not the answer key. A checker does the same: it verifies the properties of your output, and uses the brute force only for the part that is unique.

Problem E, version 2: also print the days l r of a best run. Several runs can tie.

// fast prints best, l, r.  Many (l, r) can be correct.
bool check(vector<ll> &a, ll best, int l, int r) {
    if (l < 1 || r > (int)a.size() || l > r) return false;
    ll sum = 0;
    for (int i = l; i <= r; i++) sum += a[i - 1];
    return sum == best && best == brute(a);
}

Is the range legal? Does it really sum to the printed total? Is that total the true best? If all three hold, the answer is accepted, whichever tied run was printed.

The accepted solution and edge cases

Edge case Input Output
Every day a loss 3 / -5 -2 -9 -2
Sums beyond int 3 / 1000000000 1000000000 1000000000 3000000000
One day 1 / -5 -5

Solution in C++, Java and Python

C++

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

ll fast(vector<ll> &a) {
    ll best = LLONG_MIN, cur = 0;
    for (ll x : a) {
        cur = max(cur + x, x);
        best = max(best, cur);
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &x : a) cin >> x;
    cout << fast(a) << '\n';
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken();
        int n = (int) st.nval;
        long best = Long.MIN_VALUE, cur = 0;
        for (int i = 0; i < n; i++) {
            st.nextToken();
            long x = (long) st.nval;
            cur = Math.max(cur + x, x);
            best = Math.max(best, cur);
        }
        System.out.println(best);
    }
}

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    best, cur = None, 0
    for i in range(1, n + 1):
        x = int(data[i])
        cur = max(cur + x, x)
        best = cur if best is None else max(best, cur)
    print(best)

main()

Brute force vs optimal

Brute force Fast (one pass)
Idea try every run l..r best run ending today: extend or restart
Time O(n²) ≈ 2·10^10 at n = 2·10^5 (TLE) O(n) ≈ 2·10^5 (instant)
Extra memory O(1) beyond the input O(1) beyond the input
Role in stress testing the trusted answer on tiny inputs the solution under test

Common mistakes (and what you see)

Mistake What you see Why Fix
ll best = 0 when the run must be non-empty brute = -5, fast = 0 0 is the value of an empty run ll best = LLONG_MIN
Generator values rng() % 10 + 1 when negatives are allowed All 1000 tests passed with a buggy solution the failing case is never generated cover every allowed input: (int)(rng() % 11) - 5
Huge random n in the generator a mismatch you can't read the failing test has 2·10^5 numbers n ≤ 5, values in −5..5 first
A "clever" brute force both agree, both wrong brute shares the bug try every possibility
Comparing text when any answer is valid false mismatches many correct outputs write a checker
srand(time(0)) or an unfixed seed a failure you can't reproduce different tests every run fixed seed, or print the seed

Mini project: a reusable stress harness

Turn the one-file version into a template you paste into any problem: keep fast, brute and gen as three functions, and make main read the number of rounds and the seed from input:

int main() {
    int rounds, seed;
    cin >> rounds >> seed;          // e.g. 1000 42
    mt19937 rng(seed);
    for (int it = 1; it <= rounds; it++) {
        vector<ll> a = gen(rng);    // your generator
        if (fast(a) != brute(a)) { /* print the input and both answers */ return 0; }
    }
    cout << "All " << rounds << " tests passed\n";
}

Then try it on episode 4's Step Streak: plant the global-variable bug back in and see which round finds it.

Practice

  1. Change the generator so that n is between 1 and 8 and values between −3 and 3. Does the machine still find the bug? On which test?

    Answer Yes. Any test whose values are all negative fails; smaller value ranges make that more likely, so it is found within the first few dozen rounds. The exact test number depends on the seed.

  2. Write a brute force for "longest strictly increasing run" (episode 4) that checks every pair l ≤ r.

    Answer For every l, extend r while `a[r] > a[r − 1]`; track the longest `r − l + 1`. O(n²), obviously correct.

  3. Plant a bug in the fixed fast solution: replace cur = max(cur + x, x) with cur = cur + x. What does the stress test print?

    Answer A small test where a negative prefix should be dropped, for example `n = 2, a = -3 4`: brute = 4, fast = 1.

  4. Why must the brute force use LLONG_MIN and not 0 as well?

    Answer Otherwise it shares the same bug, both answers agree, and the machine reports "all passed" on a wrong solution.

Quick quiz

Your stress test passes 10,000 rounds but the judge still says WA. The constraints allow |a[i]| ≤ 10^9 and the generator is:

mt19937 rng(42);
int n = rng() % 5 + 1;
x = rng() % 10 + 1;   // values

A) The judge is wrong · B) Need 100,000 rounds · C) The generator never makes negatives · D) mt19937 is not random

Answer

C. rng() % 10 + 1 is always 1..10, but the constraints allow negative values. The generator never produces the cases that break the solution.

Interview questions

  1. What is stress testing and when do you use it? Comparing a fast solution with a slow, obviously correct one on many random small inputs; use it when you get WA on a hidden test and can't find the bug by reading.
  2. Why small inputs? Bugs usually show up on small cases, and a small failing input can be traced by hand.
  3. Why seed the generator? So the same tests appear on every run and a failure is reproducible.
  4. What is a checker? A program that verifies an output's properties instead of comparing text, for problems with many valid answers.
  5. What is the maximum subarray problem's classic algorithm called? Kadane's algorithm: the best sum ending at each position is max(x, previous + x).

Glossary

Term Meaning Example
Hidden test A judge test whose input you can't see "Wrong answer on test 14"
Stress testing Comparing two solutions on many random inputs the 1000-round loop
Brute force A slow solution that tries every possibility every run l..r, O(n²)
Generator A program or function that makes random valid inputs rng() % 5 + 1
mt19937 C++'s Mersenne Twister random engine mt19937 rng(42);
Seed The starting point of a random sequence 42 in rng(42)
Reproducible Gives the same result every run fixed seed
Mismatch / counterexample An input where two solutions disagree n = 1, a = -5
Checker Verifies the rules of an answer instead of comparing text sum of a[l..r] equals best
LLONG_MIN The smallest long long value ll best = LLONG_MIN;
cmp A shell command that compares two files cmp -s out1.txt out2.txt
Run (subarray) A block of consecutive elements days 3..5
Kadane's algorithm The one-pass best-subarray method cur = max(cur + x, x)

Summary

  • When a hidden test fails, generate your own tests.
  • A stress test is a generator, a dumb brute force, your fast solution and a comparison in a loop.
  • Use small n and values and a fixed seed: you get a tiny, reproducible failing input.
  • The generator must cover every input the constraints allow, or the machine goes blind.
  • For "print any valid answer" problems, write a checker.
  • Here the bug was best = 0 (an empty run); best = LLONG_MIN fixed it.

Next episode: contest strategy: reading order, penalties, time management and upsolving.