The Stern-Brocot tree and Farey sequences

2021

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 […]

15 Puzzle Game: Existence Of The Solution

2021

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

2021

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

2021

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

2021

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

2021

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

2021

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

2021

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)

2021

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

2021

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

2021

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

2021

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

2021

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 […]

2 – SAT

2021

SAT (Boolean satisfiability problem) is the problem of assigning Boolean values to variables to satisfy a given Boolean formula. The Boolean formula will usually be […]

Paint the edges of the tree

2021

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

2021

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

2021

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

2021

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

2021

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

2021

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 […]