12. Greedy — Homework Solutions

The answer .cpp files are in exercises/12/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/12/homework/solutions/01-kembalian.cpp
./jawab

Problem 1 — Making change

Problem. The fewest notes to pay k using rupiah denominations.

How to think about it. Straightforward greedy: take as many as possible of the largest denomination, and pass the remainder on to the next denomination. k / pecahan[i] gives the number of notes and k % pecahan[i] gives the remainder — two operations familiar since Chapter 03.

Greedy is correct here because every rupiah denomination divides the one above it or steps up in neat multiples (1,000 → 2,000 → 5,000 → 10,000 → …). That property is what makes taking a large denomination never a loss.

Walkthrough.

int pecahan[] = {100000, 50000, 20000, 10000, 5000, 2000, 1000};

long long lembar = 0;
for (int i = 0; i < 7; i++) {
    lembar += k / pecahan[i];
    k %= pecahan[i];
}
cout << lembar << "\n";

Tests.

The last row tests the data type: a value of k up to 10⁹ still fits in int, but the answer and the intermediate remainder are safer held in long long.

Common mistakes.

• Writing the denominations not in descending order. Greedy breaks immediately.
• Using int for k up to 10⁹ (it still fits) but forgetting that the number of notes can be large too — for k = 10⁹ the answer is 10,000 notes, still safe, but make long long a habit for accumulators.

Problem 2 — Activity scheduling

Problem. The largest number of activities that can be attended.

How to think about it. Sort by finish time, then take every activity whose start is not earlier than the finish of the last activity taken. The reason: the activity that finishes earliest leaves the most time for the rest.

The initial value of waktu ("time") must be smaller than every possible start time, so that the first activity is always taken.

Walkthrough.

sort(keg, keg + n, [](Kegiatan a, Kegiatan b) {
    return a.selesai < b.selesai;
});

int banyak = 0, waktu = -1000000000;
for (int i = 0; i < n; i++) {
    if (keg[i].mulai >= waktu) {
        banyak++;
        waktu = keg[i].selesai;
    }
}

Tests.

The second case is the counterexample for the "earliest start time" greedy, which would answer 1. If your answer here is 1, the sorting measure is still wrong. The first case tests a zero-duration activity — it is still one valid activity.

Common mistakes.

• Sorting two separate arrays (mulai[] and selesai[]), which breaks their pairing. Use a struct.
• Using > instead of >=, so an activity that starts exactly when another finishes gets rejected — even though the problem allows it.

Problem 3 — Boat loading

Problem. The fewest boats, two people per boat, total weight ≤ k.

How to think about it. The heaviest person must leave on some boat. The only question is: who can go with them? If anyone can, the most profitable choice is the lightest — because if even the lightest does not fit, nobody fits.

From this the two-pointer pattern follows: kanan ("right") always moves back one step (the heaviest person always leaves), and kiri ("left") only moves forward if that person comes along.

Walkthrough.

sort(b, b + n);

int kiri = 0, kanan = n - 1, perahu = 0;
while (kiri <= kanan) {
    if (b[kiri] + b[kanan] <= k) kiri++;
    kanan--;
    perahu++;
}

Tests.

Note that both end with one person leaving alone. That is expected: what decides it is not the number of people, but whether the lightest still fits together with the heaviest.

Common mistakes.

• Pairing the two lightest people first. For 20 30 50 70 90 with k = 100, that gives 4 boats, not 3.
• Writing while (kiri < kanan), so the last person leaving alone is never counted.

Problem 4 — A greedy that fails

Problem. Find the k values that make greedy wrong for coins {1, 3, 4}.

How to think about it. The function terbaik ("best") is written recursively: for every coin that fits, try taking that coin and solve the rest. This is a brute force, and it is fast enough up to k = 30. (Chapter 13 improves it into dynamic programming.)

The output.

k = 6:  greedy 3, terbaik 2
k = 10: greedy 4, terbaik 3
k = 14: greedy 5, terbaik 4
k = 18: greedy 6, terbaik 5
...

The pattern is clear: every k of the form 4m + 2 makes greedy wrong, because greedy takes 4-coins until 2 remains, then is forced to use two 1-coins, while two 3-coins would be more economical.

Walkthrough.

int greedy(int k) {
    int jumlah = 0;
    for (int i = 0; i < 3; i++) { jumlah += k / koin[i]; k %= koin[i]; }
    return jumlah;
}

int terbaik(int k) {
    if (k == 0) return 0;
    int hasil = BESAR;
    for (int i = 0; i < 3; i++) {
        if (k >= koin[i]) {
            int calon = terbaik(k - koin[i]) + 1;
            if (calon < hasil) hasil = calon;
        }
    }
    return hasil;
}

Tests. The answer program prints every k where the results differ:

k = 6: greedy 3, terbaik 2
k = 10: greedy 4, terbaik 3
k = 14: greedy 5, terbaik 4
k = 18: greedy 6, terbaik 5
k = 22: greedy 7, terbaik 6
k = 26: greedy 8, terbaik 7
k = 30: greedy 9, terbaik 8

Note the pattern: the failures appear every four steps, starting from 6. What is worth reflecting on is not the pattern, but the fact that out of the 30 values tested, greedy is correct on 23 of them. A solution that is correct 77 percent of the time still scores zero on an online judge.

Common mistakes.

• Concluding "greedy is always wrong for coin problems". The correct view: greedy depends on the set of coins.
• Writing terbaik without the base case k == 0.

Challenge — The wrong sorting measure

Problem. Show the failure of greedy by start time and by duration.

How to think about it. For sorting measures other than finish time, a single one-directional pass is not enough — every candidate must be checked against all activities already taken. That keeps the comparison fair: what is being tested is the sorting measure, not the way of checking.

The counterexample finder generates random activities with n between 2 and 5, then compares each greedy with a brute force over all 2ⁿ subsets.

Counterexamples found.

Greedy by earliest start time fails on five activities:

4 7   3 4   1 6   4 6   3 5

Greedy takes 1..6 first, and every other activity clashes with it — the result is 1. The best answer is 2, for example 3..4 together with 4..7.

Greedy by shortest duration fails on four activities:

7 10   9 12   6 10   5 9

The shortest duration is 7..10, and after it is taken, all the rest clash — the result is 1. The best answer is 2: 5..9 together with 9..12. A short activity sitting right in the middle can clash with two activities at once.

Meanwhile, the greedy by finish time was never wrong in 20,000 trials — consistent with its proof.

Common mistakes.

• Testing with a large n. The counterexamples found become hard to read; small data is actually more useful.
• Forgetting to copy the data again before calling the next greedy. Each greedy sorts the array, so the original order is lost and the comparison is not fair.

OSN-style exercises — walkthrough

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

Problem 1 — Service Queue

How to think about it. Look at what is actually being computed. Once the order is fixed, the first customer waits 0, the second customer waits the T of the first customer, the third customer waits the sum of the first two, and so on. So the service of the customer called i-th is counted N − i times in the total.

From there the answer is immediately visible: the longest service should be multiplied by the smallest possible number, so it is called last. Sort in ascending order.

Exchange argument. Take any best arrangement. Suppose there are two adjacent customers in the order x then y where x > y. Swapping them does not change the waiting time of any other customer at all — the total service before them stays the same, and the total service after them also stays the same. Only their own two waiting times change: originally 0 and x, becoming 0 and y, and y < x. So the swap always improves or keeps things equal. Since every arrangement that is not in ascending order must have such an adjacent pair, the ascending arrangement is certainly among the best.

Walkthrough.

sort(t.begin(), t.end());

long long berjalan = 0, total = 0;
for (int i = 0; i < n; i++) {
    total += berjalan;        // customer i waits this long
    berjalan += t[i];
}

cout << total << "\n";

The order of the two lines inside the loop decides the answer: the waiting time is recorded before that customer's own service is added.

Upper bound of the total: 10,000 × 200,000 × 199,999 / 2 ≈ 2 × 10¹⁴, so long long.

Tests.

Common mistakes.

• Adding t[i] before recording the waiting time, so every customer also waits for themselves.
• Sorting in descending order.
• Using int for the total.

Problem 2 — Checkpoints

How to think about it. The temptation is to sort by left endpoint. That is wrong: an interval that starts earlier can be much longer and tells you very little about where a checkpoint should stand.

The key to this problem is the right endpoint. Sort the intervals by their right endpoint. Take the first interval that is not yet monitored, then set up a checkpoint exactly at its right endpoint. That is the rightmost position still valid for that interval, so its chance of monitoring the following intervals is the greatest. There is no reason to place it further left.

After a checkpoint is set up, the following interval only needs one condition checked: whether the last checkpoint is still inside it, that is, whether titik ≥ Lᵢ (titik = "point"). The right endpoint does not need checking, because the ordering guarantees that the right endpoint of the next interval is not smaller.

Walkthrough.

vector<pair<long long, long long>> selang(n);   // (right, left)
for (int i = 0; i < n; i++) {
    long long l, r;
    cin >> l >> r;
    selang[i] = {r, l};
}

sort(selang.begin(), selang.end());

int banyak = 0;
long long titik = -1;
for (int i = 0; i < n; i++) {
    long long kanan = selang[i].first;
    long long kiri = selang[i].second;

    if (banyak == 0 || titik < kiri) {
        banyak++;
        titik = kanan;
    }
}

Storing the pairs as (kanan, kiri) (right, left) makes a plain sort order them by right endpoint directly, with no need to write a comparison function.

Tests.

The second case tests the ordering: if sorted by left endpoint, the interval 1 10 is processed first and its checkpoint stands at kilometer 10, so the other two intervals each need their own checkpoint — the answer becomes 3.

Common mistakes.

• Sorting by left endpoint.
• Placing the checkpoint in the middle of the interval, or at its left endpoint.
• Using int for coordinates up to 10⁹ — it still fits, but titik = -1 as the initial value must remain smaller than every Lᵢ, so the banyak == 0 check is safer than relying on the initial value.

Problem 3 — Load Pairing

How to think about it. Sort all the weights, then pair the smallest with the largest, the second smallest with the second largest, and so on.

Exchange argument. Consider the heaviest item, call it B. It must be paired with something, and its cart's load is B plus the weight of its partner. Since B cannot be avoided, the only thing that can be made smaller is its partner's weight — so the best partner for B is the lightest item. After both are taken, what remains is the same problem with 2(N − 1) items, and the same reasoning applies again.

Walkthrough.

sort(a.begin(), a.end());

long long terbesar = 0;
for (int i = 0; i < n; i++) {
    long long jumlah = a[i] + a[2 * n - 1 - i];
    if (jumlah > terbesar) terbesar = jumlah;
}

cout << terbesar << "\n";

The loop only goes up to n, not 2 * n: each iteration already handles two items at once. Writing 2 * n makes every pair get checked twice — the answer happens to stay correct, but it is a sign that the pairing structure is not yet understood.

Tests.

Common mistakes.

• Pairing neighbors after sorting — smallest with second smallest. For the sample that gives 13, not 9.
• Summing all the loads and then dividing. The question asks for the heaviest load, not the average.
• Using int: two weights of 10⁹ sum to 2 × 10⁹, which already exceeds the int limit.

If you are still stuck

• Not sure what to sort by → Chapter 12, the table of common sorting measures.
• Your greedy is correct on the samples but wrong on the judge → Chapter 12, the section How to convince yourself a greedy is correct.
• Paired data gets scrambled after sorting → Chapter 12, the note about struct.

The rule that must not be broken: test against a reference before submitting. An untested greedy is the fastest way to lose all the points for a problem.