11. Brute force

Brute force means trying every possibility and then picking the ones that satisfy the requirement. It is often underestimated, yet in OSN brute force has three uses: it is the full answer for problems with small constraints, a partial answer for problems with large constraints, and a reference for testing smarter solutions.

Steps for building a brute force

1. Decide what to try — every element? every pair? every subset? every ordering?
2. Count how many possibilities there are.
3. Compare with the constraints table in Chapter 10.
4. If it fits, write the loops. If not, look for an observation that cuts down the number of possibilities.

Steps 2 and 3 must not be skipped. A brute force that was not counted first is the most common cause of a Time Limit Exceeded verdict.

The number of possibilities for the forms covered in this chapter:

How fast the last two rows grow:

That is why the problem constraints are a hint that almost never lies: n ≤ 20 almost always means "try every subset", and n ≤ 10 almost always means "try every ordering".

Form 1: every element

There are n possibilities, so O(n). This is the simplest brute force — and it is often already the best solution.

// find the largest element
int besar = a[0];
for (int i = 1; i < n; i++) if (a[i] > besar) besar = a[i];

Form 2: every pair

There are n(n−1)/2 possibilities, so O(n²). Safe up to about n = 5,000.

// how many pairs sum to k?
int banyak = 0;
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        if (a[i] + a[j] == k) banyak++;

Note j = i + 1, not j = 0. This way every pair is counted once and no element is paired with itself. For n = 4, exactly six pairs are checked:

If j starts from 0, the count becomes 16: every pair is counted twice and every element is paired with itself. In a "how many pairs" problem, each of those two mistakes changes the answer.

Form 3: every subset

If each item has only two states — taken or not — then n items have 2ⁿ possibilities. Safe up to about n = 22.

The way to write it uses binary numbers: a number mask from 0 to 2ⁿ − 1 represents one choice, and bit i says whether item i is taken.

for (int mask = 0; mask < (1 << n); mask++) {
    long long jumlah = 0;
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i)) jumlah += a[i];   // bit i is set
    }
    if (jumlah == target) banyak++;
}

How to read it: every integer is at the same time a list of "yes/no" answers. For n = 3 and items a = {5, 7, 2}, the eight values of mask represent the eight choices:

Note that the rightmost bit is bit 0, that is, the first item. The binary column is exactly binary counting from 0 to 7, so the loop for (int mask = 0; mask < (1 << n); mask++) is guaranteed to visit every possibility exactly once — nothing is skipped and nothing is duplicated. That is the advantage of this method over writing n levels of nested loops, which cannot even be written when n is only known while the program runs.

The number of steps is n · 2ⁿ. For n = 20 that is about 21 million — still safe. For n = 30 it becomes 32 billion — not safe.

Form 4: every ordering

If what you are looking for is an arrangement (who goes first, which route is taken), the number of possibilities is n!. Safe only up to about n = 10 (10! = 3.6 million).

next_permutation from <algorithm> rearranges the contents into the next ordering in dictionary order, and returns false once there is no ordering after it. For {0, 1, 2} the orderings it produces are:

012  021  102  120  201  210

Because it only steps "forward", the data must start out sorted in ascending order — otherwise some orderings never appear:

#include <algorithm>

int p[] = {0, 1, 2, 3};
sort(p, p + n);
do {
    // p now holds one ordering
} while (next_permutation(p, p + n));

Pruning the possibilities

A brute force does not have to literally check everything. Two ways to prune:

Stop early. As soon as the answer is certain, exit.

for (long long i = 2; i * i <= n; i++)
    if (n % i == 0) return false;       // no need to continue

Compute the rest instead of searching for it. If two of three values have already been chosen, the third can often be computed directly — one nested loop disappears.

// a + b + c = k, count the triples: two loops are enough
for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) {
        int c = k - a[i] - a[j];
        // then look up c in a fast way
    }

Partial scores

OSN problems often have tiered constraints, for example:

• Subtask 1 (30 points): n ≤ 20
• Subtask 2 (30 points): n ≤ 2,000
• Subtask 3 (40 points): n ≤ 200,000

An O(2ⁿ) brute force solves subtask 1. An O(n²) brute force solves subtasks 1 and 2. Sixty points from a "dumb" solution is far better than zero points from a smart solution that never got finished.

Complete example: subset sum

Given n items with weights a[1..n] and a target k. How many ways are there to choose some of the items (zero items allowed) so that the total weight is exactly k? Constraints: n ≤ 20, a[i] ≤ 10⁹.

How many possibilities? Each item is either taken or not: 2²⁰ ≈ 1 million. Each possibility needs n steps to sum: 21 million. It fits.

The code:

int banyak = 0;
for (int mask = 0; mask < (1 << n); mask++) {
    long long jumlah = 0;
    for (int i = 0; i < n; i++)
        if (mask & (1 << i)) jumlah += a[i];
    if (jumlah == k) banyak++;
}
cout << banyak << "\n";

If the constraint is n ≤ 40, this approach dies — and the solution is to split the data into two halves, each 2²⁰. That technique is outside the scope of this book, but the way of thinking is the same: count first, then decide.

Homework

Most common mistakes

OSN tips

Small constraints are an open invitation. The following numbers almost always mean "try every possibility", and the problem setter put them there precisely so that brute force fits:

If the constraints look "too small", do not be suspicious — that is exactly the answer.

Brute force is a legitimate answer, not an embarrassing one. In problems with subtasks, a brute force answer solves the small-constraint subtasks and earns real points. A contestant who spends all their time looking for the perfect answer and submits nothing gets zero.

Write the brute force first even if you know the fast approach. It becomes the reference for testing the fast answer on random input, as in the Testing against a reference section of Chapter 10. Many subtle mistakes in a fast answer can only be found this way.

Arrange the loops so nothing is counted twice. To choose pairs or triples from distinct positions, start j from i + 1 and k from j + 1. This also avoids a division at the end and guarantees every combination is counted exactly once.

Prune as early as possible. A check that can be done in an outer loop should not be postponed to an inner loop. Moving one condition from the innermost level to the second level often cuts the running time by up to ten times, without changing the answer at all.

Know the upper bound of the answer before choosing a type. Brute force often sums a very large number of possibilities. The number of triples for N = 500 alone is already 20 million; if what is summed is values rather than counts, long long is almost always required.

Summary

• Brute force means trying every possibility; it is useful as the full answer for small constraints, a partial answer for large constraints, and a reference for testing fast solutions.
• The order of work: decide what to try, count how many, compare with the constraints table in Chapter 10, and only then write the code.
• The four standard forms: every element O(n), every pair O(n²), every subset O(2ⁿ), every ordering O(n!).
• Subsets are written with a binary mask; 1 << n is 2ⁿ and mask & (1 << i) checks bit i.
• All orderings are produced by next_permutation, and the data must be sorted first.
• Pruning can remove one level of loops, but it cannot turn 2ⁿ into n². If the constraints are far out of reach, a different idea is needed — Chapter 12 or Chapter 13.

OSN-style exercises

The following three problems are the three most frequent forms of brute force: every triple, every subset, and every ordering. Pay attention to the constraints — each was chosen so that it fits exactly.

The skeletons for all three are in exercises/11/osn/.

Problem 1 — Zero-Sum Triples

Given N integers. Count how many position triples (i, j, k) with i < j < k satisfy Aᵢ + A_j + A_k = 0.

Input format. The first line contains an integer N. The second line contains N integers.

Output format. One line containing the number of triples.

Constraints.

• 3 ≤ N ≤ 500
• −10⁹ ≤ Aᵢ ≤ 10⁹

Sample input

6
-1 0 1 2 -1 -4

Sample output

3

Explanation. The triples that sum to zero are positions (1, 2, 3) holding −1, 0, 1; positions (2, 3, 5) holding 0, 1, −1; and positions (1, 4, 5) holding −1, 2, −1. What is counted is triples of positions, so two triples with the same values but different positions are counted twice.

Skeleton: exercises/11/osn/01-tripel-nol.cpp

Problem 2 — Closest Subset

An organizer has N boxes of different weights and wants to load some of them into a car whose capacity is approximately S. They may choose any boxes, including choosing none at all.

Find the total weight closest to S — it may be less or more. If two choices are equally far from S, choose the smaller total weight.

Input format. The first line contains two integers N and S. The second line contains N integers.

Output format. One line containing the total weight closest to S.

Constraints.

• 1 ≤ N ≤ 20
• 1 ≤ S ≤ 10¹⁸
• 1 ≤ Aᵢ ≤ 10⁹

Sample input

4 10
3 34 4 12

Sample output

12

Explanation. Possible totals include 0, 3, 4, 7, 12, 15, 16, and so on. The closest to 10 is 12, at distance 2; the choice 7 is at distance 3.

Skeleton: exercises/11/osn/02-himpunan-terdekat.cpp

Problem 3 — Shortest Tour

A courier must depart from the first city, visit every city exactly once, and then return to the first city. The distances between cities are given as a table. Find the shortest possible total distance.

Input format. The first line contains an integer N. Each of the next N lines contains N integers; the j-th number on line i is the distance from city i to city j.

Output format. One line containing the shortest total distance.

Constraints.

• 2 ≤ N ≤ 8
• 0 ≤ distance ≤ 1000, and the distance from a city to itself is 0.

Sample input

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

Sample output

80

Explanation. One shortest tour is city 1 → 2 → 4 → 3 → 1, with a total of 10 + 25 + 30 + 15 = 80.

Skeleton: exercises/11/osn/03-tur-terpendek.cpp

Stuck or already done? Open the homework solutions page.