08. What is computational thinking

Part 1 trained your hands: syntax, compiling, arrays. This part trains your head. Computational thinking is the way of structuring a problem so that a computer can solve it — and in OSN, this is what determines your score, not typing speed.

There are four habits that make it up.

1. Decomposition: breaking into small parts

Big problems can rarely be solved all at once. Break them into steps that can each be tested on their own.

Example problem: given n numbers, print how many distinct pairs have a sum equal to k.

The breakdown:

1. Read n, k, and n numbers. (Possible since Chapter 07.)
2. Decide what "distinct pairs" means — are (i, j) and (j, i) counted once or twice?
3. Check all pairs and count those whose sum is k.
4. Print the count.

Once broken down, none of the steps is hard. The difficulty of a problem usually lies in steps 2 and 3, not in the code.

A good decomposition produces steps that can be tested individually. Note that step 1 can already be run and checked before step 3 is written at all:

int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
cerr << "terbaca: n=" << n << " k=" << k << " a[0]=" << a[0] << "\n";

This habit — running a half-finished program to make sure the parts that already exist are correct — saves a lot of time when something goes wrong, because you know exactly which parts cannot yet contain the mistake.

2. Pattern recognition: looking for what repeats

After working through many problems, the same shapes show up again and again:

Recognizing patterns does not mean memorizing code. It means that when you read a new problem, you immediately recall an old problem with the same shape.

That table grows on its own as you practice, and the way to grow it is simple: every time you finish a problem, write one line in your notebook containing the shape of the problem's wording and the tool used. After fifty problems, those notes are far more useful than fifty code files, because what you look for during a contest is the idea, not the code.

3. Abstraction: discarding what does not matter

OSN problems are often wrapped in a story: merchants, cakes, trains, plants. The first task is to discard the story and keep the core.

Bu Dengklek has n buckets containing fish. Bucket i contains a[i] fish. She wants to move all the fish into one bucket, and each move of one fish takes one second. What is the minimum number of seconds needed?

Discard the story: given n numbers, what is their total minus the largest value? After abstraction, the answer is two lines of code.

A few more examples, story discarded, core kept:

4. Algorithms: a definite sequence of steps

An algorithm is a sequence of steps that is clear, finite, and produces the same answer every time it runs on the same input. "Find the best one" is not an algorithm. "Go through all the data, keep the largest value seen so far, print that value" is an algorithm.

Three properties an algorithm must have:

The same algorithm can be written in any language — Indonesian, a flowchart, pseudocode, C++. What OSN grades is the algorithm; C++ is only the tool for running it.

How to write one down is covered in Chapter 09 (flowcharts and pseudocode), and how to check one in Chapter 10.

Reading an OSN problem

Contest problems almost always have the same parts. Get used to reading them in the following order — not top to bottom:

1. Input and output format. This determines the shape of your code.
2. Constraints. This determines which algorithm is allowed. n ≤ 1000 and n ≤ 1,000,000 are two different problems.
3. Sample cases. These confirm that your understanding is correct. Work them out by hand before writing code.
4. The story. Read last, to fill in details that are still unclear.

An example problem excerpt and what you should conclude from each part of it:

Input. The first line contains two integers n and k. The second line contains n integers a₁ … aₙ. Output. One integer, the answer. Constraints. 1 ≤ n ≤ 200,000, 1 ≤ aᵢ ≤ 10⁹.

What is known immediately, even before the story is read:

• The shape of the code: cin >> n >> k; then one loop reading n numbers.
• The output is one line with one number — no sentence, no units.
• n up to 200,000 means nested loops are impossible; what is wanted is around O(n log n) (Chapter 10).
• aᵢ goes up to 10⁹ and may be summed up to 200,000 times, so the sum accumulator must be a long long.
• n can be 1 — an edge case that must be tested.

Those five conclusions come from reading two short paragraphs, before thinking about the idea at all.

A complete example: from problem to plan

Bu Dengklek's Cakes. Bu Dengklek bakes n cakes with sweetness levels a[1..n]. She wants to choose two different cakes so that the difference in sweetness is as small as possible. Print that smallest difference. Constraints: 2 ≤ n ≤ 200,000, 1 ≤ a[i] ≤ 10⁹.

Abstraction. Given n numbers, print the smallest difference between two numbers at different positions.

First plan (direct). Check all pairs, record the smallest difference. The number of pairs is about n²/2 — for n = 200,000 that is 2 × 10¹⁰ steps. Too slow.

Pattern recognition. "Smallest difference" is a reminder of sorted data: in a sorted sequence, the two most similar numbers must be neighbors. If they are not neighbors, there must be a number between them that is more similar to one of them.

Second plan. Sort (n log n), then go through once, comparing each element with the neighbor in front of it (n). About 3.5 million steps in total for n = 200,000. Fast enough.

Decomposition. (1) read the data, (2) sort, (3) go through the neighboring pairs while keeping the smallest difference, (4) print.

Note that all the thinking above happens before writing code, and the code itself is only ten lines.

Homework

Checklist before writing code

These five questions are answered on paper, in order. If you get stuck on any one of them, it is not yet time to touch the keyboard:

1. Can I rewrite this problem as "given ... print ..."?
2. What is the output for the sample case in the problem, if I work it out by hand? Does the result match?
3. What is my plan, in one sentence?
4. How many steps does that plan take for the largest n in the constraints, and does it fit within the time limit?
5. What edge cases might break it — n = 1, all values equal, the largest value allowed by the constraints?

Number 2 is the one skipped most often and the one that saves you most often. Working the sample case by hand often reveals that your understanding of the problem is wrong — and that is a kind of mistake that cannot be fixed by editing code.

OSN tips

OSN problems are deliberately wrapped in stories. The character names, setting, and units used almost never affect the answer. The first trained step is to discard the wrapping: rewrite the problem as one sentence "given ..., print ...". If that sentence cannot be written, the problem has not been understood — and writing code before that almost always ends with throwing all the code away.

Work the sample by hand before writing code. The sample in a problem is not just an extra: it is the only place where the problem setter's intent can be checked. If your hand calculation differs from the sample, it is your understanding that is wrong, not the sample.

Constraints determine the shape of the solution, not the speed of the code. The correct order of thinking:

1. Read the constraints.
2. Calculate how many steps are allowed (about 10⁸ per second).
3. Only then choose a method.

A constraint of 10¹⁸ never means "write a fast loop"; it means "do not have a loop that long". The Rotating Candy problem below is the clearest example: simulating handing out the candy one at a time is both the correct answer and an answer that is impossible to run.

Ask: what really needs to be remembered? Many problems that seem to demand storing all the data actually only need one or two running accumulators. "How many times was the record broken" does not need the whole list of times — only the best time so far. This question often turns a problem that looks heavy into a single loop.

Separate three different questions. When reading a problem, answer the three separately:

If you are stuck, do the small version first. Writing a slow answer that is certainly correct for small N gives two things at once: points from the subtasks with small constraints, and a tool for checking the fast answer written later. How to compare the two automatically is covered in Chapter 11.

Summary

• Decomposition: break the problem into steps that can each be tested on their own; a step that is still vague means the breakdown is not finished.
• Pattern recognition: collect "problem wording shape → tool" pairs as you practice. A pattern gives an initial guess; the constraints decide.
• Abstraction: discard the story, rewrite it as "given ... print ...".
• Algorithm: a sequence of steps that is clear, finite, and deterministic.
• Read a problem in this order: input-output format, constraints, sample cases, and only then the story.
• Work the sample cases by hand before writing code.

OSN-style exercises

The following three problems are deliberately written in a roundabout way, like real problems. Before writing code, first rewrite each one as a single sentence "given ..., print ...".

The starter files for all three are in exercises/08/osn/.

Problem 1 — Mango Harvest

Pak Dengklek has a mango orchard and a warehouse that is initially empty. For N consecutive days he picks mangoes: on day i he picks Aᵢ fruits and puts them into the warehouse.

Pak Dengklek is too lazy to go to the market, so he only sells when the warehouse holds a lot. The rule: every evening, if the warehouse contains K fruits or more, all of its contents are taken to the market and sold out that same day, so the warehouse is empty again.

Determine on how many days Pak Dengklek goes to the market and how many mangoes remain in the warehouse after day N.

Input format. The first line contains two integers N and K. The second line contains N integers A₁ A₂ … A_N.

Output format. One line containing two integers: the number of selling days and the mangoes remaining in the warehouse.

Constraints.

• 1 ≤ N ≤ 200,000
• 1 ≤ K ≤ 10⁹
• 0 ≤ Aᵢ ≤ 10⁹

Sample input

5 10
3 4 5 2 9

Sample output

2 0

Explanation. The warehouse contents are 3, 7, then 12 in turn — on the third day the contents reach 10, so they are sold and the warehouse is empty. On the fourth day 2, on the fifth day 11, sold again. Two selling days, and the warehouse ends up empty.

Starter file: exercises/08/osn/01-panen-mangga.cpp

Problem 2 — New Record

A running race has N runners who run one at a time, in the order of their bib numbers. The committee records each runner's time.

A runner is said to break the record if their time is faster than that of every runner who ran before them. The first runner automatically breaks the record, since there is nothing to compare against yet. A runner whose time is exactly equal to the current record is not considered to break the record.

Count how many times the record is broken during the race.

Input format. The first line contains an integer N. The second line contains N integers T₁ T₂ … T_N, the time of each runner in running order.

Output format. One line containing the number of records broken.

Constraints.

• 1 ≤ N ≤ 200,000
• 1 ≤ Tᵢ ≤ 10⁹

Sample input

6
15 12 14 10 10 9

Sample output

4

Explanation. The record is broken by the runners with times 15, 12, 10, and 9. The runner with time 14 does not break the record because 12 is already faster, and the fifth runner with time 10 does not either, because it has to be faster, not equal.

Starter file: exercises/08/osn/02-rekor-baru.cpp

Problem 3 — Rotating Candy

N children sit in a circle and are numbered 1 to N clockwise. A teacher hands out M candies one at a time: the first candy to child 1, the second candy to child 2, and so on. After child N, the handing out returns to child 1, going around and around until the candy runs out.

Determine the number of the child who receives the last candy, and how many candies child 1 receives.

Input format. One line containing two integers N and M.

Output format. One line containing two integers: the number of the child who receives the last candy, then the number of candies received by child 1.

Constraints.

• 1 ≤ N ≤ 10⁹
• 1 ≤ M ≤ 10¹⁸

Sample input

3 7

Sample output

1 3

Explanation. The candies are handed to children 1, 2, 3, 1, 2, 3, 1. The seventh candy goes to child 1, and child 1 receives three candies. Note the constraint on M: the answer must not be found by handing out the candies one at a time.

Starter file: exercises/08/osn/03-permen-berputar.cpp

Stuck or already done? Open the homework solutions page.