Competitive programming • National competition • SIO

Preparation for the National Informatics Competition and SIO

A complete preparation plan for students in grade 8 and the first year of secondary school. The focus is on developing algorithmic thinking, dynamic programming, graphs, combinatorics and advanced competition techniques.

🧠 Dynamic programming
🕸️ Graph algorithms
⚡ SIO level
🏆 Competition tasks

An 11-week preparation plan

The plan is meant for students who already have basic experience with recursion, combinatorics and basic algorithms, and want to move on to the national competition and SIO (the Serbian Informatics Olympiad) level.

The focus is not only on learning algorithms, but also on developing the way of thinking needed to solve complex competition problems.

Some lessons linked below are available only in Serbian for now. They are marked (SR).

Basic level
Recursion and combinatorics
Permutations, combinations, memoization and the first steps towards DP.
Intermediate level
Dynamic programming and graphs
Classic DP problems, BFS, DFS, Dijkstra and modelling states.
Advanced level
SIO and olympiad tasks
Interactive problems, optimizations and advanced data structures.
Recommended prior knowledge:
  • recursion and backtracking
  • combinatorics
  • sorting and binary search
  • basic data structures
How to use this plan?
  • ✔ First read the whole roadmap.
  • ✔ Focus only on the current week.
  • ✔ Practise every day, at least 1–2 tasks.
  • ✔ Analyse the complexity of every solution.

Week 1 — Recursion and algorithmic thinking

The first week is devoted to developing the way of thinking that is necessary for competitive programming. The focus is not only on writing code, but on how a problem is broken down into smaller subproblems.

Recursion is the foundation for later topics such as backtracking, dynamic programming, DFS and advanced state searches.

Main goal: to learn how to look at a problem through smaller subproblems and how to follow the flow of execution of recursive calls.

Topics to master

  • Basic recursion and returning from a function
  • Recursively computing a sum, a power and a factorial
  • Recursively traversing arrays and strings
  • Following the tree of recursive calls
  • The difference between the iterative and the recursive approach
  • The time complexity of simple recursion
  • Memoization as an introduction to dynamic programming
  • The Towers of Hanoi and analysing the recursion tree
Beginner level
Recursion — introduction and basic examples
The basics of recursion, the base case and simple examples.
Open lesson → (SR)
Beginner level
Recursive algorithms
Detailed explanations of the recursive model.
Open lesson →
Intermediate level
Fibonacci and factorial with recursion
Classic examples of recursion and analysing the number of calls.
Open lesson → (SR)
Note: Recursion must always lead to a smaller problem and have a correct base case.

Suggested practice tasks

Week 2 — Backtracking and generating combinations

After the basics of recursion we move on to backtracking — systematically searching the solution space while returning to the previous state.

Main idea: choose → go deeper → go back → next option

Backtracking can be seen as recursion + checking conditions. Unlike plain brute force, with the backtracking approach we do not needlessly examine all possible solutions, but early on we discard branches that certainly cannot lead to a valid result.

Topics to master

  • Permutations and combinations
  • Subsets
  • The backtracking tree
  • Pruning (cutting off branches)
  • DFS in the solution space
  • The difference between the brute-force and the backtracking approach
  • Generating solutions with constraints
Beginner level
Backtracking algorithms
The basic principle of searching the solution space.
Open lesson → (SR)
Beginner level
Permutations and combinations
Generating all combinatorial structures.
Open lesson → (SR)
Intermediate level
Combinatorics for competitions
Connecting recursion and combinatorics.
Open lesson → (SR)
Intermediate level
Backtracking and brute force
Comparing the brute-force and the backtracking approach with practical examples.
Open lesson → (SR)
Important: Backtracking has exponential complexity, so proper cutting off of branches (pruning) is often crucial for a task to pass within the time limit.

Suggested practice tasks

A universal scheme for backtracking

For every task try to identify:
  • State — what do you know at the moment?
  • Choice — which options can you try?
  • Validity — is the partial solution allowed?
  • Stop — when is the solution complete?
These four steps are the basis of almost all backtracking problems at school, district and national competitions.

Week 3 — Sorting, binary search and complexity

The focus of this week is on algorithms that appear very often at school, district and national competitions. A good knowledge of sorting, binary search and time complexity often makes it possible to solve a task many times faster than with a naive approach.

Goal: to understand when to use O(n log n) algorithms and how to optimize a search by using sorting and binary search.

Topics to master

  • Merge Sort
  • Quick Sort
  • STL sort and comparator functions
  • Binary search
  • Lower Bound and Upper Bound
  • Sorting by several criteria
  • Analysing time complexity
  • Binary Search on Answer
Beginner level
Merge Sort
The divide-and-conquer approach and sorting in O(n log n).
Open lesson →
Intermediate level
Binary search
Finding a solution in logarithmic time.
Open lesson →
Intermediate level
Sorting arrays
Analysing and comparing the most important sorting algorithms.
Open lesson →
Intermediate level
Efficient sorting algorithms
Comparing complexity and applying them in competition tasks.
Open lesson →
Note: Binary search is not limited to searching in an array. It is very often used for finding the smallest or the largest solution that satisfies a certain condition (binary search on answer).

Suggested practice tasks

Intermediate level
Efficient search algorithms
Linear search, binary search and advanced search techniques.
Open lesson →
Competition tip:
When you notice that a task asks for the smallest or the largest value that satisfies a certain condition, check whether the answer can be found with binary search. Such tasks appear very often at district, national and international competitions.

Week 4 — Introduction to dynamic programming (DP)

This week we introduce the key ideas of dynamic programming (DP) — a technique that makes it possible to solve problems that plain recursion would solve too slowly, by remembering the results of subproblems that have already been processed.

Main goal: to learn how to recognize problems with repeated subproblems and how to transform them from slow recursive solutions into efficient DP algorithms.

Topics to master

  • Overlapping Subproblems
  • Optimal Substructure
  • Defining the DP state
  • DP transitions
  • Memoization (Top-Down DP)
  • Tabulation (Bottom-Up DP)
  • Optimizing memory
  • Fibonacci as an introductory DP example
A DP thinking template:
  • 1️⃣ Define the state — dp[...]
  • 2️⃣ Determine the base cases
  • 3️⃣ Write the transitions between states
  • 4️⃣ Choose the order of computation (top-down or bottom-up)

Main concepts

  • Overlapping subproblems — the same subproblems appear several times during the recursion.
  • Optimal substructure — the optimal solution of a problem can be built from the optimal solutions of smaller subproblems.
  • State & Transition — the most important step is defining the meaning of the DP state and the transitions correctly.
Important:

The biggest problem for beginners is not the implementation, but defining the meaning of the DP array correctly. If you do not know what dp[i] represents, you will almost certainly not write a correct solution.

Fibonacci as an introductory example

Fibonacci is an ideal example for comparing recursion, memoization and tabulation. It shows very clearly why dynamic programming brings an enormous speed-up.

Recursion
An exponential solution
The same subproblems are computed several times, so the running time grows quickly.
Memoization
Top-Down DP
The results are remembered during the recursive calls and every subproblem is solved only once.
Tabulation
Bottom-Up DP
The table is filled iteratively from the base states towards the final solution.
Memoization vs. Tabulation
  • Memoization (Top-Down) uses recursion and stores the results of states that have already been processed.
  • Tabulation (Bottom-Up) starts from the base cases and fills the DP table iteratively.
  • Both approaches often have the same asymptotic complexity, but tabulation allows better control of memory.

Suggested lessons

Beginner level
Introduction to dynamic programming
Basic concepts, states and transitions.
Open lesson →
Intermediate level
0/1 Knapsack
The best-known dynamic programming problem.
Open lesson →
Intermediate level
Longest Common Subsequence
A classic DP problem on strings.
Open lesson →
Important: If you notice that the same recursive function is called several times with the same parameters, it is very likely that the problem can be solved with dynamic programming.

Suggested practice tasks

Note:

The AtCoder Educational DP Contest (A–Z) is one of the best sets of tasks for learning dynamic programming systematically. The tasks are arranged so that new DP ideas are introduced gradually.

Work plan (suggestion)

  1. Analyse the Fibonacci recursion and find the repeated subproblems.
  2. Measure the number of function calls for n=30 and n=40.
  3. Implement memoization and compare the number of calls.
  4. Move on to bottom-up tabulation.
  5. Optimize the memory from O(n) to O(1).
  6. Solve Frog 1 using the same principle.
  7. Start the first Knapsack and Coin Change tasks.
  8. Compare the performance of recursion, memoization and tabulation.

Study notes

  • DP often arises as an optimization of slow recursion.
  • Always write the meaning of the DP state on paper first.
  • Base cases are just as important as transitions.
  • Try to explain the transitions without looking at the code.
  • Do not memorize formulas — understand the meaning of every state.

Resources and references

Week 5 — Dynamic programming with several dimensions (2D / 3D DP)

After mastering the basic one-dimensional DP problems, we move on to tasks in which the state depends on two or more parameters. Such problems appear very often at district, national and SIO competitions.

Main goal: to learn how to define states of the form dp[i][j] and dp[i][j][k], and how to correctly determine the order of filling the DP table.

Topics to master

  • 2D DP states — dp[i][j]
  • 3D DP states — dp[i][j][k]
  • DP on matrices
  • DP on strings
  • Longest Common Subsequence (LCS)
  • Edit Distance
  • 0/1 Knapsack as 2D DP
  • Optimizing memory (2D → 1D)
  • The order of filling the DP table
Rule:

If a problem depends on two independent parameters (e.g. a position in a matrix, two strings, or an index and a capacity), you very often need to use 2D dynamic programming.

How to recognize 2D DP?

  • There are at least two parameters that determine the state of the problem.
  • The solution depends on a combination of several previous states.
  • A table dp[i][j] forms naturally.
  • Matrices, strings or two independent indices often appear.
  • Several pieces of information have to be tracked at the same time.

Classic 2D DP problems

Beginner level
The maximum sum through a matrix
A classic example of DP on a grid and a matrix.
Open lesson →
Intermediate level
Longest Common Subsequence
The best-known DP problem on strings.
Open lesson →
Intermediate level
0/1 Knapsack
A multidimensional state and optimizing memory.
Open lesson →

DP on matrices

For problems with grids and matrices the state used most often is:


dp[i][j]

which represents the best value up to the cell (i,j).

Typical transitions:
  • from the cell above
  • from the cell on the left
  • from the diagonal cell
  • a combination of several previous states

DP on strings

  • Longest Common Subsequence (LCS) — finding the longest common subsequence of two strings.
  • Edit Distance — the minimum number of operations needed to transform one string into another.
  • Longest Common Substring — the longest common contiguous substring.
Important: In most 2D DP problems the most common mistakes are not in the formulas, but in wrongly defined base cases and the order of filling the table.

Suggested practice tasks

Work plan (suggestion)

  1. Start with simple DP problems on matrices.
  2. Draw the DP table by hand for small input examples.
  3. Analyse how the transitions between states are formed.
  4. Move on to LCS and problems on strings.
  5. Implement Edit Distance.
  6. Try to optimize the memory to two rows.
  7. Compare the memory complexity of the 2D and the optimized 1D solution.

Common mistakes

  • An unclear meaning of the DP state.
  • The wrong order of filling.
  • Forgotten base cases.
  • Too much memory.
  • Not recognizing the dimensions that actually define the state.
  • Using the whole DP table when it can be optimized to a 1D array.
Competition tip:

For every DP task first define what one state represents. Only when you clearly know the meaning of the state, write the transitions and the code. That is the most important habit to develop for serious DP problems.

Resources and references

Week 6 — More advanced dynamic programming (Knapsack and optimizations)

This week focuses on more advanced forms of dynamic programming, with a special emphasis on Knapsack problems, their different variations and optimizing memory and running time.

Main goal: to learn how 2D DP models are optimized into 1D, how the 0/1 and the unbounded variants differ and how DP is applied to real optimization problems.

Topics to master

  • The 0/1 Knapsack problem
  • Unbounded Knapsack
  • Bounded Knapsack (the basic idea)
  • DP by weight and by value
  • Optimizing memory (2D → 1D DP)
  • The order of the loops and its effect on the result
  • DP over subsequences and combinatorial choices
2D DP model
The Knapsack table
The classic state dp[i][w] as the basis of the knapsack problem.
Open lesson →
Optimization
2D → 1D DP
Reducing memory by running the iteration correctly.
Problem variants
0/1, unbounded and bounded Knapsack
Different models of choosing elements.

The key concept — 0/1 Knapsack

The goal is to maximize the value of the items without exceeding the capacity of the knapsack. Every item can be taken at most once.

DP state:

dp[i][w]

The maximum value using the first i items with capacity w.

Optimizing memory (the key idea)

Since every state depends only on the previous row, 2D DP can be reduced to a 1D array.


for (int i = 0; i < n; i++) {
    for (int w = W; w >= weight[i]; w--) {
        dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
    }
}
An important rule:

If the iteration runs backwards (W → 0), we get 0/1 Knapsack. If it runs forwards, we get unbounded Knapsack.

0/1 vs Unbounded Knapsack

  • 0/1 Knapsack: every item is used at most once.
  • Unbounded Knapsack: every item can be used several times.
  • The difference is in the direction of the iteration over the capacity.

DP variations you should know

  • Knapsack by weight
  • Knapsack by value
  • The minimum cost for a given value
  • The number of ways to reach a sum

Common mistakes

  • The wrong direction of the loop (the most common mistake)
  • Mixing the 0/1 and the unbounded logic
  • Using the same DP value several times in the same iteration
  • A wrongly defined DP state
  • Too much memory without need

Suggested tasks

Work plan (suggestion)

  1. Implement the classic 2D Knapsack.
  2. Understand the meaning of dp[i][w].
  3. Convert the 2D DP into a 1D DP.
  4. Experiment with the direction of the loops (0/1 vs unbounded).
  5. Solve Coin Change (the number of ways + the minimum number of coins).
  6. Connect Knapsack with the previous DP problems.

Study notes

  • DP is modelling choices, not only implementation.
  • The direction of the loop directly changes the mathematical model of the problem.
  • Always clarify first: can the elements be repeated?
  • Optimizing memory does not change the logic of the problem.

Resources

Week 7 — Graphs: representation, BFS and DFS


This week is the entry into graphs, one of the most important areas of algorithmic programming. Graphs appear in a huge number of competition tasks — from simple searches to complex problems with constraints.

The focus is on understanding how to represent a graph, how to perform a graph search and how to recognize that a problem is actually a graph problem.


Basic concepts
Representing graphs
The adjacency list, the adjacency matrix, directed and undirected graphs.
Graph search
DFS and BFS
Traversing a graph, connected components and the shortest path in an unweighted graph.
Modelling problems
Graphs in a matrix
Mazes, islands, grids and problems with states and transitions.

Basic concepts

  • Vertex (node), edge
  • Directed and undirected graphs
  • Weighted and unweighted graphs
  • Connected components
  • A graph as an abstract model of a problem

Representing a graph

  • The adjacency list — the most common and the most efficient (O(V + E))
  • The adjacency matrix — simple, but expensive in memory (O(V²))

// Adjacency list (undirected graph)
vector<vector<int>> adj(n);

adj[u].push_back(v);
adj[v].push_back(u);

Note: The adjacency list is the standard at competitions and is used in almost all BFS/DFS tasks.


DFS — Depth-First Search

DFS goes as deep into the graph as possible before going back. It is most often implemented recursively and is used for:

  • Finding connected components
  • Detecting cycles
  • Traversing a graph and a matrix
  • Topological sorting (later)

vector<bool> visited;

void dfs(int u) {
    visited[u] = true;

    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

BFS — Breadth-First Search

BFS traverses the graph level by level and uses a queue. The key property: in unweighted graphs BFS gives the shortest path.

  • The shortest path in an unweighted graph
  • Problems with the minimum number of steps
  • A state graph

vector<int> dist(n, -1);
queue<int> q;

dist[start] = 0;
q.push(start);

while (!q.empty()) {

    int u = q.front();
    q.pop();

    for (int v : adj[u]) {

        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

Important: If all edges have the same weight — BFS is optimal for the shortest path.


A graph in a matrix (grid)

Many tasks are not given explicitly as a graph, but as a matrix or a maze. Every cell is a vertex, and the moves are edges.

  • The number of islands
  • The shortest path in a maze
  • Spreading (fire, flood, infection)

Suggested practice tasks


Work plan (suggestion)
  1. Learn the basic concepts and how to represent a graph.
  2. Implement DFS and BFS from scratch.
  3. Practise graphs in a matrix (4/8 directions).
  4. Tell when to use BFS and when DFS.
  5. Solve at least 5 graph tasks.

Study notes
  • If a problem can be described as "states + transitions" — it is probably a graph.
  • BFS = the minimum number of steps.
  • DFS = structure, components, cycles.
  • Graphs are the basis for Dijkstra, DSU and topological sorting.

Resources

Week 8 — Graphs (shortest paths) + Priority Queue

This week the focus is on shortest path problems in a graph, which are very common at national competitions and SIO. Students learn how to correctly model a real problem as a graph and how to choose the right algorithm depending on the type of edge weights.

Special emphasis is on Dijkstra's algorithm, and on the correct use of the priority_queue from the C++ STL, which is a common source of mistakes for students.

Basic level
BFS for the shortest path
The shortest path in unweighted graphs and working with the queue structure.
Intermediate level
Dijkstra's algorithm
The shortest path in weighted graphs with non-negative weights.
Advanced level
Priority Queue
Min-heap, stale entries and optimizing performance.

Main topics

  • Modelling a problem as a graph (vertices, edges, weights)
  • The difference between unweighted and weighted graphs
  • BFS as an algorithm for the shortest path in an unweighted graph
  • Dijkstra's algorithm (SR) — the idea, invariants, complexity and implementation
  • Using priority_queue in C++
  • Working with the min-heap structure
  • Typical beginner mistakes: entering the queue several times, wrong use of the visited array, wrong comparison of pairs
Main idea: if all edges have the same weight, the shortest path is found with BFS. If the weights are different, you move on to Dijkstra's algorithm.

Dijkstra — the basic idea

In every step the algorithm chooses the vertex with the currently smallest known distance and tries to improve the distances of its neighbours. When a vertex is taken out of the priority queue with a valid distance, that distance becomes final.

Unlike BFS, a classic visited array is usually not used here. Instead, we check whether the distance taken out is stale.

An example implementation (C++)


#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
vector<vector<pair<int,int>>> graph;
vector<long long> dist;

void dijkstra(int start) {
    priority_queue<
        pair<long long,int>,
        vector<pair<long long,int>>,
        greater<pair<long long,int>>
    > pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue; // stale entry

        for (auto [v, w] : graph[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}
  
Important: Dijkstra does not work with negative weights. For larger inputs use long long, and always check whether the graph is directed or undirected.

Typical tasks

  • The shortest path between two cities
  • The fastest or the cheapest path
  • Graphs with weights
  • Mazes with move costs
  • Multiple queries from a single source
  • Modelling problems where a state is a vertex of the graph

Suggested practice tasks

Work plan (suggestion)
  1. Solve the shortest path with BFS in an unweighted graph.
  2. Understand why BFS does not work for different weights.
  3. Implement Dijkstra's algorithm.
  4. Simulate the algorithm by hand on a small graph.
  5. Solve several tasks from the CSES / SPOJ platforms.
Study notes
  • Dijkstra does not work with negative weights.
  • Complexity: O((V + E) log V).
  • Use long long for large distances.
  • Always check whether the graph is directed or undirected.
  • If you see "shortest path" in an unweighted graph, think of BFS first.

Week 9 — Number theory (advanced / olympiad level)

This week is an extension of the basic plan and is meant for students preparing for national competitions, SIO and olympiads. Number theory is one of the most common areas at the higher levels of competition and requires a combination of mathematical thinking and efficient implementation.

The emphasis is on understanding the properties of numbers, modular arithmetic and applying well-known algorithms such as Euclid's algorithm and fast modular exponentiation.

Basic concepts
GCD and LCM
Euclid's algorithm, divisibility and the basic properties of numbers.
Open lesson →
Competition level
Modular arithmetic
Addition, multiplication, properties of modulo and working with large numbers.
Open lesson → (SR)
Olympiad level
Prime numbers
Primality testing, factorization and advanced number theory techniques.
Open lesson → (SR)

Main topics

  • Euclid's algorithm — GCD and the extended Euclidean algorithm
  • Modular arithmetic (addition, multiplication, properties of modulo)
  • Fast exponentiation (a^b mod m)
  • Prime numbers and primality testing
  • Factorizing a number into prime factors
  • The least common multiple (LCM) and its connection with the GCD
Main goal: to learn to recognize when a task is actually a number theory task, even when it is "disguised" as combinatorics, graphs or DP.

Important concepts for competitions

  • Why direct computation is often not possible (large numbers)
  • Working with the modulus 10⁹+7 and similar constants
  • Recognizing when a number theory task is "hidden"
  • Combining number theory with DP or graphs
  • The role of divisibility in building and analysing a solution

Example: Fast modular exponentiation (C++)


long long modexp(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
  

This technique is used in a large number of tasks — from number theory to combinatorics and cryptography.

Typical tasks

  • Computing the GCD and the LCM for a large number of queries
  • Checking divisibility and properties of numbers
  • Working with large powers and a modulus
  • Tasks with prime numbers and factors
  • A combination of mathematics and implementation

Suggested practice tasks

Work plan (suggestion)

  1. Revise the basic properties of divisibility and GCD/LCM.
  2. Learn and implement Euclid's algorithm.
  3. Practise modular arithmetic.
  4. Implement fast exponentiation.
  5. Solve several combined tasks.

Study notes

  • Number theory requires more thinking than code.
  • Practise recognizing patterns in tasks.
  • Always check the input limits (constraints).
  • This area is common at olympiads and in final rounds.
Tip: When you see a large number, a modulus or divisibility, first check whether there is a shorter mathematical path before implementing.

Resources

Week 10 — Advanced data structures

This week covers advanced data structures that often appear at national competitions, SIO and olympiads, but require a solid foundation in previous areas such as DP, graphs and priority queues.

The goal is not only to learn the implementation, but to understand when a particular structure is optimal, how it affects the complexity and how it is combined with other algorithmic techniques.

Focus of the week:
  • efficiently processing a large number of queries
  • working with logarithmic structures
  • combining data structures with graphs and DP
  • optimizing time complexity
Basic level
Set and Map
Searching, inserting and removing elements in O(log n).
Intermediate level
Fenwick Tree
Prefix sums and updates in logarithmic time.
Advanced level
Segment tree
Advanced interval queries and a big optimization.
Intermediate level
Priority Queue
The heap structure and its use in tasks with priorities.

Main topics

  • Set / Map — balanced trees and hash structures
  • unordered_set / unordered_map — O(1) access on average
  • Priority Queue (Heap) — the minimum / maximum elements
  • Fenwick Tree (BIT) — prefix sums in O(log n)
  • Segment Tree — working with intervals
An important idea:

Advanced data structures are used when a plain array, sorting or a linear search are no longer efficient enough.

Set and Map — the basic idea

The set and map structures in the C++ STL are based on balanced trees and allow:

  • inserting in O(log n)
  • removing in O(log n)
  • searching in O(log n)

set<int> s;

s.insert(5);
s.insert(2);

if (s.count(5)) {
    cout << "Exists";
}
  
Note:

unordered_set and unordered_map are often faster, but their elements are not sorted.

Fenwick Tree — the basic idea

A Fenwick Tree (BIT) allows:

  • computing prefix sums
  • updating elements
  • all in O(log n)

It is used when there is a large number of:

  • queries over segments
  • element updates
  • online data processing
Typical problems:
  • the number of elements smaller than x
  • prefix sums
  • inversions in an array
  • dynamic queries

Segment tree — introduction

A Segment Tree is a powerful structure for processing intervals.

It allows:

  • the minimum / maximum on a segment
  • sums on segments
  • range update operations
  • advanced lazy propagation techniques
Status:

Detailed pages and implementations for the Fenwick and Segment Tree will be added gradually in the next versions of the guide.

Why are these topics important?

  • They make it possible to solve problems with a large number of queries.
  • They are often the difference between partial and full points.
  • They are combined with DP, graphs and number theory.
  • They appear at the higher levels of competition.

Suggested tasks and resources

Work plan (suggestion)

  1. Revise the STL structures (set, map, priority_queue).
  2. Understand the difference between O(n), O(log n) and O(1).
  3. Learn the basic idea of the Fenwick tree.
  4. Go through the introduction to the segment tree.
  5. Practise tasks with a large number of queries.
Competition tip:

In many tasks the key is not a complicated algorithm, but choosing the right data structure.

Recommendation for students:
  • Do not skip the previous weeks — this material builds on them.
  • For now it is enough to understand when these structures are used.
  • The detailed implementation comes in the next versions of the guide.

Week 11 — Geometry and mixed tasks

The final week is the transition from individual areas to solving complex competition problems that combine several techniques.

The focus is on computational geometry, modelling problems and developing a competition way of thinking. Such tasks are common at national competitions and SIO because they test the understanding of modelling a problem, and not only the knowledge of one technique.

Geometry
Basic formulas and orientation
Areas, segment intersections, distances and working with points.
Combined tasks
Graph + DP + mathematics
Problems that require several algorithmic techniques.
Competition modelling
SIO-level thinking
Recognizing patterns and optimizing solutions.

Geometry topics

  • The shoelace formula — the area of a polygon
  • The orientation of points — turning left/right
  • Segment intersection — collinearity and special cases
  • The distance of a point from a line
  • The convex hull — the basic idea
Why is geometry hard?

Geometry tasks often require precise modelling and careful thinking, while the implementation itself is usually shorter than for DP or graphs. That is why the key is in interpreting the conditions correctly and handling special cases carefully.

The shoelace formula

It is used to compute the area of a simple polygon whose vertices are known. The formula uses the coordinates of neighbouring vertices and is very common at competitions.

Important:

The vertices should be listed in the order in which the edge of the polygon is traversed (clockwise or counterclockwise). The direction of traversal affects only the sign of the result, so the absolute value is taken.

Segment intersection

One of the best-known geometry problems is to determine whether two segments intersect. The key ideas for this are the orientation of points, collinearity and handling special cases.

  • the orientation of points
  • collinearity
  • special cases
  • touching at the endpoints

Mixed tasks

At the higher levels of competition tasks rarely belong to just one area. Different techniques are very often combined, and this is exactly where the ability to model a problem comes to the fore.

The most common combinations are:

  • graphs + DP
  • combinatorics + mathematics
  • geometry + search
  • data structures + graphs
  • DP over geometric objects (intervals, segments, points)
The key skill:

The most important thing is to learn to recognize which area and technique fit the problem. In mixed tasks the winner is usually not the longest code, but the clearest model.

Typical problems

  • the shortest path with additional constraints
  • counting paths in graphs
  • optimization over segments
  • combined mathematical problems
  • modelling states

Recommended resources

Work plan (suggestion)

  1. Revise all the previous areas.
  2. Solve combined tasks.
  3. Practise modelling problems.
  4. Do competition simulations.
  5. Analyse your own solutions and mistakes.
Final recommendation:

Competitive programming is not only learning algorithms, but developing a way of thinking.

The biggest progress comes through:

  • solving tasks continuously
  • analysing other people's solutions
  • persistence and practice
Note:

You do not need to learn everything by heart. It is much more important to understand:

  • how to think about a problem
  • how to model a state
  • how to analyse complexity
  • when to use a particular technique

An extension for the olympiad level (advanced students)

The following topics are not required for the standard school competitions, but they are a very important part of preparing for higher-level national competitions, the SIO final, national olympiads and IOI-style tasks.

These areas require serious experience in solving tasks, a good knowledge of the basic algorithms and the ability to combine several techniques in one problem.

Advanced graph algorithms

Graphs
Minimum spanning tree
Prim's and Kruskal's algorithms for optimizing networks.
DAG
Topological sorting
Working with dependencies and directed acyclic graphs.
SCC
Strongly connected components
Kosaraju's and Tarjan's algorithms.

MST — Minimum spanning tree

  • Prim's algorithm
  • Kruskal's algorithm
  • Disjoint Set Union (DSU)

Topological sorting

  • DAG graphs
  • dependencies
  • DP on graphs

Strongly connected components (SCC)

  • Kosaraju
  • Tarjan
  • graph compression

Bellman–Ford

  • negative weights
  • detecting cycles

Advanced dynamic programming

DP on graphs
DAG DP
Combining topological sorting and DP.
Bitmask DP
States with subsets
Problems with n ≤ 20.

DP on graphs (DAG DP)

It combines topological sorting and dynamic programming.

  • the shortest / longest path in a DAG
  • counting paths
  • optimizing dependencies

DP with bitmasks

  • TSP
  • subsets

Advanced data structures

  • Segment tree
  • Fenwick (BIT)
  • combined structures

Segment tree

Fenwick (BIT)

Recommendation: Introduce these topics only after DFS/BFS, Dijkstra and basic DP.

A note on the sources of the tasks

All links lead to the sources of the tasks (LeetCode, GeeksforGeeks, Petlja) or to local solutions on Svet programiranja. The code and the detailed explanations on the local pages are original and adapted for educational use.