OSN Informatika

This book prepares you for OSN in Informatics (OSN: Olimpiade Sains Nasional, Indonesia's National Science Olympiad): an olympiad that tests the ability to solve problems with algorithms, and then to write that solution as a program that is correct and fast enough.

No prior knowledge is assumed. The book starts from installing a compiler and writing a first program, and goes up to the techniques actually used in OSN problems: brute force, greedy, dynamic programming, modular arithmetic, GCD/LCM, and the counting rules and permutations-combinations.

How the book is organized

The book is divided into five parts. Each part ends with one mini-project that uses only what has been taught up to that point.

  • Part 1 — C++ programming basics. Installing a compiler, the first program, variables, branching, loops, functions, arrays and vector. C++ is placed at the very front so that every later part can be run directly on a computer, not merely read.
  • Part 2 — Computational thinking. Decomposition, pattern recognition, abstraction, and algorithms. This includes how to write an algorithm as a flowchart and pseudocode, trace it by hand, and count its number of steps.
  • Part 3 — Problem solving. The three approaches most often used in OSN: brute force, greedy, and dynamic programming — when each one is used and when it fails.
  • Part 4 — Number theory. Modular arithmetic with its properties and theorems, then GCD and LCM with the Euclidean algorithm.
  • Part 5 — Combinatorics. The sum and product rules, permutations, and combinations — including how to compute them with a program.

The shape of each chapter

Every chapter has the same shape:

  • A short explanation of one idea.
  • Code examples that can be opened from the exercises/ folder and run on your own computer.
  • Several Try this boxes in the middle of the chapter. Each contains a one-line change that you should do right away.
  • A Homework section at the end of the chapter, with three to five problems and one optional Challenge.
  • A separate homework solutions page (linked at the end of the homework section) that explains the way of thinking first, and only then shows code.

Boxes inside a chapter

Four kinds of colored boxes are used repeatedly. Learn what they mean now so you know which ones may be skimmed and which may not:

Box Contents
Note extra explanation, background, or contest habits
Watch out mistakes that genuinely happen often and cost points
Try this a one- or two-line change done directly on the computer
Homework the list of problems at the end of the chapter

The Watch out box is the most expensive one to skip. Its contents are not theory, but a list of ways to lose points that have been proven in practice.

How to read the code examples

Three kinds of blocks are used throughout the book, and they mean different things:

A C++ code block — this is what you type into a .cpp file:

cout << 1 + 2 << "\n";

An indented block without color — this is program output or a command typed in the terminal, not C++ code:

3

A pseudocode block — this is not any programming language, but an algorithm written as short sentences (Chapter 09 covers its rules):

READ n
PRINT n * 2

Some code snippets in this book deliberately show only the part being discussed, without #include and int main(). Such snippets cannot be compiled as-is — the full version is in the file named in the nearby Try this box.

What you need

  • A computer with Windows 10 or 11.
  • A C++ compiler (MinGW-w64 or Visual Studio, installed in Chapter 01) and a code editor.
  • Paper and pencil. Parts 2 through 5 are largely worked on paper first, exactly as when solving OSN problems.
  • An account on an online judge site to practice submitting answers. Chapter 01 explains the options.

How to use this book

Work through each chapter with the following five-step loop, in order:

  1. Read the chapter once to the end, without a computer. The goal is to recognize which ideas it contains, not to memorize.
  2. Run every example named in a Try this box. Reading code and running code produce completely different understanding.
  3. Break the example on purpose. Change one number, delete one line, flip one comparison sign, then guess what will happen before running it again. A wrong guess is where your understanding leaks, and that is the most useful thing to fix.
  4. Do the homework yourself until it works, without opening the solutions page.
  5. Only then open the solutions page, and compare it with your answer — including when your answer is already correct, because the walkthrough often contains a shorter method or an edge case you missed.

Skipping steps 2 through 4 and going straight to the solutions is the fastest way to feel you understand when you cannot yet do it.

If one homework problem has been stuck for more than about half an hour with no progress at all, stop staring at the screen: trace the code on paper with a very small input (Chapter 10 teaches how). Most of the time the blockage disappears in the tracing table, not on the screen.

Two habits need to be built from Part 1 onward, because both decide your score in the contest:

  • Always run your code with edge cases, not just the examples given in the problem. Points lost in OSN are far more often caused by one missed edge case than by a wrong algorithm.
  • Count the number of steps first, then write the code. Chapter 10 gives a table that turns a problem's constraints into a choice of algorithm. From Part 3 onward, this habit is what separates full-score answers from answers that run out of time.

The next chapter, Setup, installs the compiler and editor so the code in this book can be run.