C++ Module 19 – C++ for DSA and competitive programming

Stress testing contest solutions in C++

Find wrong answers by comparing a fast C++ solution with a brute force on many small random inputs, replay every failure from its seed, and shrink it.

Intermediate
30 minutes
Examples run with Clang 21.0.0, GCC 16.2.0 and Python 3.14.8
By MySmartCoPilot

Free: A solution can pass both samples and still be wrong · A stress test needs four pieces · The first failing seed names the bug · 2 more sections. With a pass: 2 in-depth parts and 3 interview answers, about 19 minutes.

What you will learn

Find wrong answers by comparing a solution with a brute force
Choose generator sizes and value ranges that reach boundary bugs
Reproduce every failing case from its seed, on any compiler
Simplify a failing case to a small input that still fails

Before you start

What you’ll learn · Before you start

What you will learn

Find wrong answers by comparing a solution with a brute force
Choose generator sizes and value ranges that reach boundary bugs
Reproduce every failing case from its seed, on any compiler
Simplify a failing case to a small input that still fails

Before you start

On this page

A solution can pass both samples and still get Wrong answer on test 23, a test the judge never shows you. A A test that runs a solution and a slow but surely correct version of it on many small random inputs and compares their answers, so that the first difference gives a failing input small enough to check by hand. finds such an input for you: it runs your fast solution and a slow, obviously correct one, the The simplest correct solution of a problem, such as checking every pair, written straight from the statement: far too slow for the real limits, but easy to trust as the reference a faster solution is tested against., on thousands of small random inputs and stops at the first input on which their answers differ, small enough to check by hand. It needs four pieces: a generator that makes one input from a seed: The value that sets a random number engine's starting state, such as 42 in std::mt19937 engine(42). The same seed gives the same sequence again; a seed from std::random_device makes each run different. More in “Random numbers in C++: engines, distributions, seeds”, the brute force, the solution under test, and a driver that compares their outputs and prints the seed with every failure, so that the case replays exactly. Use one whenever a solution passes its samples and still fails, or before submitting one whose edge cases you doubt. This lesson builds one for an original problem and catches a boundary bug that both samples miss.

A solution can pass both samples and still be wrong

Close scores. n players have integer scores a₁, …, aₙ. Two players are close when their scores differ by at most d. Count the pairs of players i < j that are close. Constraints: 1 ≤ n ≤ 200,000, 0 ≤ d ≤ 10⁹ and 0 ≤ aᵢ ≤ 10⁹. The input is n and d, then the n scores; the output is one number. Sample 1 is 5 3 with the scores 10 2 6 4 15, sample 2 is 6 4 with 1 20 3 11 30 9, and both answers are 2.

Sorting the scores puts close players next to each other, so two pointers count the pairs in O(n log n): for each score a[j], the scores from a[i] to a[j - 1] are within d of it, and i only ever moves right.

fast.cpp C++ · fast.cpp

// fast.cpp: "Close scores" in O(n log n): sort, then slide two pointers. It passes both samples.
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    int n;
    long long d;
    std::cin >> n >> d;
    std::vector<long long> a(n);
    for (auto& x : a) std::cin >> x;
    std::ranges::sort(a);
    long long pairs = 0;
    int i = 0;  // the first score that is still close enough to a[j]
    for (int j = 0; j < n; ++j) {
        while (i < j && a[j] - a[i] >= d) ++i;
        pairs += j - i;  // a[i], ..., a[j - 1] are each within d of a[j]
    }
    std::cout << pairs << '\n';
}

Both samples Python · samples_session.py

from session import run

# The fast solution on the two samples of the statement: both answers are right.
run("""
clang++ -std=c++23 -O2 -Wall -Wextra fast.cpp -o fast
./fast < sample1.txt
./fast < sample2.txt
""")

Output

$ clang++ -std=c++23 -O2 -Wall -Wextra fast.cpp -o fast
$ ./fast < sample1.txt
2
$ ./fast < sample2.txt
2

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 samples_session.py

Both answers are right, and that is all two samples can show.

Checkpoint

Check: Close scores and its two-pointer solution

Question 1 of 2 Sample 1 has d = 3 and the scores 10 2 6 4 15. Which pairs of scores are close?
Choose one answer.

6 and 10, and 10 and 15 2 and 4, 4 and 6, and 2 and 6 2 and 4, and 4 and 6 Only 4 and 6

Show the answer: Question 1 of 2

Answer: 2 and 4, and 4 and 6

Sorted, the scores are 2 4 6 10 15. Two players are close when their scores differ by at most d = 3: 4 − 2 = 2 and 6 − 4 = 2 qualify, and every other difference is 4 or more. That gives the sample's answer, 2.
Question 2 of 2 Sample 2 sorted is 1 3 9 11 20 30, with d = 4. When j reaches 11, at position 3, how many pairs does fast.cpp add?
Type a number.
Your answer pairs

A hint

Find where i stands: the first score that is still close enough to 11. j adds the scores from a[i] to a[j − 1].

Show the answer: Question 2 of 2

Answer: 1 pairs

When j was at 9, the loop moved i past 1 and 3 to position 2. For 11, a[j] − a[i] = 11 − 9 = 2 is within d, so i stays at 2 and j adds j − i = 3 − 2 = 1: the pair 9 and 11. The scores 1 and 3 are 10 and 8 below 11.

A stress test needs four pieces

The four pieces form one loop, repeated once per seed:

The loop of a stress test

Text description of the diagram

The diagram is a loop of five steps.

"seed k" leads to "gen k", which makes one small random input from the seed.
The input goes to two programs: "brute", which checks every pair and is slow but easy to trust, and "fast", the two-pointer solution under test.
Both answers go to a diamond, "same answer?".
An arrow labelled "yes: k + 1" goes from the diamond back to the seed, so the loop tries the next seed.
An arrow labelled "no" goes to "stop: print seed k, the input and both answers", which is everything needed to replay the failing case.

The brute force checks every pair, O(n²), which is hopeless at n = 200,000 and trivial to get right. The generator makes inputs that are small on purpose: at most 8 scores, from 0 to 9, so that equal scores and exact differences turn up all the time. It uses only the raw numbers of std::mt19937, which the C++ standard fixes, so a seed gives the same input with every standard library:

The brute force and the generator

C++ (brute.cpp) · brute.cpp

// brute.cpp: "Close scores" by checking every pair, O(n²): far too slow for n = 200,000, and easy to trust.
#include <iostream>
#include <vector>

int main() {
    int n;
    long long d;
    std::cin >> n >> d;
    std::vector<long long> a(n);
    for (auto& x : a) std::cin >> x;
    long long pairs = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (a[i] - a[j] <= d && a[j] - a[i] <= d) ++pairs;
    std::cout << pairs << '\n';
}

C++ (gen.cpp) · gen.cpp

// gen.cpp: one small random input of "Close scores", fully decided by the seed in argv[1].
// It takes the engine's raw numbers and reduces them with %, so every standard library makes the same input from
// the same seed (std::mt19937's numbers are fixed by the C++ standard; distributions are not). The tiny bias of %
// does not matter for test inputs.
#include <cstdlib>
#include <iostream>
#include <random>

int main(int argc, char* argv[]) {
    std::mt19937 engine(static_cast<unsigned>(std::strtoul(argv[1], nullptr, 10)));
    auto pick = [&](unsigned lo, unsigned hi) { return lo + engine() % (hi - lo + 1); };
    unsigned n = pick(1, 8);  // small, so that a failing case is easy to read
    unsigned d = pick(0, 4);
    std::cout << n << ' ' << d << '\n';
    for (unsigned k = 0; k < n; ++k) std::cout << pick(0, 9) << (k + 1 < n ? ' ' : '\n');  // many equal scores
}

The driver is a short shell loop. It writes each input to a file, runs both programs on it, and compares the two outputs with cmp, which POSIX defines to return a non-zero exit status: The number a program hands back when it ends, the value main returns. 0 means success; a shell keeps the last status in $?, and && runs the next command only after a status of 0. More in “How C++ compiles: preprocess, compile and link” when files differ:

stress.sh Shell · stress.sh

#!/bin/sh
# stress.sh: build the three programs, then compare fast with brute on the inputs of seeds 1 to $1, and stop at the
# first difference with everything needed to replay it.
set -e
clang++ -std=c++23 -O2 gen.cpp -o gen
clang++ -std=c++23 -O2 brute.cpp -o brute
clang++ -std=c++23 -O2 "${2:-fast.cpp}" -o fast
seed=1
while [ "$seed" -le "$1" ]; do
    ./gen "$seed" > input.txt
    ./brute < input.txt > expected.txt
    ./fast < input.txt > got.txt
    if ! cmp -s expected.txt got.txt; then
        echo "seed $seed: the outputs differ"
        cat input.txt
        echo "expected $(cat expected.txt), got $(cat got.txt)"
        exit 1
    fi
    seed=$((seed + 1))
done
echo "seeds 1 to $1: no difference"

Follow the driver’s first pass, on seed 1:

Interactive · stage by stage The driver's first pass, on seed 1 Step through one pass of stress.sh. Each stage is one line of its loop; the arrow on the right is the way back to the next seed.

The drawing shows the whole scene; its 6 steps are listed below.

Every step as text

Seed 1 makes an input. The loop starts at seed 1. gen.cpp seeds std::mt19937 with 1 and draws n = 6, d = 4 and six scores from 0 to 9, which it writes to input.txt.
The brute force answers. brute.cpp checks all 15 pairs of the six scores. 11 of them differ by at most 4, so expected.txt holds 11.
The solution answers. fast.cpp sorts the scores to 1 1 3 3 4 8 and counts with its two pointers. It prints 10, so got.txt holds 10.
cmp finds a difference. cmp -s prints nothing and answers with its exit status: non-zero, because the two files differ. The if in stress.sh therefore runs.
The loop stops. The driver prints seed 1, the input and "expected 11, got 10", then exits with status 1. Running ./gen 1 again makes the same input, so the case can be replayed and checked by hand.
With the fixed solution. Built from fast_fixed.cpp, the solution prints 11 for seed 1 too. cmp answers 0, the loop goes on to seed 2, and seeds 1 to 100 pass without a difference.

Checkpoint

Check: The four pieces of a stress test

Question 1 of 2 The stress test reports "seed 1: the outputs differ". What do you need to replay that case exactly?
Choose one answer.

The seed and the same generator program The output of the fast solution Nothing can replay it, because the input was random The time at which the test ran

Show the answer: Question 1 of 2

Answer: The seed and the same generator program

gen.cpp decides the whole input from the seed, using only the engine's raw numbers, so ./gen 1 prints the same input every time and with every standard library. The driver prints the seed with every failure for exactly this reason.
Question 2 of 2 ./stress.sh 1000 stops with "seed 37: the outputs differ". How many times did it run brute?
Type a number.
Your answer runs

Show the answer: Question 2 of 2

Answer: 37 runs

The loop runs gen, brute and fast once per seed, starting at seed 1, and stops at the first seed whose two outputs differ. Seeds 1 to 37 each ran brute once, 37 runs in all, and seeds 38 to 1,000 never ran.

The first failing seed names the bug

Here is the driver’s run on fast.cpp, then on the fixed version:

The stress test, on fast.cpp and then on the fixed version Python · stress_session.py

from session import run

# The stress test on the fast solution, then on the fixed one. Each case starts gen, brute, fast and cmp, so the
# fixed solution gets 100 cases here; the in-process driver later in the lesson runs far more.
run("""
./stress.sh 1000
./stress.sh 100 fast_fixed.cpp
""")

Output

$ ./stress.sh 1000
seed 1: the outputs differ
6 4
4 8 3 3 1 1
expected 11, got 10
[exit status 1]
$ ./stress.sh 100 fast_fixed.cpp
seeds 1 to 100: no difference

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 stress_session.py

The first seed already failed. Sorted, its scores are 1 1 3 3 4 8, and with d = 4 the brute force counted 11 close pairs: the 10 pairs among 1, 1, 3, 3 and 4, plus 4 and 8, whose difference is exactly 4. The fast solution counted 10, because its loop moved i on while a[j] - a[i] >= d, which treats a difference of exactly d as too far. Step through the loop on these six scores and watch the pair 4 and 8 go missing:

Interactive · step by step Where fast.cpp loses a pair, on the input of seed 1 Step through the loop for each position j. The left column holds the sorted scores; the right one says where i stands and how many pairs j adds.

The drawing shows the whole scene; its 7 steps are listed below.

Every step as text

The failing input, sorted. fast.cpp sorts the six scores of seed 1 to 1 1 3 3 4 8; d is 4. For each position j it moves i to the first score close enough to a[j], then adds j − i, the scores from a[i] to a[j − 1].
j = 0. a[0] = 1 has no score before it, so i stays at 0 and j adds 0.
j = 1. 1 − 1 = 0 is within 4, so i stays at 0 and j adds 1: the pair of the two 1s.
j = 2, 3 and 4. 3, 3 and 4 are each within 4 of a[0] = 1, so i does not move and they add 2, 3 and 4: the 10 pairs among 1, 1, 3, 3 and 4.
j = 5: 8 is far away. For a[5] = 8, the scores 1, 1, 3 and 3 differ from it by 7 and 5, more than d, so the while loop moves i past all four of them, to position 4.
The bug: 8 − 4 = 4. Now a[i] = 4, and 8 − 4 = 4 is exactly d. fast.cpp moves i on while a[j] − a[i] >= d, and 4 >= 4 holds, so i moves to 5 and j adds 0. The pair 4 and 8 is lost, and the total stays at 10.
The fix: > instead of >=. fast_fixed.cpp moves i only while a[j] − a[i] > d. 4 > 4 is false, so i stops at 4 and j adds 5 − 4 = 1: the total is 11, the brute force's answer.

The fix is >, after which the pointer can never pass j, so the i < j guard goes too:

fast_fixed.cpp C++ · fast_fixed.cpp

// fast_fixed.cpp: fast.cpp with its boundary fixed. A pair whose scores differ by exactly d is close, so the left
// pointer moves only while the difference is greater than d.
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    int n;
    long long d;
    std::cin >> n >> d;
    std::vector<long long> a(n);
    for (auto& x : a) std::cin >> x;
    std::ranges::sort(a);
    long long pairs = 0;
    int i = 0;
    for (int j = 0; j < n; ++j) {
        while (a[j] - a[i] > d) ++i;  // stops at i == j at the latest: a[j] - a[j] is 0
        pairs += j - i;
    }
    std::cout << pairs << '\n';
}

The fixed solution matched the brute force on all 100 seeds. Both samples had passed because neither contains two scores exactly d apart, which is typical: samples show the format, not every edge.

Checkpoint

Check: Reading the first failing case

Question 1 of 2 For seed 1, d = 4 and the scores 4 8 3 3 1 1, brute counted 11 pairs and fast counted 10. Which pair did fast miss?
Choose one answer.

1 and 4 The two 1s 4 and 8 3 and 8

Show the answer: Question 1 of 2

Answer: 4 and 8

8 − 4 is exactly d, so the pair is close. fast moved its left pointer past 4 because its loop condition was a[j] − a[i] >= d, which treats a difference of exactly d as too far. 8 − 3 is 5, which really is too far.
Question 2 of 2 fast.cpp, with its >= test, runs on d = 2 and the scores 0 2 2 5. The brute force prints 3. What does fast.cpp print?
Type a number.
Your answer pairs

A hint

Step through j = 1, 2 and 3 as the figure does: the loop moves i on while a[j] − a[i] >= 2.

Show the answer: Question 2 of 2

Answer: 1 pairs

At j = 1, 2 − 0 = 2 >= 2 moves i to 1, so j adds 0 and the pair 0 and 2 is lost. At j = 2, 2 − 2 = 0 stops i at 1 and j adds 1, the two 2s. At j = 3, 5 − 2 = 3 moves i to 3 and j adds 0. fast prints 1 where the brute force finds 3: both pairs exactly 2 apart are lost.

Small inputs with narrow ranges reach the bugs

A stress test finds a bug only when its inputs can reach it, so the generator matters more than the loop. These are the first six inputs that gen.cpp makes:

The inputs of seeds 1 to 6 Python · inputs_session.py

from session import run

# The first six inputs gen.cpp makes, each on one line: n and d, then the scores.
run("""
clang++ -std=c++23 -O2 gen.cpp -o gen
for s in 1 2 3 4 5 6; do echo "seed $s: $(echo $(./gen $s))"; done
""")

Output

$ clang++ -std=c++23 -O2 gen.cpp -o gen
$ for s in 1 2 3 4 5 6; do echo "seed $s: $(echo $(./gen $s))"; done
seed 1: 6 4 4 8 3 3 1 1
seed 2: 1 2 1
seed 3: 3 3 7 7 0
seed 4: 3 4 1 3 9
seed 5: 4 4 7 5 6 0
seed 6: 3 1 3 2 4

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 inputs_session.py

Repeated scores and scores exactly d apart turn up within a few seeds. Four habits make a stress test find such cases:

Small sizes keep a failing case readable and let the brute force run thousands of times a second.
Small value ranges make duplicates, equal scores and exact differences common, which is where boundaries break.
An independent brute force shares no code or shortcut with the solution, so the two cannot be wrong together.
A seed per case, printed with every failure, turns a random input into a test you can run again.

Key idea

Keep inputs small and ranges narrow, so that boundaries appear often, and print the seed of every failure.

The rest of a good stress-testing setup builds on these:

An in-process driver calls both solutions as functions, without starting programs for every case.
Making a failing test input smaller by removing or lowering one part at a time, and keeping each change only while the input still fails, so that a small case remains that shows the bug. removes and lowers parts of a failing input while it still fails. The smaller the case, the sooner it shows the bug.
Running a solution on every possible input up to a small size, in order of size, so that the first failure found is also a smallest one. tries every input up to a small size, so the first failure is also a smallest one.
A A program that judges an answer by checking it against the problem's rules, instead of comparing it with one expected output, for problems that accept more than one right answer. validates an answer instead of comparing it with one expected output, for problems with many right answers.
Structured generators make trees, graphs and permutations that are valid by construction.
A hand-made maximum test reaches what small inputs cannot, such as overflow and slowness.

Checkpoint

Check: Inputs that reach the bugs

Question 1 of 2 The problem allows scores up to 10^9, yet gen.cpp draws them from 0 to 9. Why?
Choose one answer.

The brute force cannot handle numbers above 9 Larger numbers would overflow the fast solution std::mt19937 only gives uniform numbers below 10 Small ranges make equal scores and exact differences common, and boundary bugs hide in those cases

Show the answer: Question 1 of 2

Answer: Small ranges make equal scores and exact differences common, and boundary bugs hide in those cases

A bug at the boundary, such as a pair whose scores differ by exactly d, needs an input with that exact difference. With scores from 0 to 9 and d from 0 to 4 such inputs are common; with scores up to 10^9 two random scores almost never differ by exactly d.
Question 2 of 2 Seed 6 makes d = 1 and the scores 3 2 4. What do brute.cpp and fast.cpp print for it?
Choose one answer.

brute 0, fast 0 brute 3, fast 1 brute 2, fast 0 brute 2, fast 2

Show the answer: Question 2 of 2

Answer: brute 2, fast 0

Sorted, the scores are 2 3 4. 3 − 2 = 1 and 4 − 3 = 1 are exactly d, so brute counts 2; 4 − 2 = 2 is too far. fast moves i on while a[j] − a[i] >= 1, so it counts neither pair and prints 0. A narrow range makes such inputs common: this is only the sixth seed.

Practise

Faster loops, failures that replay anywhere, and automatic shrinking Pro: opens with a Pro, Premium or Ultimate pass

A shell loop is fine for a first look, but it spends most of its time starting programs. This part moves the stress test into one process, measures how often the bug shows up for different value ranges, makes failures replay on any compiler, and shrinks a failing input automatically.

In this part:

A million cases in one process, with the bug rate per value range measured
Failures that replay on another compiler
Shrinking a failing case automatically

1 diagram · 7 runnable examples (C header, C++, Python) · about 9 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Beyond comparing outputs: exhaustive search, checkers and the bugs small tests miss Pro: opens with a Pro, Premium or Ultimate pass

Random comparison is one tool among several. This part enumerates every small input, judges answers with a checker when many outputs are right, shows the two kinds of bug that small random inputs cannot reach, and ends with an exercise on three more broken solutions.

In this part:

Generators for inputs with structure
Every input up to four scores, checked exhaustively
A checker when many answers are right
What small random tests cannot find, with numbers
Your turn: three solutions that pass both samples

10 runnable examples (C++, C++ (int_count.cpp), C++ (max_test.cpp), C++ (solution_a.cpp), C++ (solution_b.cpp), C++ (solution_c.cpp), Python) · about 10 minutes

Opening this part with your pass…Pro part. It opens with the same pass as the part above.

Interview questions

Fresher · Warm-up

What is a stress test in competitive programming, and which four pieces does it need?

A stress test runs your fast solution and a slow but obviously correct one, the brute force, on many small random inputs, compares their outputs and stops at the first input on which they differ. It needs four pieces: a generator that makes one input from a seed, the brute force, the solution under test, and a driver that runs both on each input and compares the answers, for example a shell loop with cmp. The driver prints the seed and the input with every failure, so the case can be replayed and checked by hand. Small sizes and narrow value ranges matter: they make duplicates and exact boundaries common, which is where most wrong answers hide.
Fresher to mid

Your solution passes the samples but gets Wrong Answer on test 23, which the judge does not show. Design a stress test to find a failing case: what do you generate, how do you make sure the brute force is right, and what do you do with the first difference?

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Mid to senior

Your stress test ran a million random cases without a single difference, but the judge still reports Wrong Answer. Name the likely reasons, and say how you would check each one.

Model answer, Pro. First step and follow-ups
Mid to senior

Your stress test reports a failure at seed 4711. A teammate builds the same files with another compiler and gets a different input for that seed, which passes. Why, and how do you design the generator and the report so that every failure replays everywhere?

Model answer, Pro. First step and follow-ups

Key takeaways

fast.cpp passed both samples while it lost every pair of scores exactly d apart.
A stress test needs a seeded generator, a trusted brute force, the solution and a driver that stops at the first difference.
The first failing case, read against the brute force’s count, named the bug: >= where “at most d” needs >.
Small inputs with narrow value ranges make boundaries common, and a seed per case makes every failure replay.

References

Working Draft, Programming Languages: C++ (N4950): [rand.dist.general], [rand.dist.uni.int], [rand.predef] (ISO/IEC JTC1/SC22/WG21)
POSIX.1-2024: cmp, compare two files (The Open Group and IEEE)
POSIX.1-2024: time, time a simple command (The Open Group and IEEE)
UndefinedBehaviorSanitizer (LLVM Project)
Simplifying and Isolating Failure-Inducing Input (Zeller and Hildebrandt) (IEEE Transactions on Software Engineering)

Report a problem with this lesson

In this module: C++ for DSA and competitive programming

Online judge C++ compilers, flags and limits Free lesson, Pro answers: 20 minutes
A clean C++ contest template, and habits to avoid Free core, Pro depth: 8 of 20 minutes free
Fast C++ input and output for online judges Free core, Pro depth: 8 of 20 minutes free
The STL toolkit for DSA in C++ Free core, Pro depth: 8 of 20 minutes free
Custom comparators and strict weak ordering Free core, Pro depth: 8 of 20 minutes free
C++ binary search: lower_bound and partition_point Free core, Pro depth: 7 of 20 minutes free
Overflow, __int128 and modular arithmetic Free core, Pro depth: 7 of 20 minutes free
C++ unordered_map: custom hashes and anti-hash tests Free core, Pro depth: 8 of 20 minutes free
Order-statistics trees with __gnu_pbds (GCC only) Free core, Pro depth: 8 of 20 minutes free
Deep recursion, stack limits and iterative DFS Free core, Pro depth: 7 of 20 minutes free
Stress testing contest solutions in C++ Free core, Pro depth: 11 of 30 minutes free

Your country

Stress testing contest solutions in C++

What you will learn

Before you start

What you will learn

Before you start

A solution can pass both samples and still be wrong

A stress test needs four pieces

The first failing seed names the bug

Small inputs with narrow ranges reach the bugs

Practise

Faster loops, failures that replay anywhere, and automatic shrinking Pro: opens with a Pro, Premium or Ultimate pass

Beyond comparing outputs: exhaustive search, checkers and the bugs small tests miss Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

What is a stress test in competitive programming, and which four pieces does it need?

Your solution passes the samples but gets Wrong Answer on test 23, which the judge does not show. Design a stress test to find a failing case: what do you generate, how do you make sure the brute force is right, and what do you do with the first difference?

Your stress test ran a million random cases without a single difference, but the judge still reports Wrong Answer. Name the likely reasons, and say how you would check each one.

Your stress test reports a failure at seed 4711. A teammate builds the same files with another compiler and gets a different input for that seed, which passes. Why, and how do you design the generator and the report so that every failure replays everywhere?

Key takeaways

References

Related tools