10. Tracing and counting steps

Two skills separate participants who get full marks from those who get half: being able to trace an algorithm by hand to make sure the answer is correct, and being able to count its steps to make sure the program is fast enough. Both are done before pressing the compile button.

Tracing with a table

Tracing means running the algorithm on paper, one line at a time, while recording the contents of every variable. Make one column per variable and one row per step.

The algorithm being traced:

READ n              // n = 4
jumlah <- 0
i <- 1
WHILE i <= n
    jumlah <- jumlah + i * i
    i <- i + 1
PRINT jumlah

The table:

Note: the value of i in the first column is the value after the line i <- i + 1 has run. Fix your own convention and then stick with it, so the table does not confuse you.

Four rules so that a tracing table actually catches mistakes:

1. One row for each time the loop body runs, not one row per line of code.
2. One column for each variable that changes, plus one column for the result of the condition check.
3. Write the values as they are, even if they look wrong. The biggest temptation while tracing is to write the value that should appear, not the one the step actually produces.
4. Do not stop at the last iteration. Most off-by-one errors show up precisely at the final condition check, when the loop stops.

Test cases and edge cases

A program that is correct for the sample in the problem is not necessarily correct. Also test edge cases, meaning inputs at the ends of the constraints:

Most points lost in OSN are not due to a wrong algorithm, but due to one edge case that was never tested.

For each kind of problem, the edge cases can be guessed before the code is finished:

A quick way to generate edge cases: take the constraints in the problem, then try values exactly at the bound and one inside the bound. For 1 ≤ n ≤ 200,000, that means n = 1, n = 2, and n = 200,000.

Counting steps

Count how many times the innermost part of a program runs, as a function of n.

for (int i = 0; i < n; i++)              // n times
    cout << a[i];

for (int i = 0; i < n; i++)              // n * n times
    for (int j = 0; j < n; j++)
        ...

for (int i = 0; i < n; i++)              // n * (n-1) / 2 times
    for (int j = i + 1; j < n; j++)
        ...

for (int i = 1; i <= n; i *= 2)          // log2(n) times
    ...

What is usually written is only the growth shape, ignoring constant factors and smaller terms:

The reason constant factors are ignored: as n grows, the growth shape is what decides. An O(n²) program with a small constant still loses badly to an O(n log n) program once n reaches the hundreds of thousands.

How badly can be seen in the following table. The numbers are step counts, not seconds:

Look at the O(n²) column: from n = 1,000 to n = 100,000, the data grows 100 times but the work grows 10,000 times. This is why a solution that is "fast enough" on the sample can fail to finish at all on the real data.

A quick way to recognize the growth shape without counting: see what happens when n is doubled.

The step counts of some operations you have already used:

From constraints to choice of algorithm

The judge machine does roughly 10⁸ simple operations per second. The time limit of a problem is usually 1 or 2 seconds. From there, the constraint on n in the problem immediately tells you what kind of algorithm is expected:

The figure of 10⁸ per second is a deliberately safe estimate. A very simple loop can run much faster than that, while steps that access memory in a scattered way can be much slower. For choosing an algorithm, the safe estimate is what is used.

An example of reading it: a problem with n ≤ 200,000 almost certainly does not want nested loops. If your plan has the shape "check all pairs", there is an observation you have not found yet — for example "sort first", as in the example in Chapter 08.

Measuring real time

The estimates above still need to be checked. The easiest way on your own computer:

#include <ctime>

clock_t t0 = clock();
// ... the part being measured ...
double detik = (double)(clock() - t0) / CLOCKS_PER_SEC;
cerr << detik << " detik\n";

Note cerr, not cout: cerr output is not graded by the online judge, so it is safe to use for helper messages. Even so, make a habit of removing it before submitting.

When the constant factor matters too

The growth shape determines the choice of algorithm, but there is one thing that often makes a correct O(n) solution still run out of time: input reading speed. By default cin is set up so it can be used together with scanf, and that synchronization costs time. Two lines at the start of main turn it off:

ios::sync_with_stdio(false);
cin.tie(nullptr);

In a measurement of reading one million integers, the time dropped from 0.21 seconds to 0.04 seconds — about five times faster, without changing a single line of the algorithm. For problems with hundreds of thousands of input numbers, make a habit of writing both lines.

Testing against a reference

If a fast solution feels doubtful, test it against a slow solution that is clearly correct:

1. Write a slow version that is definitely correct (for example, checking all pairs).
2. Generate small random data.
3. Run both and compare their outputs.
4. Repeat hundreds of times. As soon as something differs, you have a small example case that can be traced by hand.

The key is step 2: the data must be small. A difference found on an array of four numbers can be traced by hand in a minute; a difference on an array of a hundred thousand numbers tells you nothing.

for (int uji = 0; uji < 1000; uji++) {
    int n = rand() % 6 + 1;                  // 1 to 6 elements
    for (int i = 0; i < n; i++) a[i] = rand() % 21 - 10;   // -10 to 10
    if (cepat(n) != lambat(n)) {
        cerr << "beda pada n=" << n << ":";
        for (int i = 0; i < n; i++) cerr << " " << a[i];
        cerr << "\n  cepat=" << cepat(n) << " lambat=" << lambat(n) << "\n";
        break;
    }
}

This technique finds bugs that are not visible when reading the code, and it is also the only practical way to test greedy conjectures in Chapter 12. An example is in exercises/10/04-uji-banding.cpp.

Homework

READ n
a <- 0
b <- 1
FOR i FROM 1 TO n
    c <- a + b
    a <- b
    b <- c
PRINT a

OSN tips

Read constraints as instructions, not as remarks. Before deciding on an approach, match the largest constraint in the problem against this table. The numbers use the benchmark of 10⁸ simple operations per second.

The constraint N ≤ 200,000 that appears again and again in OSN problems is the clearest signal: N² = 4 × 10¹⁰ is impossible, so what is wanted is a single-pass or single-sort solution.

State the cost before typing. Write one line on scratch paper: "N ≤ 2 × 10⁵, my approach is N², so 4 × 10¹⁰ — does not fit". A sentence that short prevents half an hour of typing an answer that is certain to get Time Limit Exceeded.

A slow answer is still worth submitting. If the problem is split into subtasks, an N² answer usually solves the subtasks with small constraints. Submit it first, then improve it. What you must not do is run out of time without submitting anything.

A slow answer is also a testing tool. How to compare automatically is covered in this chapter: run the slow version and the fast version on the same random input, and compare the outputs with diff. If they differ, you have a small failing example — far more useful than an unexplained Wrong Answer verdict.

Large input needs fast reading. For N in the hundreds of thousands and above, these two lines should become a habit at the start of main:

ios::sync_with_stdio(false);
cin.tie(nullptr);

After writing them, do not mix cin with scanf in one program.

Measure, do not guess. clock() from <ctime> is enough to measure the part suspected of being slow. Guessing which part is slow almost always misses, and optimizing a part that is not the cause changes nothing.

Summary

• Tracing with a table checks correctness; counting steps checks speed. Both are done before compiling.
• Tracing table: one row per iteration, one column per variable, write the values as they are, and do not stop before the final check.
• Mandatory edge cases: n = 1, all values equal, all negative, no answer, and the largest value allowed by the constraints.
• O notation hides constant factors and keeps the growth shape. A quick way to recognize it: see what happens when n is doubled.
• Safe estimate: 10⁸ simple operations per second. Use the constraints table to choose an algorithm before writing code.
• ios::sync_with_stdio(false); cin.tie(nullptr); speeds up reading large input without changing the algorithm.
• A reference tester with small random data finds bugs that are not visible when reading the code.

OSN-style exercises

Each of the following three problems has a direct answer that is easy to write and certainly too slow. Before typing, first count the steps of that direct answer, then look for a shape that fits.

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

Problem 1 — Maximum Subarray

Given a sequence of N integers. Choose a contiguous, non-empty segment so that the sum of its contents is as large as possible. Determine that sum.

Input format. The first line contains the integer N. The second line contains N integers A₁ A₂ … A_N.

Output format. One line containing the largest sum that can be achieved.

Constraints.

• 1 ≤ N ≤ 200,000
• −10⁹ ≤ Aᵢ ≤ 10⁹

Sample input

8
-2 1 -3 4 -1 2 1 -5

Sample output

6

Explanation. The segment 4 -1 2 1 sums to 6, and no other segment is larger. Note that the segment may not be empty: if all numbers are negative, the answer is the largest negative number, not 0.

Skeleton: exercises/10/osn/01-subarray-maksimum.cpp

Problem 2 — Pairs Summing to K

Given N integers and a number K. Count how many position pairs (i, j) with i < j satisfy Aᵢ + A_j = K.

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

Output format. One line containing the number of pairs.

Constraints.

• 2 ≤ N ≤ 200,000
• 1 ≤ Aᵢ ≤ 10⁶
• 2 ≤ K ≤ 2 × 10⁶

Sample input

5 7
1 6 3 4 2

Sample output

2

Explanation. The pairs are (1, 6) and (3, 4). The number 2 has no partner because 5 is not in the list. What is counted is pairs of positions: if the input is 2 2 2 2 with K = 4, the answer is 6, because there are six ways to choose two different positions.

Skeleton: exercises/10/osn/02-pasangan-berjumlah.cpp

Problem 3 — Range Sum

Given a sequence of N integers and Q queries. Each query contains two position numbers L and R; the answer is the sum of A_L through A_R, including both ends.

Input format. The first line contains two integers N and Q. The second line contains N integers. Each of the next Q lines contains two integers L and R.

Output format. Q lines, one answer per query.

Constraints.

• 1 ≤ N, Q ≤ 200,000
• −10⁹ ≤ Aᵢ ≤ 10⁹
• 1 ≤ L ≤ R ≤ N

Sample input

5 3
1 2 3 4 5
1 5
2 3
4 4

Sample output

15
5
4

Explanation. The first query sums the whole sequence, the second sums 2 + 3, and the third is just one number. Re-summing for every query takes N × Q = 4 × 10¹⁰ additions — work it out yourself before deciding.

Skeleton: exercises/10/osn/03-jumlah-rentang.cpp

Stuck or already done? Open the homework solutions page.