Complete Search (Bruteforce)
Written By Raouf Ould Ali
Hello Again! 👋
I hope you won't hate me after this problemset 😅
In this unit, we're diving into a very important problem-solving paradigm: complete search, also known as bruteforce.
What is Bruteforce? 🤔
The core idea behind bruteforce is simple: if you try every possible option in a problem, you'll eventually find the correct solution. However, it's not practical to try every possibility in most cases, as the set of possibilities is often too large to fully explore within the time limit. Still, there are times when bruteforce is useful for solving a subproblem or when you can manually reduce the number of possibilities by eliminating options that obviously won't work.
For example, if you're trying to find how many prime numbers less than are congruent to 6 modulo 13, there's no need to check numbers that aren't congruent to 6 modulo 13.
Why Practice Bruteforce?
It's also important to remember that while bruteforce might sound easy, it’s not something you can magically pull off during a contest and expect to score partial points. Like any technique, it requires practice so you can implement bruteforce solutions quickly and efficiently. In IOI contests, this technique often helps you grab some partial points, but if you spend two hours for just 6 points, you won’t get very far.
Also, ensure that your algorithm is as optimized as possible. Since bruteforce typically has a high time complexity, you don't want to lose extra time or hit a TLE (Time Limit Exceeded) error due to minor inefficiencies in your code.
Further Reading 📖
For more details about some implementations you may need, read pages 47 to 49 of Competitive Programmer's Handbook by Antti Laaksonen, watch this video and read pages 39 to 44 of Competitive Programming 2 by Steven & Felix.
Please make sure that you know how to loop over permutations, combinations, subsets, and how to use bitmasks for these purposes.
Problems 📚
I highly recommend you to solve at least 12 of these problems, and if you have times, try to solve all of them! (Don't worry, most of them are pretty easy, they only need some focus and some white paper to draft on.)
- JBOI - Puzzle (Mendo)
- AtCoder Beginner Contest 371: Problem C
- Card Trick 2 (Kattis)
- Online Judge Problem 533
- Black Friday (Kattis)
- Cudoviste (DMOJ)
- Calculating Dart Scores (Kattis)
- Medals (Kattis)
- Dance Recital (Kattis)
- Dreamer (Kattis)
- Geppetto (Kattis)
- Communication (Kattis)
- Good Morning (Kattis)
- Paintings (Kattis)
- CSES: 2164
- Codeforces: Problem 1692F
- DMOJ: AC19P4
- DMOJ: BF2
- DWITE 07C2P1 (DMOJ)