Stress Testing - Забони барномасозии C++ барои барномасозии рақобатӣ
Stress Testing
Stress Testing
Introduction
A solution may pass the samples and still be wrong. Samples are designed to explain the statement, not to cover every interaction between edge cases.
Stress testing searches for counterexamples automatically. We write two solutions to the same problem:
a simple trusted solution that is too slow for full constraints but correct on small inputs;
the fast solution that we want to verify.
Then we generate many small tests, run both solutions, and compare their answers. If they disagree, the tester prints the complete failing test. Instead of guessing where the bug might be, we receive concrete evidence.
Stress testing is especially effective for greedy algorithms, two pointers, binary search, dynamic programming optimizations, and any solution whose mistakes appear only on unusual small cases.
Running example
Given an array, find the maximum sum of a non-empty contiguous subarray.
For [3, -5, 4, 2, -1], the best subarray is [4, 2], with sum 6.
For [-5, -2, -7], the answer is −2. The subarray must be non-empty, so choosing no elements and returning 0 is not allowed.
A brute-force solution can try every left border and extend every right border. Kadane's algorithm solves the full problem in O, but a common incorrect implementation begins its answer at :
(
n
)
0
This code silently allows the empty subarray. It passes many tests containing positive values but fails when all values are negative.
The four parts of a stress test
A trusted brute force
The brute force should be as simple as possible. Its job is not to be fast; its job is to be obviously correct for small inputs.
For every left border l, start a sum at 0 and extend the right border r. Every non-empty subarray appears exactly once, so the largest observed sum is the answer.
The brute force takes O(n2) time, which is completely acceptable when generated tests use n≤10.
The candidate solution
Place the optimized logic in a separate function with the same input and output meaning as the brute force. Direct function calls make millions of small comparisons much faster and simpler than repeatedly reading and writing files.
The candidate must use the exact same problem rules. If one function allows an empty subarray and the other does not, their disagreement reveals a semantic bug rather than a performance issue—which is still valuable, but the intended meanings should be explicit.
A generator
The generator creates valid small tests. Small sizes let the brute force finish quickly and make any counterexample easy to inspect.
Random tests should include the important value categories:
negative, zero, and positive values;
repeated values;
minimum size;
values near special boundaries used by the algorithm.
Uniform random data is only a starting point. Good generators are biased toward structures that might break the candidate.
A comparer
For every generated test, calculate both answers. If they differ, print:
the complete input in a copy-pasteable format;
the brute-force answer;
the candidate answer;
optionally, the random seed or test number.
Then stop immediately. Continuing would only hide the first useful failure under more output.
Main algorithm
Algorithm:
The stress tester is not submitted to the judge. It is a local development program. After finding and fixing failures, submit only the actual optimized solution.
Mental model and detailed walkthrough
Suppose the generator produces
[-5, -2, -7].
The brute force checks every non-empty subarray:
[-5] has sum −5;
[-5, -2] has sum −7;
[-5, -2, -7] has sum −14;
[-2] has sum −2;
[-2, -7] has sum −9;
[-7] has sum −7.
It returns −2.
The buggy candidate starts with best = 0 and never lets its current sum fall below 0. It returns 0. The comparer reports:
This three-element input explains the bug much better than a large hidden wrong-answer test. The candidate has treated the empty subarray as valid.
We fix the algorithm by starting both cur and best at a[1]. At each later position, the best subarray ending there either begins at a[i] or extends the previous best ending at i−1:
cur=max(a[i],cur+a[i])
Now the candidate returns −2, matching the brute force.
Reproducibility
Use a fixed seed while debugging, such as mt19937 rng(712367). Every run then generates the same sequence of tests. A failure that appeared once will appear again at the same test number.
After the bug is fixed, try several different seeds or a time-based seed to explore other tests. If a time-based seed finds a failure, print that seed so the sequence can be reproduced.
Reproducibility is more valuable than maximum randomness. A counterexample that cannot be regenerated is unnecessarily difficult to investigate.
Making generators stronger
Pure random generation may almost never create the structure that breaks an algorithm. Add targeted test families:
all values equal;
all values negative;
strictly increasing or decreasing arrays;
alternating large and small values;
answers at the first or last position;
minimum and maximum allowed sizes;
values near overflow boundaries.
You can mix strategies: generate ordinary random tests most of the time, then deliberately produce one special family every few iterations.
For very small domains, exhaustive testing is even stronger. If n≤6 and each value is from −2 to 2, enumerate every possible array. This is still not a proof for arbitrary constraints, but it guarantees complete coverage of that bounded domain.
Reducing a counterexample
A small failing test is easier to understand. If the generator prints a larger one, try removing elements, decreasing values, or simplifying the structure while checking that the mismatch remains.
This process is called shrinking or minimizing the counterexample. It can be done manually, or automated by repeatedly attempting small changes and keeping any change that preserves the failure.
Often the minimal counterexample exposes the exact missing case: one element, all negative values, two equal endpoints, or an off-by-one boundary.
What stress testing can and cannot prove
Passing many tests increases confidence but does not prove correctness. Random generation can miss a rare structure forever. A correctness argument is still needed.
Stress testing and reasoning support each other:
the proof explains why all cases work;
the stress tester finds mistakes in the code or missing cases in the proof;
a counterexample immediately disproves an incorrect idea.
When a problem allows several different valid outputs, exact output comparison may be inappropriate. Compare objective values or validate both outputs with a checker. For floating-point answers, compare with an accepted tolerance rather than exact equality.
Implementation
1. Define brute(a):
1.1. Set best = negative infinity.
1.2. For l = 1..n:
1.2.1. Set sum = 0.
1.2.2. For r = l..n:
1.2.2.1. Add a[r] to sum.
1.2.2.2. Set best = max(best, sum).
1.3. Return best.
2. Define fast(a):
2.1. Set cur = a[1] and best = a[1].
2.2. For i = 2..n:
2.2.1. Set cur = max(a[i], cur+a[i]).
2.2.2. Set best = max(best, cur).
2.3. Return best.
3. Define generate():
3.1. Choose random n from 1..10.
3.2. Choose every a[i] randomly from -10..10.
3.3. Return a.
4. Repeat for many tests:
4.1. Generate a small array a.
4.2. Set expected = brute(a).
4.3. Set received = fast(a).
4.4. If expected != received:
4.4.1. Print the test, expected, and received.
4.4.2. Stop.
5. Print that all generated tests passed.
Mismatch
3
-5 -2 -7
Expected: -2
Received: 0
long long fast_buggy(const vector<long long> &a){ long long best = 0; long long cur = 0; for(int i = 1; i <(int)a.size(); i++){ cur = max(0LL, cur + a[i]); best = max(best, cur);} return best;}
#include <bits/stdc++.h>using namespace std;const long long inf =(1LL<< 62);mt19937 rng(712367);int rnd(int l, int r){ return uniform_int_distribution<int>(l, r)(rng);}long long brute(const vector<long long> &a){ int n =(int)a.size() - 1; long long best = -inf; for(int l = 1; l <= n; l++){ long long sum = 0; for(int r = l; r <= n; r++){ sum += a[r]; best = max(best, sum);}} return best;}long long fast(const vector<long long> &a){ int n =(int)a.size() - 1; long long cur = a[1]; long long best = a[1]; for(int i = 2; i <= n; i++){ cur = max(a[i], cur + a[i]); best = max(best, cur);} return best;}vector<long long> generate_test(){ int n = rnd(1, 10); vector<long long> a(n + 1); for(int i = 1; i <= n; i++){ a[i] = rnd(-10, 10);} return a;}void print_test(const vector<long long> &a){ int n =(int)a.size() - 1; cout << n << endl; for(int i = 1; i <= n; i++){ cout << a[i]<< ' ';} cout << endl;}int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); const int tests = 100000; for(int test = 1; test <= tests; test++){ vector<long long> a = generate_test(); long long expected = brute(a); long long received = fast(a); if(expected != received){ cout << "Mismatch on test "<< test << endl; print_test(a); cout << "Expected: "<< expected << endl; cout << "Received: "<< received << endl; return 0;}} cout << "All tests passed"<< endl; return 0;}
