09. Flowcharts and pseudocode

An algorithm needs to be written down before it becomes code. There are two ways to write it: a flowchart (a picture) and pseudocode (text). Both appear in district-level OSN problems, and both force you to think about the order of steps without being bothered by semicolons.

Writing the algorithm first feels like extra work, but it saves time. The reason: fixing a wrong step on paper takes one stroke of the pen, while fixing it after it has become sixty lines of C++ means rereading the whole program while guessing where the error is. In a contest, participants who start typing immediately usually lose to participants who spend the first five minutes on paper.

Flowchart symbols

Four rules that make a flowchart readable by other people — and three of them are the most common mistakes on answer sheets:

1. A diamond always has exactly two outgoing arrows, labeled yes and no. An unlabeled branch forces the reader to guess.
2. One Start oval and one End oval. Every path eventually leads to the same End oval.
3. Every box has exactly one outgoing arrow. If a box needs two possibilities, it must be replaced by a diamond.
4. No dangling arrows. An arrow that leads nowhere means there is a step that has not been thought through.

Three basic patterns

Every algorithm, however long, is built from these three patterns.

Sequence

Branching

Loop

The arrow from i = i + 1 back to the diamond is the loop. Without the back arrow, nothing repeats.

Note the fixed layout of a loop in a flowchart, because this shape is always the same for any loop:

Branching inside a loop

The combination of the two patterns is the shape that appears most often in problems: go through all the data, and make a decision at each element. Here is the algorithm for finding the largest value (besar, "largest").

There are two diamonds with different jobs: the upper one controls how many times the loop runs, the lower one controls what is done with one element. Note also that both branches of the lower diamond meet again at the box i = i + 1 — that step must run whatever the decision is, otherwise the loop never stops.

Pseudocode

Pseudocode is an algorithm written as short sentences, one step per line, with indentation to show what is inside what. There is no fixed standard, but this is the form used in this book (jumlah means "sum"):

READ n
jumlah <- 0
FOR i FROM 1 TO n
    jumlah <- jumlah + i
PRINT jumlah

The keywords you need to know:

Two rules of form: one step per line, and indentation shows the body. An indented line is inside the loop or branch directly above it. Since there are no curly braces, indentation is the only marker — so writing it neatly is not a matter of looks.

Compare two pieces of pseudocode that differ only in indentation:

jumlah <- 0
FOR i FROM 1 TO n
    jumlah <- jumlah + i
    PRINT jumlah

jumlah <- 0
FOR i FROM 1 TO n
    jumlah <- jumlah + i
PRINT jumlah

The first prints n lines, the second prints one line. District-level OSN problems do like to test differences this subtle.

A longer example — finding the largest value:

READ n
READ a[1..n]
besar <- a[1]
FOR i FROM 2 TO n
    IF a[i] > besar
        besar <- a[i]
PRINT besar

From pseudocode to C++

The translation is almost line by line:

Watch the index shift: pseudocode in this book writes arrays starting at 1 (like OSN problems), while C++ starts at 0. This is one of the most common sources of mistakes when translating.

There are two ways to handle it, and both are valid as long as you use one consistently:

• Shift everything: a[1] in the pseudocode becomes a[0] in the code, and FOR i FROM 1 TO n becomes for (int i = 0; i < n; i++).
• Leave index 0 empty: read the data into a[1] through a[n], and write for (int i = 1; i <= n; i++). The array only has to be one slot larger.

The second way is often chosen in contests precisely because it removes the shift: the code and the problem use the same numbering, so formulas like "element i and element i+1" can be copied as they are.

Reading someone else's pseudocode

The exercises used at district-level OSN go the other way around: the pseudocode is given, and the output is asked for. Try this fragment before reading on:

n <- 5
hasil <- 1
WHILE n > 1
    hasil <- hasil * n
    n <- n - 1
PRINT hasil

Trace it by hand: hasil ("result") becomes 5, then 20, then 60, then 120 in turn, and n stops at 1. The output is 120, which is 5!. Chapter 10 teaches how to build a tracing table like this systematically so no step is skipped.

When to use which

• Flowcharts for short algorithms with complicated branching. The picture shows branches that were missed.
• Pseudocode for algorithms with nested loops or many steps. Drawing three nested loops produces an unreadable picture; writing them takes six lines.

On district-level OSN answer sheets, problems often present pseudocode and then ask "what is the output?". The ability to read someone else's pseudocode is as important as writing it — and that is the exercise of Chapter 10.

Homework

Most common mistakes

OSN tips

"Predict the output" problems are free points if you trace them with a table. Do not read them in your head. Make a table on scratch paper: one column per variable, one row per iteration. This takes half a minute and is almost never wrong, while guessing from reading is almost always wrong on the last iteration.

Check the two places that trap people most often: the value of a variable after the loop ends, and whether PRINT is inside or outside the loop. A difference of one indentation level changes the answer from one line to n lines.

Watch the loop bounds. FOR i FROM 1 TO n includes n, while for (int i = 1; i < n; i++) does not. This off-by-one error is the most common cause of Wrong Answer on translation problems.

Pseudocode in problems uses indices starting at 1. OSN problems almost always number data from 1, while C++ arrays start at 0. Decide how to handle it once at the start — shift everything, or leave index 0 empty — then use only that one way until the end. Mixing both in one program is a source of mistakes that are very hard to find.

A design on paper is not a waste of time. Five minutes writing pseudocode saves half an hour chasing logic errors, because a design mistake shows up as an awkward sentence, not as a wrong number on test case 37. What needs to be drawn is not the whole program, only the part that is still unclear.

A flowchart is useful for checking the flow, not for writing code. In a contest, drawing a complete flowchart is not worth the time. What is used is the condensed form: three to five boxes to make sure every branch has a way out and every loop has a stopping condition.

Summary

• A flowchart uses ovals for start/end, rectangles for actions, diamonds for decisions, and arrows for order.
• A diamond has exactly two outgoing arrows labeled yes and no; a loop is marked by a back arrow to its diamond.
• Pseudocode writes one step per line and uses indentation to show the body of a loop or branch.
• The keywords used in this book: READ, PRINT, <-, IF, ELSE, FOR ... FROM ... TO ..., WHILE.
• Flowcharts suit complicated branching; pseudocode suits nested loops and long algorithms.
• The translation to C++ is almost line by line; what needs watching is the array index shift from 1 to 0.

OSN-style exercises

Do the first two problems on paper first, like the analytical problems that appear in the early selection stages: what is tested is not typing speed but care in tracing. Only the third problem is done on the computer, but write its pseudocode first.

The skeletons are in exercises/09/osn/.

Problem 1 — Trace the Pseudocode

Consider the following pseudocode:

READ n
a <- 0
b <- 1
FOR i FROM 1 TO n
    IF i divisible by 3
        a <- a + i
    ELSE
        b <- b * 2
PRINT a
PRINT b

Answer without running the program:

a. What is printed for n = 10? b. What is printed for n = 1? c. In your own words, what do the values of a and b mean in general? d. From which n does the value of b exceed the int limit?

How to work it out. Make a table with columns i, a, and b, then fill one row per iteration. For part (c), look at how many times each branch is entered, not at the values one by one.

After answering on paper, check with exercises/09/osn/solutions/01-telusuri.cpp.

Problem 2 — Read the Flowchart

The following flowchart reads one integer N and prints one number.

a. What is printed for N = 100? b. What is printed for N = 1? c. In one sentence, what does this flowchart compute? d. Write it in C++, then run it for N = 10¹⁸.

Input format. One line containing the integer N.

Output format. One line containing one integer.

Constraints. 1 ≤ N ≤ 10¹⁸.

Skeleton: exercises/09/osn/02-pangkat-dua.cpp

Problem 3 — Mountain Sequence

A sequence is called a mountain sequence if it strictly increases up to one peak, then strictly decreases to the end. Strictly increasing means each number is greater than the previous one; strictly decreasing means each number is smaller than the previous one. The peak must not be at either end: there must be an increasing part and a decreasing part.

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

Output format. One line containing YA if the sequence is a mountain sequence, or TIDAK if it is not.

Constraints.

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

Sample input

5
1 3 7 4 2

Sample output

YA

Explanation. The sequence rises from 1 to 3 to 7, then falls to 4 and 2. The sequence 1 2 3 4 is not a mountain sequence because it never falls, and the sequence 3 3 4 2 1 is not one because its first two numbers are equal — the rise is not strict.

Write the pseudocode on paper first. Hint: you only need two loops that run one after the other on the same pointer, not two nested loops.

Skeleton: exercises/09/osn/03-deret-gunung.cpp

Stuck or already done? Open the homework solutions page.