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
ndays,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 |
|---|---|---|
63 -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
mt19937is a fast, good-quality pseudo-random engine. Eachrng()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.
% 11gives 0..10; the cast tointkeeps the subtraction signed;- 5gives −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
-
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. -
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. -
Plant a bug in the fixed fast solution: replace
cur = max(cur + x, x)withcur = 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. -
Why must the brute force use
LLONG_MINand 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
- 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.
- Why small inputs? Bugs usually show up on small cases, and a small failing input can be traced by hand.
- Why seed the generator? So the same tests appear on every run and a failure is reproducible.
- What is a checker? A program that verifies an output's properties instead of comparing text, for problems with many valid answers.
- 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_MINfixed it.
Next episode: contest strategy: reading order, penalties, time management and upsolving.