10. Tracing and counting steps — Homework Solutions

Problems 1 and 2 are done on paper. The .cpp files for problem 3 through the challenge are in exercises/10/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 reproduce it yourself. The Test sections contain checked inputs and outputs for the coding problems.

Running one of the answers:

g++ -std=c++17 -O2 -o jawab exercises/10/homework/solutions/03-kasus-tepi.cpp
./jawab

Problem 1 — Tracing table

Problem. Trace the algorithm with three lines inside the loop for n = 5.

How to think about it. Three variables change, and the order matters: c is computed first from the old values of a and b, and only then are a and b shifted. That is why the table needs a c column.

Answer.

The output is 5. This algorithm computes the n-th term of the Fibonacci sequence — the same as fib_cepat in Chapter 06.

Common mistakes.

• Updating a first, then using the new a to compute b. The result becomes a sequence of powers of two, not Fibonacci.
• Printing b instead of a. The value is always one term too far.

Problem 2 — Choose an algorithm

How to think about it. Use the table in this chapter in reverse: from the constraint on n, find the step count that is still below about 10⁸.

Answer.

a. n ≤ 18 → safe up to O(2ⁿ) (2¹⁸ ≈ 262,000), even O(n · 2ⁿ). Example: trying all subsets of 18 items to find the best combination (Chapter 11).

b. n ≤ 2,000 → safe up to O(n²) (4 million). Example: checking all pairs, or a dynamic programming table of size n × n (Chapter 13).

c. n ≤ 300,000 → safe up to O(n log n) (about 5.5 million). Example: sort followed by one pass, like the greedy solutions in Chapter 12. O(n²) means 9 × 10¹⁰ steps: far too slow.

d. n ≤ 10¹² → the value is too large to go through one by one. What is safe is O(√n) (10⁶ steps, for example a primality test using the square root method) or O(log n) (fast modular exponentiation, Chapter 14).

Common mistakes.

• Answering based on the size of n alone without multiplying by the number of steps per element. n ≤ 300,000 with O(n) inside each test case, and 100 test cases, means 3 × 10⁷ — still safe, but it needs to be computed.

Problem 3 — Fix the edge cases

Problem. An average-of-positive-numbers program that fails on three edge cases.

How to think about it. Run those three edge cases first before reading the code: the results immediately show where the problem is. n = 1 gives an obviously wrong answer, and data with no positive numbers gives nan or inf.

Answer.

1. The loop starts at i = 1, so a[0] is never checked. For n = 1, no data is processed at all.
2. Division by banyak ("count") without checking banyak == 0. Division by zero on a double produces nan or inf, not an error message.
3. The accumulator jumlah ("sum") is of type int. For 100,000 numbers with value 10⁹, the sum is 10¹⁴ and it overflows.

Walkthrough.

long long jumlah = 0;
int banyak = 0;

for (int i = 0; i < n; i++) {
    if (a[i] > 0) {
        jumlah += a[i];
        banyak++;
    }
}

double rata = (banyak == 0) ? 0.0 : (double)jumlah / banyak;
cout << fixed << setprecision(2) << rata << "\n";

Tests.

The third row is the most dangerous of the three mistakes: without the banyak == 0 check, the program divides by zero and prints nan or inf — and on the online judge that is graded as a wrong answer, not a Runtime Error, so the cause is harder to track down.

Common mistakes.

• Fixing only one of the three. Edge cases are checked one at a time, not all at once.
• Using if (banyak > 0) to print, but forgetting to print anything when banyak == 0. The judge treats empty output as wrong.

Problem 4 — Count the steps

Answer.

This ratio is the way to check a guess without working out a formula: if n is doubled and the step count doubles too, the shape is linear; if it becomes four times, quadratic; if it only increases by one, logarithmic.

Tests. Run for n = 100 and then n = 200:

A O(n)       : 100        A O(n)       : 200
B O(n^2)     : 10000      B O(n^2)     : 40000
C O(log n)   : 7          C O(log n)   : 8
D O(n log n) : 700        D O(n log n) : 1600

Compare the left and right columns: A doubles, B quadruples, C increases by one, and D is a bit more than double. This is the "if n is doubled" table from Chapter 10, but this time computed by the program itself rather than estimated.

Common mistakes.

• Guessing fragment D as O(n²). Its inner loop multiplies by two rather than adding one, so it only runs log₂ n times.
• Using int for the O(n²) counter with a large n.

Challenge — Reference tester

Problem. Find the bug in the fast function using a random tester.

How to think about it. The core of this technique is small data. If n is limited to 6 and the values to −10 through 10, a failing example case is small enough to trace by hand. Generating random data of size 100,000 looks more like a real problem, but it does not help find the bug.

srand(12345) makes the sequence of random numbers the same on every run, so a failing case can be reproduced.

The bug. The loop bound i < n - 1 in cepat() ("fast") skips the last element. The tester finds it on the first attempt with the data 4 4 0 -4: the correct answer is 8, the answer from cepat() is 4, because -4 is never checked.

Walkthrough.

for (int uji = 1; uji <= 1000; uji++) {
    int n = rand() % 6 + 1;
    int a[10];
    for (int i = 0; i < n; i++) a[i] = rand() % 21 - 10;

    if (lambat(a, n) != cepat(a, n)) {
        cout << "berbeda: n = " << n << "\n";
        for (int i = 0; i < n; i++) cout << a[i] << " ";
        cout << "\n";
        break;
    }
}

The fix is one character: i < n - 1 becomes i < n.

Tests. The answer program prints:

versi lama gagal pada uji ke-1, n = 4
4 4 0 -4
lambat = 8, cepat_bug = 4
versi perbaikan cocok pada 1000 uji

Note how small the counterexample is: four numbers. That is exactly the purpose of a reference tester — not just telling you there is a bug, but giving you the smallest case that can be traced by hand.

Trace 4 4 0 -4 yourself. The largest value is 4, the smallest is −4, so the largest difference is 4 − (−4) = 8. The buggy version stops at i < n - 1 so it only sees 4 4 0: largest 4, smallest 0, difference 4. Once you see it on data this small, the location of the mistake is immediately clear — whereas on data with a hundred thousand numbers, all you see is two different large numbers with no clue at all.

Common mistakes.

• Comparing two functions that are both written with the same assumption. The slow version must be written as plainly as possible — check every possibility — so its correctness is not in doubt.
• Forgetting break after finding a difference, so the screen fills with output and the first case cannot be seen.

OSN-style exercises — walkthrough

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

Problem 1 — Maximum Subarray

Count first. The direct answer: try every pair of left and right ends, then sum the contents. That is N² / 2 segments, and summing the contents of each segment makes it N³. With a small improvement — adding one element at a time as the right end moves — the cost drops to N² = 4 × 10¹⁰ for N = 200,000. Still far too large.

The actual numbers, measured with clock() on the author's machine (g++ 13, -O2), using the N² version:

Note the pattern: N doubles, the time quadruples. That is the signature of N². The single-pass version below solves N = 200,000 in 0.0003 seconds on the same machine.

How to think about it. The key is one question: what is the largest sum of a segment that ends exactly at position i? The answer has only two possibilities — the segment contains only A[i] by itself, or A[i] is appended to the best segment ending at the previous position. Take the larger one.

Once the answer for every position is known, the answer to the problem is the largest among them all. Both can be computed in a single pass, without storing the data at all.

This technique is known as Kadane's algorithm, and it is actually the simplest form of the dynamic programming in Chapter 13.

Walkthrough.

long long terbaik = 0, sampaiSini = 0;

for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;

    if (i == 0) {
        sampaiSini = x;
        terbaik = x;
    } else {
        if (sampaiSini + x > x) sampaiSini = sampaiSini + x;
        else sampaiSini = x;

        if (sampaiSini > terbaik) terbaik = sampaiSini;
    }
}

cout << terbaik << "\n";

The first element is handled separately so that terbaik ("best") never starts at 0 — if it started at 0, the answer would be wrong on a sequence that is entirely negative.

Tests.

Common mistakes.

• Starting terbaik at 0, so a sequence that is entirely negative is answered 0. This is the number one mistake on this problem.
• Using int for the sum. 200,000 × 10⁹ = 2 × 10¹⁴.
• Resetting sampaiSini ("up to here") to 0 when it is negative, and then printing a terbaik that is never updated in the all-negative case.

Problem 2 — Pairs Summing to K

Count first. Checking all pairs is N² / 2 = 2 × 10¹⁰ comparisons. It does not fit.

How to think about it. The hint is in the value constraint: Aᵢ ≤ 10⁶, much smaller than the space of pairs. So use a counting array as in Chapter 07, then turn the question around: for each value v that appears, its partner must have the value K − v. The number of pairs formed is cacah[v] × cacah[K − v] (cacah means "count").

Two adjustments:

• Every pair is counted twice, once from the v side and once from the K − v side. That is why the result is divided by two at the end.
• If v and K − v are equal, the two chosen numbers come from the same slot, so the number of pairs is cacah[v] × (cacah[v] − 1) — and the division by two at the end turns it into the correct combination formula.

Walkthrough.

const int BATAS = 1000000;
long long cacah[BATAS + 1];          // outside main: too large for the stack

// ... read data, cacah[x]++ ...

long long hasil = 0;
for (int v = 1; v <= BATAS; v++) {
    if (cacah[v] == 0) continue;

    long long pasangan = k - v;
    if (pasangan < 1 || pasangan > BATAS) continue;

    if (pasangan == v) hasil += cacah[v] * (cacah[v] - 1);
    else hasil += cacah[v] * cacah[pasangan];
}

cout << hasil / 2 << "\n";

The check pasangan < 1 || pasangan > BATAS is mandatory: without it, a large K makes the program read cacah outside the array bounds.

Tests.

The number of pairs in the worst case — 200,000 numbers that are all equal — reaches about 2 × 10¹⁰, so the accumulator must be long long.

Common mistakes.

• Forgetting to divide by two, so every answer is doubled.
• Using cacah[v] * cacah[v] for the case v = K − v, which also counts the "pair" of a number with itself.
• Declaring long long cacah[1000001] inside main. Its size is 8 MB, which usually exceeds the stack, and the program stops before the first line.
• Using int for the result.

Problem 3 — Range Sum

Count first. Re-summing for every query takes up to N additions per query, so N × Q = 4 × 10¹⁰. It does not fit.

How to think about it. All the queries ask something similar, and the answers can be prepared once up front. Let pre[i] = the sum of A₁ through Aᵢ, with pre[0] = 0. Then the sum of A_L through A_R is pre[R] − pre[L−1]: the whole prefix up to R, minus the part that was not asked for.

The cost becomes N for the preparation plus one subtraction per query. This technique is called prefix sum and appears very often in OSN problems.

Numbering from 1 is used here precisely to avoid mistakes: pre[0] = 0 means L = 1 does not need to be handled as a special case.

Walkthrough.

vector<long long> pre(n + 1, 0);
for (int i = 1; i <= n; i++) {
    long long x;
    cin >> x;
    pre[i] = pre[i - 1] + x;
}

for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    cout << pre[r] - pre[l - 1] << "\n";
}

With Q up to 200,000 output lines, the two lines ios::sync_with_stdio and cin.tie at the start of main make a real difference, and endl must be replaced by "\n".

Tests. For the sample, the output is 15, 5, 4. Add two tests of your own: L = R = 1 (one element at the left end) and L = 1, R = N (the whole sequence), because both touch pre[0] and pre[n].

Common mistakes.

• Writing pre[r] - pre[l], which drops one element at the left end.
• Making pre of size n, so pre[n] is out of bounds.
• Using int for pre. 200,000 × 10⁹ = 2 × 10¹⁴.
• Storing the original array as well even though it is never used again — not wrong, but the memory and reading time can be saved.

If you are still stuck

• You do not know which line the mistake is on → Chapter 10, the section Tracing with a table and its four rules.
• The answer is correct but gets Time Limit Exceeded → Chapter 10, the table From constraints to choice of algorithm.
• The answer is correct on your computer but wrong on the judge → Chapter 10, the edge case table.

The two skills of this chapter are used throughout the rest of the book: tracing to check correctness, and counting steps to check speed.