The Stern-Brocot tree and Farey sequences
1. Stern-Brocot tree The Stern-Brocot tree is an elegant construction to represent the set of all positive fractions. It was independently discovered by German mathematician […]
ACM
15 Puzzle Game: Existence Of The Solution
This game is played on a $4 \times 4$ board. On this board there are $15$ playing tiles numbered from 1 to 15. One cell […]
Josephus Problem
1. Statement We are given the natural numbers $n$ and $k$. All natural numbers from $1$ to $n$ are written in a circle. First, count […]
Optimal schedule of jobs given their deadlines and durations
Suppose, we have a set of jobs, and we are aware of every job’s deadline and its duration. The execution of a job cannot be […]
Scheduling jobs on two machines
This task is about finding an optimal schedule for $n$ jobs on two machines. Every item must first be processed on the first machine, and […]
Scheduling jobs on one machine
This task is about finding an optimal schedule for $n$ jobs on a single machine, if the job $i$ can be processed in $t_i$ time, […]
Sprague-Grundy theorem
1. Introduction This theorem describes the so-called impartial two-player game, i.e. those in which the available moves and winning/losing depends only on the state of the game. […]
Games on arbitrary graphs
Let a game be played by two players on an arbitrary graph $G$. I.e. the current state of the game is a certain vertex. The […]
K-th order statistic in O(N)
Given an array A of size N and a number K. The challenge is to find K-th largest number in the array, i.e., K-th order statistic. The basic idea – to use […]
Search the subarray with the maximum/minimum sum
Here, we consider the problem of finding a subarray with maximum sum, as well as some of its variations (including the algorithm for solving this […]
Longest increasing subsequence
We are given an array with $n$ numbers: $a[0 \dots n-1]$. The task is to find the longest, strictly increasing, subsequence in $a$. Formally we […]
Range Minimum Query
You are given an array $A[1..N]$. You have to answer incoming queries of the form $(L, R)$, which ask to find the minimum element in […]
Heavy-light decomposition
Heavy-light decomposition is a fairly general technique that allows us to effectively solve many problems that come down to queries on a tree . 1. Description Let there […]
Paint the edges of the tree
This is a fairly common task. Given a tree $G$ with $N$ vertices. There are two types of queries: the first one is to paint […]
Edge connectivity / Vertex connectivity
1. Definition Given an undirected graph $G$ with $n$ vertices and $m$ edges. Both the edge connectivity and the vertex connectivity are characteristics describing the […]
Topological Sorting
You are given a directed graph with $n$ vertices and $m$ edges. You have to number the vertices so that every edge leads from the vertex with […]
Kuhn’s Algorithm for Maximum Bipartite Matching
1. Problem You are given a bipartite graph $G$ containing $n$ vertices and $m$ edges. Find the maximum matching, i.e., select as many edges as […]
Check whether a graph is bipartite
A bipartite graph is a graph whose vertices can be divided into two disjoint sets so that every edge connects two vertices from different sets […]
Solving assignment problem using min-cost-flow
The assignment problem has two equivalent statements: Given a square matrix $A[1..N, 1..N]$, you need to select $N$ elements in it so that exactly one element is […]
