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.
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).
- recursion and backtracking
- combinatorics
- sorting and binary search
- basic data structures
- ✔ 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.
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
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.
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
Suggested practice tasks
- A correct expression — generating combinations and expressions.
- Permutations and subsets — Svet programiranja (SR)
- Counting the ways (decoding / Fibonacci, in Serbian)
- Generating combinatorial objects (in Serbian)
- N queens — a detailed explanation (task 9) (SR)
- Analysis of several solutions of the N queens problem
- Sudoku solver (SR)
- A Sudoku solver — a detailed explanation (task 10) (SR)
- LeetCode — N Queens
- LeetCode — Sudoku Solver
- Word Search (DFS + backtracking)
- Words in a grid — a local solution (SR)
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?
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.
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
Suggested practice tasks
- Find the first element ≥ x in a sorted array.
- Find the last element ≤ x in a sorted array.
- Count the occurrences of an element by using lower_bound and upper_bound.
- Sort intervals by their start, and then by their end.
- Sort objects by several criteria by using a comparator function.
- Solve a task by using the Binary Search on Answer approach.
- LeetCode — Binary Search
- Search Insert Position
- First and Last Position of Element in Sorted Array
- Koko Eating Bananas — a classic example of the "binary search on answer" approach.
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.
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
- 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.
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.
- 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
Suggested practice tasks
- AtCoder DP A — Frog 1
- Climbing Stairs — first recursion, then memoization and finally tabulation.
- 0/1 Knapsack — Svet programiranja
- Coin Change — the minimum number of coins.
- Coin Change — the number of ways to form a given sum.
- Longest Common Subsequence (LCS)
- AtCoder Educational DP Contest
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)
- Analyse the Fibonacci recursion and find the repeated subproblems.
- Measure the number of function calls for n=30 and n=40.
- Implement memoization and compare the number of calls.
- Move on to bottom-up tabulation.
- Optimize the memory from O(n) to O(1).
- Solve Frog 1 using the same principle.
- Start the first Knapsack and Coin Change tasks.
- 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.
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
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
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).
- 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.
Suggested practice tasks
- Petlja — The maximum path sum through a matrix (in Serbian)
- Svet programiranja — The maximum sum through a matrix
- Longest Common Subsequence (LCS)
- LeetCode — Longest Common Subsequence
- LeetCode — Edit Distance
- AtCoder DP C — Vacation
- AtCoder DP E — Knapsack 2
Work plan (suggestion)
- Start with simple DP problems on matrices.
- Draw the DP table by hand for small input examples.
- Analyse how the transitions between states are formed.
- Move on to LCS and problems on strings.
- Implement Edit Distance.
- Try to optimize the memory to two rows.
- 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.
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.
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
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[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]);
}
}
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
- Knapsack — Svet programiranja
- AtCoder DP D — Knapsack 1
- AtCoder DP E — Knapsack 2
- LeetCode — Coin Change
- Partition Equal Subset Sum
Work plan (suggestion)
- Implement the classic 2D Knapsack.
- Understand the meaning of dp[i][w].
- Convert the 2D DP into a 1D DP.
- Experiment with the direction of the loops (0/1 vs unbounded).
- Solve Coin Change (the number of ways + the minimum number of coins).
- 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
- 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
- BFS and DFS — Svet programiranja (SR)
- The number of islands — BFS/DFS in a matrix (SR)
- The shortest path in a maze — BFS (SR)
- LeetCode — Number of Islands
- Takprog / Petlja — graph tasks (in Serbian)
- Learn the basic concepts and how to represent a graph.
- Implement DFS and BFS from scratch.
- Practise graphs in a matrix (4/8 directions).
- Tell when to use BFS and when DFS.
- Solve at least 5 graph tasks.
- 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.
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
visitedarray, wrong comparison of pairs
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});
}
}
}
}
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
- Svet programiranja — Dijkstra's algorithm (SR)
- Priority Queue in C++ (SR)
- CSES — Shortest Routes I
- SPOJ — Easy Dijkstra
- AtCoder — Come Back Quickly
- Takprog / Petlja — graph tasks (in Serbian)
- Solve the shortest path with BFS in an unweighted graph.
- Understand why BFS does not work for different weights.
- Implement Dijkstra's algorithm.
- Simulate the algorithm by hand on a small graph.
- Solve several tasks from the CSES / SPOJ platforms.
- Dijkstra does not work with negative weights.
- Complexity: O((V + E) log V).
- Use
long longfor 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.
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
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
- Svet programiranja — Number theory (guide) (SR)
- Euclid's algorithm — explanation and examples
- An arithmetic triangle — the sum of a row with a formula (solution)
- CSES — Common Divisors
- SPOJ — Extended GCD
- Takprog / Petlja — number theory (in Serbian)
- Modular arithmetic — a detailed explanation (SR)
- Fast exponentiation — examples and applications
Work plan (suggestion)
- Revise the basic properties of divisibility and GCD/LCM.
- Learn and implement Euclid's algorithm.
- Practise modular arithmetic.
- Implement fast exponentiation.
- 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.
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.
- efficiently processing a large number of queries
- working with logarithmic structures
- combining data structures with graphs and DP
- optimizing time complexity
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
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";
}
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
- 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
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
- A guide to algorithms — Svet programiranja
- CP-Algorithms — Fenwick Tree
- CP-Algorithms — Segment Tree
- CSES Problem Set — the Range Queries section
- Priority Queue in C++ (SR)
Work plan (suggestion)
- Revise the STL structures (set, map, priority_queue).
- Understand the difference between O(n), O(log n) and O(1).
- Learn the basic idea of the Fenwick tree.
- Go through the introduction to the segment tree.
- Practise tasks with a large number of queries.
In many tasks the key is not a complicated algorithm, but choosing the right data structure.
- 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 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
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.
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 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)
- Revise all the previous areas.
- Solve combined tasks.
- Practise modelling problems.
- Do competition simulations.
- Analyse your own solutions and mistakes.
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
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
MST — Minimum spanning tree
- Prim's algorithm
- Kruskal's algorithm
- Disjoint Set Union (DSU)
- On this site: MST — Prim (SR)
- On this site: MST — Kruskal (SR)
Topological sorting
- DAG graphs
- dependencies
- DP on graphs
- On this site: Topological sorting (SR)
Strongly connected components (SCC)
- Kosaraju
- Tarjan
- graph compression
- External: CP-Algorithms — SCC
Bellman–Ford
- negative weights
- detecting cycles
- External: CP-Algorithms — Bellman–Ford
Advanced dynamic programming
DP on graphs (DAG DP)
It combines topological sorting and dynamic programming.
- the shortest / longest path in a DAG
- counting paths
- optimizing dependencies
- On this site: DP on DAGs (SR)
- On this site (REQUIRED): The longest path in a DAG (SR)
DP with bitmasks
- TSP
- subsets
Advanced data structures
- Segment tree
- Fenwick (BIT)
- combined structures
Segment tree
- On this site: Segment tree (SR)
Fenwick (BIT)
- On this site: Fenwick tree (SR)
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.
