08. What is computational thinking — Homework Solutions

Problems 1 to 3 are done on paper. The .cpp files for problem 4 and the challenge are in exercises/08/homework/solutions/.

Open this page after trying on your own. For the paper problems, write your answer first, then compare — reading someone else's answer feels clear even when you could not necessarily reproduce it yourself. The Tests section holds checked inputs and outputs for the coding problems.

Running one of the answers:

g++ -std=c++17 -O2 -o jawab exercises/08/homework/solutions/04-penumpang.cpp
./jawab

Problem 1 — Abstraction

Problem. Rewrite three story problems as one "given ... print ..." sentence.

How to think about it. Discard the names of characters, objects, and units. Keep: what is given (the shape of the data) and what is asked (the shape of the answer).

Answer.

a. Given n numbers, print their total minus their largest value.

b. Given n pairs of numbers naik[i] and turun[i], print the largest value ever reached by the running sum (naik − turun) after each pair is processed.

c. Given n, print how many of the numbers 1 to n have an odd number of divisors.

Form (c) is deliberately still halfway: "the switch is pressed once for each divisor" is the result of the first abstraction. The second abstraction — that an odd number of divisors only happens for square numbers — is done in the challenge.

Common mistakes.

• Keeping the story ("chicken", "bus stop") in the new sentence. If nouns from the story are still there, the abstraction is not finished.
• Answering with code. At this stage the answer is still a sentence.

Problem 2 — Decomposition

Problem. Break the bus problem into steps.

How to think about it. Each step must be small enough to be written in a few lines of code, and clear enough to be tested on its own.

Answer.

1. Read n.
2. Set up two accumulators: di_dalam (current passengers, literally "inside") and terbanyak (the highest record, literally "most"), both with value 0.
3. Repeat n times: read a pair naik and turun.
4. At each stop: subtract turun from di_dalam, then add naik — in the order the problem states.
5. Compare di_dalam with terbanyak; if it is larger, update the record.
6. After all stops, print terbanyak.

Note that steps 4 and 5 are two already familiar patterns: accumulation and the running champion.

Common mistakes.

• Storing all the data in an array first. Allowed, but unnecessary: the answer can be computed while reading.
• Checking the record before updating di_dalam, so the last stop is never counted.

Problem 3 — Pattern recognition

Answer.

a. "how many ... are divisible by 7" → loop + counter, with the condition % 7 == 0.

b. "two numbers whose product is largest" → nested loops over all pairs. If n is large, sort first and then compare the product of the two largest with the product of the two smallest (two large negative numbers can win).

c. "how many 7s among the digits of 1 to n" → a loop over 1..n that processes the digits inside it with % 10 and / 10.

d. "the most contests without overlapping schedules" → sort + greedy. This is the activity scheduling problem covered in Chapter 12.

Common mistakes.

• For (b), immediately answering "take the two largest numbers". For data that may be negative, that answer is wrong.

Problem 4 — Bus passengers

Problem. Print the largest number of passengers ever inside the bus.

How to think about it. Follow the decomposition from problem 2. No array is needed: two variables are enough, because the record can be updated while reading.

Walkthrough.

int di_dalam = 0, terbanyak = 0;

for (int i = 0; i < n; i++) {
    int naik, turun;
    cin >> naik >> turun;

    di_dalam -= turun;
    di_dalam += naik;
    if (di_dalam > terbanyak) terbanyak = di_dalam;
}

cout << terbanyak << "\n";

Check with an example: 5 0 → 5, 3 2 → 6, 1 4 → 3. The record is 6.

Tests.

Each input line contains naik then turun for one stop. The third row is the most important check: the largest count (6) occurs in the middle of the trip, not at the last stop. A program that only prints the bus's occupancy at the end will answer 0.

Common mistakes.

• Letting passengers on first and then off, so the record is too large.
• Printing di_dalam at the end instead of terbanyak.

Challenge — Lamps

Problem. Count the lamps that are on, then find the pattern.

How to think about it. The direct version is simple: for each i, flip the state of all its multiples. The amount of work is n/1 + n/2 + n/3 + ... ≈ n ln n, so for n = 1,000,000 it still finishes quickly.

Walkthrough.

for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i)
        nyala[j] = !nyala[j];

int banyak = 0;
for (int i = 1; i <= n; i++) if (nyala[i]) banyak++;
cout << banyak << "\n";

The results:

The pattern: the answer is the integer part of √n.

Why. Lamp number x is pressed once for each divisor of x. Divisors always come in pairs: if a divides x, then so does x / a. So the number of divisors is even — except when a = x / a, that is, when x is a square number. Only lamps with square numbers are pressed an odd number of times and end up on. The number of square numbers from 1 to n is ⌊√n⌋.

Once that pattern is found, the whole program becomes one line:

cout << (int)sqrt((double)n) << "\n";

This is the purest form of this chapter: observing a pattern replaces computation. In OSN, the difference between an n log n answer and an O(1) answer is often a one-sentence observation like this.

Tests.

That last column is the pattern. Once the pattern is found, the whole program can be replaced by one line — and the difference is large: the direct method takes about n log n switch presses, whereas computing the square root takes one operation.

Common mistakes.

• Using sqrt without care on large numbers. For very large n, (int)sqrt(...) can be off by one; check it with while ((long long)(akar + 1) * (akar + 1) <= n) akar++;.
• Concluding a pattern from only one value of n. Three data points at minimum, and the pattern still has to be proven with a reason.

OSN-style exercises — walkthrough

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

Problem 1 — Mango Harvest

The abstraction. Given N numbers and a threshold K, run an accumulator that grows at each step and is emptied each time it reaches K; print how many times it was emptied and what remains.

The orchard, the market, and Pak Dengklek's laziness do not make it into the code.

How to think about it. The only things to remember are the current warehouse contents and a sales counter. The Aᵢ values do not all need to be stored: each one is used once and then no longer needed. Realizing this turns the problem from "an array of 200,000 elements" into "two variables".

Check the type: just before being emptied, the warehouse holds at most K − 1 + Aᵢ, which can approach 2 × 10⁹ — beyond int.

Walkthrough.

long long simpanan = 0;
int penjualan = 0;

for (int i = 0; i < n; i++) {
    long long a;
    cin >> a;
    simpanan += a;
    if (simpanan >= k) {
        penjualan++;
        simpanan = 0;
    }
}

cout << penjualan << " " << simpanan << "\n";

Tests.

The second case matters: the answer is not 0 0. The remainder that was never sold must still be printed.

Common mistakes.

• Using > instead of >=. The problem statement says "reaches K fruits or more".
• Forgetting to empty the warehouse after a sale.
• Using int for simpanan ("stock").

Problem 2 — New Record

The abstraction. Given a sequence of N numbers, print how many numbers are smaller than all the numbers before them.

How to think about it. Comparing each runner with all previous runners takes N² = 4 × 10¹⁰ comparisons. But "faster than all previous runners" means the same as "faster than the fastest so far" — and that fastest time only needs to be kept in one variable. The problem is solved in a single read.

The first runner is handled as a special case, because there is nothing to compare against yet.

The word faster must be read carefully: a time equal to the record does not count, so the comparison is <, not <=.

Walkthrough.

long long terbaik = 0;
int rekor = 0;

for (int i = 0; i < n; i++) {
    long long t;
    cin >> t;
    if (i == 0 || t < terbaik) {
        rekor++;
        terbaik = t;
    }
}

cout << rekor << "\n";

Tests.

Common mistakes.

• Using <=, so equal times are counted too and the third case answers 4.
• Setting terbaik ("best") to 0 and comparing right away, so the first runner is never counted.
• Storing all the times in an array and then comparing pairwise.

Problem 3 — Rotating Candy

The abstraction. Given N and M, print ((M − 1) mod N) + 1 and ⌊(M − 1) / N⌋ + 1.

How to think about it. Simulation is both the correct answer and an impossible one: M can be 10¹⁸, while one second is only enough for about 10⁸ steps. A constraint that large always means the answer is a formula.

The pattern shows up when you number the candies. Candy 1 goes to child 1, candy 2 to child 2, candy N to child N, candy (N + 1) back to child

1. So candy m goes to the child numbered "the remainder of m divided by N" — with one adjustment: a remainder of 0 means child N, not child 0.

That adjustment is written neatly as (m - 1) % n + 1: first shift the numbering to 0 through N − 1, compute the remainder, then shift back to 1 through N.

Child 1 receives candy 1, candy (N + 1), candy (2N + 1), and so on. The count is ⌊(M − 1) / N⌋ + 1 — the same shift.

Walkthrough.

long long n, m;
cin >> n >> m;

long long terakhir = (m - 1) % n + 1;
long long bagianPertama = (m - 1) / n + 1;

cout << terakhir << " " << bagianPertama << "\n";

Tests.

The third row is the edge case N = 1: all the candy goes to the same child. The fourth row makes sure large divisions stay correct.

Common mistakes.

• Writing m % n without the adjustment, so multiples of N answer 0 — a child number that does not exist.
• Computing the first child's share as m / n, which is wrong whenever there is a remainder.
• Writing the simulation for (long long i = 0; i < m; i++). Logically correct, but it will never finish.

If you are still stuck

• Story problems feel complicated → Chapter 08, the Abstraction section and the story → core table.
• You know the answer but not where to start → Chapter 08, the Decomposition section.
• Not sure your plan is fast enough → Chapter 08, the complete example from problem to plan, then Chapter 10.

The habit to build from now on: before writing code, first answer the five questions in the Checklist before writing code in Chapter 08.