11. Brute force — Homework Solutions

The answer .cpp files are in exercises/11/homework/solutions/.

Open this page after trying on your own. Compare your line of reasoning with the How to think about it section, not the code line by line: two programs of different shape can both be correct, and what is worth copying is how to get there. The Tests section of each problem contains inputs and outputs that have been checked — run your own answer on those inputs before considering yourself done.

Running one of the answers:

g++ -std=c++17 -O2 -o jawab exercises/11/homework/solutions/01-pasangan.cpp
./jawab

Problem 1 — Pairs summing to k

Problem. Count pairs (i, j), i < j, with a[i] + a[j] == k.

How to think about it. Count first: n ≤ 2,000 means n²/2 = 2 million pairs. Safe. A two-loop brute force is already the full answer.

The key to correctness is j = i + 1. If it is written j = 0, every pair is counted twice and elements are also paired with themselves.

Walkthrough.

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++;

Tests.

The second row is an important edge case: equal values must not make the program stop counting. The answer is 6, that is, all 4 × 3 / 2 pairs. The third row tests n = 1, where the inner loop never runs.

Common mistakes.

• Using int for the counter when the problem allows an answer above 2 × 10⁹ (for example, all elements equal and k matching). For n = 2,000 the maximum is about 2 million, so int is enough here — but check the bound every time.
• Summing a[i] + a[j] in int when the elements approach 10⁹. Two elements that large already exceed the limit.

Problem 2 — Pythagorean triples

Problem. Count triples a < b < c ≤ n with a² + b² = c².

How to think about it. Three nested loops with the condition a < b < c give about n³/6 steps. For n = 300 that is 4.5 million — it fits easily.

But this is also an example of the pruning from the chapter: c does not need to be searched for. After a and b are chosen, c is computed as the square root of a² + b², then checked for being an integer. The number of steps drops to n²/2 = 45,000.

Walkthrough (three loops).

int banyak = 0;
for (int a = 1; a <= n; a++)
    for (int b = a + 1; b <= n; b++)
        for (int c = b + 1; c <= n; c++)
            if (a * a + b * b == c * c) banyak++;

Walkthrough (two loops).

int kuadrat = a * a + b * b;
int c = (int)sqrt((double)kuadrat);
for (int d = c - 1; d <= c + 1; d++)
    if (d > b && d <= n && d * d == kuadrat) banyak++;

The check from c − 1 to c + 1 is there because sqrt works with double and can be off by one. This habit saves many answers.

For n = 20 the answer is 6, for n = 300 the answer is 209.

Tests.

The three-loop version needs about 300³/6 ≈ 4.5 million steps for n = 300, while the two-loop version (file 02b-tripel-cepat.cpp) needs about 45,000. Both answer 209; the difference only shows when the bound is raised.

Common mistakes.

• Writing b = 1 and c = 1 as the lower bounds, then counting the same triple several times in different orders.
• Trusting (int)sqrt(...) without checking its neighbors.

Problem 3 — Subsets summing to k

Problem. Count the subsets whose sum is k, n ≤ 20.

How to think about it. 2²⁰ ≈ 1 million possibilities, each needing 20 addition steps: 21 million. It fits.

Every number mask from 0 to 2ⁿ − 1 is one subset. mask & (1 << i) checks whether item i is chosen.

Walkthrough.

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++;
}

Tests.

The second row is the heart of the problem: mask = 0 represents "take nothing" and its sum is 0, so it is counted when k = 0. A program that starts the loop from mask = 1 will answer 0 here.

Common mistakes.

• Writing 1 << n with n up to 31 or more; the result overflows. For large n use 1LL << n.
• Using int for jumlah ("sum"). Twenty elements of value 10⁹ give 2 × 10¹⁰.
• Forgetting that mask = 0 is the empty set with sum 0 — which must be counted when k = 0.

Problem 4 — Best ordering

Problem. The shortest route visiting every city, starting from city 0, n ≤ 8.

How to think about it. City 0 stays at the start, so only the order of the remaining n − 1 cities is arranged: at most 7! = 5,040 orderings. Each ordering needs n steps to sum its distances. Very light.

next_permutation produces the next ordering and returns false after the last ordering — which is why the data must be sorted before the do ... while loop starts.

Walkthrough.

int kota[16];
int m = 0;
for (int i = 1; i < n; i++) kota[m++] = i;
sort(kota, kota + m);

int terpendek = 2000000000;
do {
    int panjang = 0, sekarang = 0;
    for (int i = 0; i < m; i++) {
        panjang += jarak[sekarang][kota[i]];
        sekarang = kota[i];
    }
    if (panjang < terpendek) terpendek = panjang;
} while (next_permutation(kota, kota + m));

For the 4-city example in the homework file, the answer is 65 (route 0 → 2 → 1 → 3: 15 + 35 + 25 = 75; route 0 → 1 → 3 → 2: 10 + 25 + 30 = 65).

Tests.

The second case is a classic example: the shortest route visiting all four cities from city 0 is 0 → 1 → 3 → 2 with length 10 + 25 + 30 = 65. The number of orderings tried is (n−1)! = 6, few enough to check by hand — and that is exactly the point of testing with a small n.

Common mistakes.

• Also permuting city 0, so routes that do not start at city 0 get counted.
• Forgetting sort before do ... while, so some orderings are skipped.
• Forgetting the case n = 1, where there is no move at all.

Challenge — Partial scores

Problem. Write O(n²) and O(n) versions for the largest difference a[j] − a[i] with i < j, then compare them.

How to think about it. The slow version is the problem definition written as is. The fast version comes from one observation: when at position j, the best a[i] is the smallest among all positions before j. So a single variable terkecil ("smallest") updated along the way is enough.

The order inside the loop matters: first compute the difference using the old terkecil (which certainly comes from a smaller index), then update terkecil. If reversed, a[j] − a[j] gets counted and the condition i < j is violated.

Walkthrough.

int cepat(int a[], int n) {
    int terbaik = -2000000000;
    int terkecil = a[0];
    for (int j = 1; j < n; j++) {
        if (a[j] - terkecil > terbaik) terbaik = a[j] - terkecil;
        if (a[j] < terkecil) terkecil = a[j];
    }
    return terbaik;
}

Measurement results for n = 50,000 (the author's computer):

For n = 200,000, the O(n²) version needs about 16 times 0.57 seconds — about 9 seconds, far past the time limit. The O(n) version stays at a fraction of a millisecond. This is the constraints table from Chapter 10 in concrete form.

Tests. The answer program prints its own comparison results:

2000 uji cocok
lambat: 999886 (0.580913 detik)
cepat : 999886 (2.4e-05 detik)

The last two lines are for n = 50,000. The answers are the same, but the O(n²) version needs about 1.25 billion pairs while the O(n) version needs only 50,000 steps — in this measurement about twenty thousand times faster. This is the kind of partial score Chapter 11 means: the slow version is still correct and still earns points on small subtasks.

Common mistakes.

• Updating terkecil before computing the difference.
• Initializing terbaik = 0 (terbaik = "best"). For decreasing data such as 5 3 1, the answer is negative and that version is wrong.

OSN-style exercises — walkthrough

The answer files are in exercises/11/osn/solutions/.

Problem 1 — Zero-Sum Triples

Count first. The number of position triples from 500 values is 500 × 499 × 498 / 6 ≈ 2.07 × 10⁷. Below 10⁸, so three nested loops fit. Measured on the author's machine, the answer below finishes in 0.03 seconds for N = 500.

How to think about it. The only decision here is the loop bounds. Writing all three from 0 to N would count every triple six times and also count triples that use the same position twice. Starting j from i + 1 and k from j + 1 solves both at once, with no division and no extra checks.

Walkthrough.

long long banyak = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            if (a[i] + a[j] + a[k] == 0) banyak++;
        }
    }
}

The sum of three numbers of size 10⁹ reaches 3 × 10⁹, so a must be long long. If a is of type int, the sum overflows and triples that do not actually sum to zero may get counted.

Tests.

The third case is useful as a check of the loop bounds: the answer must be 4, the number of ways to choose 3 positions out of 4. An answer of 24 means the order was counted too; an answer of 64 means the same position was allowed to be reused.

Common mistakes.

• Starting j and k from 0, so triples get counted many times.
• Using int for the data.
• Using an int counter for the result — for N = 500 with all-zero data, the answer is over 20 million, which still fits in int, but the safety margin is thin.

Problem 2 — Closest Subset

Count first. N ≤ 20 means 2²⁰ = 1,048,576 subsets, and summing the contents of each takes up to 20 steps — about 2 × 10⁷ operations. It fits. Measured on the author's machine: 0.10 seconds for N = 20.

How to think about it. Every subset can be represented by one integer between 0 and 2^N − 1. Bit i being set means element i is chosen. That way "try every subset" becomes an ordinary loop.

Two things must be read carefully from the problem. First, the empty subset may be chosen, so the initial answer is 0 with distance S. Second, in a tie the smaller total is chosen — that condition has to be written; it does not appear by itself.

Walkthrough.

long long terbaik = 0;                      // empty subset
long long selisihTerbaik = s;               // |0 - s|

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

    long long selisih = jumlah - s;
    if (selisih < 0) selisih = -selisih;

    if (selisih < selisihTerbaik ||
        (selisih == selisihTerbaik && jumlah < terbaik)) {
        selisihTerbaik = selisih;
        terbaik = jumlah;
    }
}

The sum of 20 elements of value 10⁹ reaches 2 × 10¹⁰, and S itself can be 10¹⁸, so everything is long long.

Tests.

Third case: 3 is at distance 4 from 7, and 11 is also at distance 4. The answer is 3.

Common mistakes.

• Starting mask from 1 without setting up the empty subset as the initial answer, so the second case is wrong.
• Writing 1 << i with i up to 31 on type int — for N ≤ 20 it is still safe, but the 1LL << i habit holds up better when the constraints are raised.
• Forgetting the tie rule, so the answer depends on the enumeration order.

Problem 3 — Shortest Tour

Count first. The first city is fixed as the starting point, so what is tried is the ordering of the remaining N − 1 cities: 7! = 5,040 orderings for N = 8, each computed in 8 steps. About 40,000 operations — very light. Measured on the author's machine: 0.004 seconds.

Fixing the first city is not just a speedup: without it, every tour is counted N times, because the same tour can be written starting from any city.

How to think about it. next_permutation from <algorithm> turns a vector into the next ordering in alphabetical order, and returns false if it is already the last ordering. The standard pattern:

sort(v.begin(), v.end());
do {
    // check one ordering
} while (next_permutation(v.begin(), v.end()));

The contents of v here are the city numbers 1 to N − 1, which are already in ascending order when created, so sort is not needed. If the initial data is not sorted, sort is mandatory — without it some orderings are never tried.

Walkthrough.

vector<int> urutan;
for (int i = 1; i < n; i++) urutan.push_back(i);

long long terbaik = -1;
do {
    long long total = 0;
    int sekarang = 0;
    for (int kota : urutan) {
        total += d[sekarang][kota];
        sekarang = kota;
    }
    total += d[sekarang][0];

    if (terbaik < 0 || total < terbaik) terbaik = total;
} while (next_permutation(urutan.begin(), urutan.end()));

Note total += d[sekarang][0] at the end: the courier must return, and that last leg is very often forgotten.

Tests.

The second case checks the return leg: the answer is 10, not 5.

Common mistakes.

• Forgetting to add the distance back to the first city.
• Trying all N! orderings including the first city. The answer is still correct, but eight times slower and easier to get wrong.
• Starting terbaik from 0, so no tour is ever smaller.

If you are still stuck

• Not sure what to try → Chapter 11, its four forms: every element, every pair, every subset, every ordering.
• Confused by mask and bit operations → Chapter 11, the table of mask ↔︎ subset in binary.
• Your brute force runs out of time → Chapter 11, steps 2 and 3: count the number of possibilities first, then write the code.

The contest strategy to make a habit of: write the brute force first, secure the points for the small subtasks, and only then think about the full solution.