Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 63 ยท Contest Toolkit

Stress Testing with a Brute Force

Find bugs your samples miss: write a slow brute force, generate seeded random tests, compare answers automatically and shrink a failing case to its smallest form.

Every contestant knows the feeling: the samples pass, you submit, and the judge says "Wrong answer on test 7". You cannot see test 7, so you stare at the code and guess. Stress testing replaces guessing with a machine. You write a second, obviously correct but slow solution (the brute force), generate thousands of small random inputs, and run both solutions on each one. The first input where they disagree is a concrete, reproducible bug report.

This technique pays for itself even in a timed contest, because small inputs are enough to expose almost every logic bug. If you can reason about 5 numbers by hand, you can verify a fast solution against a brute force that simply tries everything. This lesson builds the whole loop in Python, step by step, and the project at the end of the track turns it into a reusable framework. It assumes you are comfortable with the templates and habits from the previous lessons.

The loop

A stress test has four parts, and each one is only a few lines long.

flowchart LR
  G["Generator<br/>(seeded random input)"] --> F["Fast solution"]
  G --> B["Brute force"]
  F --> C{"Same answer?"}
  B --> C
  C -- "yes" --> G
  C -- "no" --> R["Report and shrink<br/>the failing input"]

The stress loop: generate, solve twice, compare, and stop at the first disagreement.

  1. The fast solution is the one you intend to submit. Wrap it in a function that takes the parsed input and returns the answer, not one that reads standard input.
  2. The brute force is so simple that it is hard to get wrong. It may be exponential or cubic, as long as it handles inputs of size 5 to 10.
  3. The generator produces random small inputs from a seeded random number generator. A fixed seed makes every failure reproducible.
  4. The comparison runs both on each input and stops at the first mismatch.

Writing solutions as functions of parsed data, instead of printing directly, is what makes the loop possible. The same rule appeared in templates and habits.

A first stress test

Take a classic problem: given a list of integers, find the maximum sum of a non-empty contiguous subarray. A common fast solution is Kadane's algorithm, and a very common bug is starting the running best at 0, which quietly allows an empty subarray. The samples in the statement usually contain a positive number, so the bug survives them.

Python Stress test: buggy Kadane against a brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The loop stops quickly at an input where every number is negative. The brute force correctly says the best non-empty subarray is the largest single element (a negative number), while the buggy version answers 0. Notice what this gave you: a tiny, concrete input and both answers, with no judge involved.

Always generate inputs that are small and use a small value range. With values in -5..5 and length up to 6, duplicates, ties, zeros and all-negative lists appear constantly. With values up to 10^9 they almost never do, and bugs hide.

Writing a good brute force

A brute force is not "my solution but slower". It must be built on a different idea, otherwise it will share the bug. Good brute forces share these traits:

  • Direct from the statement. Try every subarray, every permutation, every subset, every pair. Do not apply any cleverness.
  • Independent. Do not reuse helper functions from the fast solution. A shared helper with a bug fools both sides equally.
  • Tiny constraints are fine. If the brute force is O(2^n) and you only test n up to 10, that is 1,024 steps per test.
  • Python helps. itertools.permutations, itertools.combinations and itertools.product express "try everything" in one line.

For example, a brute force for "minimum number of coins to make amount t" can simply enumerate how many of each coin to use, up to the largest possible count. It is slow and trustworthy, while the fast solution is a clever DP.

When you cannot write a brute force at all, you probably do not yet understand the statement. That is useful information too: write the brute force first and you will often notice a misreading before writing any fast code.

Generators that find bugs

Pure random input finds a lot, but you should shape it on purpose.

Goal Technique
Hit ties and duplicates Small value range such as 0..3
Hit negative numbers Range that is symmetric around zero
Hit boundaries Let n be 1, 2 or 3 often, not just uniform
Hit structure Generate sorted, reversed, all-equal or alternating lists
Hit trees and graphs Build a random valid structure, never random edges that may break the rules

A generator for a tree, for example, should attach each vertex i to a random earlier vertex, which always produces a valid tree:

Python Seeded generators for lists, trees and strings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

An alphabet of just "ab" is deliberate. Two letters create repeated substrings, palindromes and ties far more often than 26 letters would.

Seeds and reproducibility

Create the generator with random.Random(seed) and never use the global random functions inside a stress test. When a test fails, print the seed (or the test number, as above) together with the input. You can then rerun exactly that case while you debug.

A useful variation is to give each test its own seed: rng = random.Random(test_number). Then "test 517 failed" is enough information to reproduce it in isolation, without running tests 1 to 516 again.

Shrinking a failing case

Random failures are often noisy: a list of six numbers where only two matter. Shrinking repeatedly tries to make the failing input smaller while it still fails. Two simple moves cover most problems: delete one element, and replace a value by something closer to zero.

Python Shrink a failing input automatically

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The shrunk case is typically a single negative number such as [-1], which tells you immediately what the bug is. A one-element input is something you can trace by hand in ten seconds.

Shrinking must keep the input valid. If the problem promises n >= 1, never shrink to an empty list; that is why fails above returns False for an empty input.

When there is more than one right answer

Many problems accept any valid answer, for example "print any permutation with property P". You cannot compare outputs with ==. Instead write a checker: a function that takes the input and an output and says whether the output is valid. Then verify the fast solution's output with the checker, and compare its quality (such as the length) against the brute force's best. The local judge project uses the same idea.

Tips for using stress tests in a contest

  • Write the brute force while your solution is being thought about, not after the first Wrong Answer. It is often faster than rereading code.
  • Keep the stress harness in your template so setting it up costs two minutes.
  • Test at the extremes, n = 1 and n = 2, and also at the maximum value size if overflow matters in your language. The next lesson, edge cases and pitfalls, lists what to aim for.
  • Stress testing proves correctness only on the inputs you tried. It does nothing for speed, so separately estimate time as described in estimating time and memory.
  • If hundreds of thousands of random tests pass and the judge still fails, suspect input parsing, output format or a performance limit, not the algorithm.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why should a stress test use small inputs with a small value range?

    Bugs usually hide in special cases such as ties, zeros or n = 1. A small range makes those cases common, and a short failing input can be traced by hand.
  2. 2. What makes a good brute force?

    If both solutions share code or an idea, they share the same bug and will always agree. A brute force should follow the statement literally.
  3. 3. Why seed the random generator with a fixed value?

    A fixed seed (or a per-test seed) makes the same input appear again, so you can rerun the failing case after every code change.
  4. 4. A problem accepts any valid answer. How do you stress test it?

    When several outputs are correct, equality is the wrong test. A checker decides whether an output is valid for the given input.
  5. 5. What does shrinking do?

    Shrinking deletes elements and simplifies values while the failure persists, leaving a minimal case that is easy to understand.

Summary

  • Stress testing compares a fast solution with a slow, obviously correct brute force on many random small inputs.
  • Write both as functions of parsed input so a loop can call them directly.
  • Generators should use tiny sizes and tiny value ranges so special cases are common, and should always produce valid inputs.
  • Use random.Random(seed) so every failure is reproducible.
  • Shrink a failing input by deleting elements and moving values toward zero until it is minimal.
  • If many answers are valid, validate with a checker instead of ==.
  • Stress tests check correctness, not speed.

Next: Fast Input and Output in C++, Java and Python, and Reading from Files