Josephus Problem

0

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

Sprague-Grundy theorem

0

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

K-th order statistic in O(N)

0

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

Range Minimum Query

0

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

0

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

0

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

Topological Sorting

0

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