The Most Important Idea In USACO Bronze: Brute Force

What is Brute Force?

Brute force is an important technique used in USACO Bronze problems. As the name suggests, brute force involves trying all possible situations in order to find or count the number of favorable situations. For instance, one can use a brute force approach to find a value in an array by iterating through all values in the aforementioned array and comparing them to the desired value.

In this article, time complexity and Big O notation will be mentioned. If you are not familiar with such concepts, consider reading usaco.guide’s page on time complexity.

Beginner Practice Problem

Let us look at USACO 2016 US Open Bronze Problem 1: Diamond Collector. Please think about the problem before continuing to read this article.

Once you have read the problem, it is important to immediately note that N is bounded by 1000, meaning we can comfortably have runtimes of O(N^3) and O(N^2). As a result, one should find a solution that likely has nested loops going from 0 to N. Indeed, we can brute force on the maximum number of diamonds in the case such that the i-th diamond is the smallest diamond in our case. To do this, we will once again need to loop through all of the diamonds in order to check how many diamonds larger than the i-th differ in size by at most K. My solution code in C++ is below.

Note that we could have sorted the diamonds array prior to our nested for loop to make writing out code easier; however, this is not necessary.

Key Takeaways

The two key takeaways of this problem are:

1. Look at the upper bounds of variables

Noting that N was upper bounded by 1000 immediately motivated us to think of an O(N^3) or O(N^2) solution, which easily suggests using nested loops--a common appearance in Bronze problems.

1. Have a specific goal when using brute force. 

While coming up with a solution to this problem, have a clear picture of exactly what you will be brute forcing. It is easy to accidentally try brute forcing on i, such that the i-th diamond will be used in the diamond case. However, this is not an easy problem to solve. Therefore, clearly define our algorithm before implementing it. This is crucial not only in brute force problems, but also all competitive programming problems you solve in the future. To be successful, you should clearly map out how your code will work before starting to write code in order to save an immense amount of time.

A Harder Brute Force Problem

Let’s look at USACO 2018 January Bronze Problem 2: Lifeguards. Please think about the problem before continuing to read this article.

We must focus on the upper bound of N: 100. This means we can have up to an O(N^4) solution. Upon reading the problem, we are immediately motivated to brute force on which lifeguard we choose to eliminate. Once again, paying attention to the upper bound of values is important; note that the pool is only open from t = 0 to t = 1000. This means we can comfortably loop through every single unit of time inside a loop going through every single lifeguard, nested inside the loop where we brute force on firing the i-th lifeguard. In order to find the amount of time that is still covered by the remaining shifts, we can then have an array pool[] of size 1001 such that pool[i] = true means that there is a lifeguard at time t = i and pool[i] = false means that there is not a lifeguard at time t = i. Our code will have approximately 10^4 x 10^3 = 10^7 operations, which is easily within the time constraints (in general, anything under 10^8 operations will be guaranteed to run in time). My solution code in C++ is below.

Brute Force Tips & Tricks

• Brainstorm possible time complexities of your code immediately (eg. O(N), O(N^2), O(NM), etc.)! This will help motivate you towards certain ideas (what to brute force on). In fact, this technique is extremely useful not only for brute force problems, but also for every single competitive programming problem you will ever do.

• Have a clear idea of the code you will write before actually writing it. Consider writing out some pseudocode. Though tedious, this will save you a lot of debugging time, and perhaps will even save you from having to completely rewrite your code because your original idea was incorrect. For example, in the Diamond Collector problem, if we forgot to restrict the i-th diamond as the lowest size, we may have overcounted our diamonds, forcing us to debug and re-write parts of our code.

• When the problem mentions finding some sort of minimum or maximum, it is likely that you should use brute force on some constraint that will result in the aforementioned minimum or maximum. In our Lifeguards problem, to find the maximum time that can still be covered, we brute force on the lifeguard that is going to be fired. *Note that finding minimums and maximums likely suggest binary search in problems in higher divisions, especially Silver.

• Practice! Consistent practice will help you become more and more familiar with brute force, allowing you to see which constraint to brute force on easier. The official USACO website and CodeForces have many practice problems.