Let’s think it through · Start with a story
The girl cannot think of a fast method yet, so she lists all four possibilities. The robot says, “Having a correct answer for small cases is useful.”
Break down the process
- List candidatesCover the full range
- Check each oneKeep valid answers
- Get a referenceCorrect results for small inputs
- OptimizeCompare against the reference
Brute force can help you understand a problem and give an optimized algorithm a small-scale reference.
It should be clear and easy to check, not deliberately complicated. Comparing two methods on the same input can expose errors.
01Why think of the “clumsiest method” when you are stuck?
Because a “clumsy but correct” method can take you from having no idea at all to at least knowing how to get an answer.
02Step 1: List all the candidates
For example, for the Two Sum problem, you could start by enumerating every pair of indices:
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Check a[i] + a[j]
}
}03What is brute force good for?
A correct starting point
Begin with a method that works.
Understanding the search space
How many candidates are there?
Finding repeated work
What is being calculated many times?
Cross-checking
Validate an optimized algorithm on small inputs.
04What is cross-checking?
In contest practice, you can compare:
- A simple, trustworthy brute-force program
- A new, faster algorithm
Run both on the same batch of random small inputs. If their outputs differ, at least one of them has a problem.
05When is brute force good enough?
It depends on the input size.
If n is small, even O(n²) or O(2^n) may be completely acceptable within the stated constraints.
06When should you keep optimizing?
If your estimate shows that brute force does far more work than the time limit allows, ask:
What you have learned
- When you are stuck, start by designing a correct brute-force method.
- Brute force can help you understand the candidate space.
- It can also serve as a baseline for checking an optimized algorithm.
- Whether you need to optimize depends on the input size.
- Moving from brute force to optimization is an important problem-solving path in informatics competitions.
Next: How Do We Spot Repeated Work?
Your turn
If a fast algorithm and a brute-force algorithm give different results on the same small input, does that prove the fast algorithm is wrong?
Have an answer? Click to see the explanation
Not necessarily; the reference implementation could also be wrong. Work the example out by hand, then check both implementations against the problem statement.