Stress Testing¶

In one sentence

When a submission fails on a test you cannot see, stop rereading the code. Generate tiny random tests, compare your solution against an obviously correct brute force, and let the computer hand you the smallest failing input.

Where we are

From the lesson of 20 Sep 2026, after 814C came back WA on test 6.

1. What problem does it solve?¶

Codeforces tells you that test 6 failed, not what test 6 is. Staring at the code is the slowest possible way to find out, and it fails completely for bugs that only fire on one extreme input.

Here is the bug that caused it. This precomputes f[c][m] = the longest run of colour c after repainting at most m characters:

for c in range(26):
    for l in range(n):
        cnt = 0
        for r in range(l, n):
            cnt += (a[r] != c)
            f[c][cnt] = max(f[c][cnt], r - l + 1)
    for i in range(1, n):          # <-- the bug
        f[c][i] = max(f[c][i], f[c][i - 1])

f[c] has n + 1 slots (indices 0 … n), but the running-maximum sweep stops at n - 1. So f[c][n] never receives it.

And f[c][n] is only ever written directly when all n characters differ from c — that is, when c does not occur in s at all. So every query with m = n on a colour that does occur returns 0, where the answer should be n.

The first five tests happened to contain no m = n query. Hence WA on test 6.

You will not find that by reading. You will find it in one second by running this:

2
ab
1
2 b

Expected 2, the code prints 0.

2. How it works¶

Four files, each with exactly one job:

file	job
`gen.py`	take a seed, print one random test to stdout
`brute.py`	slow but obviously correct; same stdin/stdout interface as `sol.py`
`sol.py`	the solution under test — paste it in unchanged
`stress.py`	generate, run both, compare stdout, stop at the first mismatch

The brute force must be a separate file

A tempting shortcut is to write a brute() function inside the solution and call it there. That does not work. The two would share the same input() call and the same parsed arrays, so any mistake in reading the input is made by both, and no comparison can see it.

Worse, in the example above the bug lives in f[c][n] — a cell of the precomputed table that a brute() function never touches. Only two independent processes, each reading from stdin and writing to stdout, compare the thing that actually gets judged.

3. Designing the generator¶

This is where stress testing is won or lost, and where beginners get it backwards.

Make the data small, not big

n = random.randrange(1, 7)    # not 1000
ALPHA = "ab"                  # not 26 letters

Small n — the brute force stays fast, and you can read the failing case by eye.
Narrow value range — duplicates, ties and collisions appear constantly. Wide random data almost never produces them.

A stress test can only find bugs your generator can produce

The bug above needs a query with m = n. If gen.py had said random.randrange(1, n) instead of random.randrange(1, n + 1), it would never be caught, no matter how many rounds you run.

So before writing the generator, ask out loud: which extreme cases am I allowing to appear? Empty ranges, m = n, all elements equal, n = 1, the answer being 0 — each one has to be reachable.

4. Template¶

Put all four in one folder, next to each other.

"""Random test generator.  Usage:  python3 gen.py <seed>  ->  one test on stdout"""
import random
import sys

random.seed(int(sys.argv[1]))

# The point: keep it tiny, small enough to read the failing case by eye.
n = random.randrange(1, 7)
ALPHA = "ab"                  # a small alphabet collides much more often

s = "".join(random.choice(ALPHA) for _ in range(n))

q = random.randrange(1, 5)
# m must be able to reach n, or the m = n bug can never show up.
queries = [(random.randrange(1, n + 1), random.choice(ALPHA)) for _ in range(q)]

out = [str(n), s, str(q)]
out += ["%d %s" % (m, c) for m, c in queries]
print("\n".join(out))

"""Brute force: slow, but obviously correct.

Reads stdin and writes stdout -- exactly the same interface as sol.py.
"""
import sys

input = sys.stdin.readline


def solve():
    n = int(input())
    s = input().strip()
    q = int(input())
    for _ in range(q):
        m_str, ch = input().split()
        m = int(m_str)
        c = ord(ch) - 97
        a = [ord(x) - 97 for x in s]

        best = 0
        for l in range(n):
            cnt = 0
            for r in range(l, n):
                cnt += (a[r] != c)
                if cnt <= m:
                    best = max(best, r - l + 1)
        print(best)


solve()

"""Stress-test driver.  Usage:  python3 stress.py [rounds]

Each round: gen.py makes a test -> feed it to sol.py and brute.py -> compare stdout.
Stops at the first mismatch and prints the failing input.
"""
import subprocess
import sys

PY_EXE = sys.executable
ROUNDS = int(sys.argv[1]) if len(sys.argv) > 1 else 1000


def run(script, data):
    return subprocess.run(
        [PY_EXE, script], input=data, capture_output=True, text=True
    ).stdout.split()


for seed in range(1, ROUNDS + 1):
    data = subprocess.run(
        [PY_EXE, "gen.py", str(seed)], capture_output=True, text=True
    ).stdout

    got = run("sol.py", data)
    want = run("brute.py", data)

    if got != want:
        print("=== mismatch on round %d ===" % seed)
        print("--- input ---")
        print(data.strip())
        print("--- sol.py ---")
        print(" ".join(got))
        print("--- brute.py ---")
        print(" ".join(want))
        sys.exit(1)

    if seed % 100 == 0:
        print("%d rounds passed" % seed)

print("all %d rounds agree" % ROUNDS)

To move this to another problem you rewrite gen.py and brute.py. stress.py never changes.

5. Running it¶

python3 stress.py 500

On the buggy version of 814C it stops immediately:

=== mismatch on round 1 ===
--- input ---
2
ab
1
2 b
--- sol.py ---
0
--- brute.py ---
2

Round 1. Two characters. A query with m = n = 2.

Change range(1, n) to range(1, n + 1) and the same command prints:

all 500 rounds agree

Two runs, two seconds, and the bug is both found and confirmed fixed. Compare that with resubmitting and waiting for the verdict.

6. Method 2 — AutoCp's built-in stress tester¶

AutoCp has this whole loop built into the IDE. View > Tool Windows > AutoCp, select the solution file, then open the Generator tab.

It replaces all three scripts:

AutoCp field	what goes in it	replaces
Generator program code	prints one test to stdout	`gen.py`
Solution program code	the slow, obviously correct reference; stdin to stdout	`brute.py`
Stress testing testcase amount	how many rounds to run	the loop in `stress.py`
Stop on first failing testcase	halt at the first mismatch	`sys.exit(1)` in `stress.py`

The file being tested is simply the file the tool window is attached to, so there is no sol.py to keep in sync.

How the generator gets its seed

AutoCp feeds the generator one number on stdin: the index of the current stress testcase. Read it and use it as the random seed, and the tests stay reproducible — round 7 is always the same test.

import random

seed = int(input())        # <-- instead of sys.argv[1]

random.seed(seed)

n = random.randrange(1, 7)
alpha = "ab"

s = "".join(random.choice(alpha) for _ in range(n))

q = random.randrange(1, 5)
qu = []

for _ in range(q):
    m = random.randrange(1, n + 1)
    c = random.choice(alpha)
    qu.append((m, c))

out = [str(n), s, str(q)]
out += ["%d %s" % (m, c) for (m, c) in qu]

print("\n".join(out))

That is the only line that differs from gen.py in §4.

Everything in §3 still applies without change. AutoCp gives you the plumbing, not the judgement: a generator that cannot produce m = n fails to find the bug just as silently here as it does in the scripts.

Which one to reach for

AutoCp — zero setup when you are already in the IDE, results land in the Test Runner UI. The fastest path during a contest.
The four files — plain Python, no IDE, no plugin. Keep them next to the solution, hand them to someone else, or run them anywhere. This is also the only version that survives when you are not on your own machine.

They do the same thing. Learn the files first, because they show you what the buttons are doing.

Both methods keep the reference in its own program

In the scripts this is brute.py, a separate process. In AutoCp it is the Solution program code pane, also run on its own. Either way the reference parses the input itself and prints its own answer — which is exactly what makes the comparison mean something. See §2.

7. Common mistakes¶

Calling the brute force from inside the solution under test

Defining brute() inside the reference program is fine — that whole program is the reference. The mistake is calling it from the solution you are testing and comparing the two results there. They then share the input parsing and the internal state, so the comparison is worth nothing, and a bug in a precomputed table the brute force never touches stays invisible. See §2.

Generating large random tests

n = 1000 makes the brute force too slow to run thousands of rounds, and makes a failing case unreadable when you finally get one. Small data finds more bugs, not fewer.

A generator that cannot produce the edge case

If the bug needs m = n, an empty range or two equal elements, and the generator never emits one, the stress test will happily report success forever.

Editing sol.py to make it work with the driver

Paste the submitted code unchanged. The moment you adjust it, you are testing something other than what the judge is running.

Comparing raw strings

The driver compares .split(), not the raw text, so trailing spaces and line-ending differences do not cause false alarms. If a problem accepts multiple valid answers, stress.py cannot compare directly — write a checker that validates sol.py's output instead.

8. The same tool tests an idea, not just an implementation¶

Everything above hunts for bugs in code that implements a strategy you already trust. Swap what brute.py does and the same four files test the strategy:

brute.py enumerates every possibility and returns the true optimum.
sol.py applies your greedy rule.

A wrong greedy rule almost never survives a few hundred tests with n <= 6. This is the practical version of "look for a counterexample before you try to prove it" — the habit from Sorting & Greedy.

Two uses, one tool:

`brute.py` is…	what you are testing
a slow but correct algorithm	your implementation
exhaustive enumeration	your idea