Sieve of Eratosthenes
Sieve of Eratosthenes is an algorithm for finding all the prime numbers in a segment $[1;n]$ using $O(n \log \log n)$ operations. The algorithm is […]
ACM
Fibonacci Numbers
The Fibonacci sequence is defined as follows: $$F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$$ The first elements of the sequence (OEIS […]
Linear Diophantine Equation
A Linear Diophantine Equation (in two variables) is an equation of the general form: $$ax + by = c$$ where $a$, $b$, $c$ are given […]
Extended Euclidean Algorithm
While the Euclidean algorithm calculates only the greatest common divisor (GCD) of two integers $a$ and $b$, the extended version also finds a way to represent GCD […]
Euclidean algorithm for computing the greatest common divisor
Given two non-negative integers $a$ and $b$, we have to find their GCD (greatest common divisor), i.e. the largest number which is a divisor of both $a$ […]
Binary Exponentiation
Binary exponentiation (also known as exponentiation by squaring) is a trick which allows to calculate $a^n$ using only $O(\log n)$ multiplications (instead of $O(n)$ multiplications […]
Cow and Exercise
Farmer John is obsessed with making Bessie exercise more! Bessie is out grazing on the farm, which consists of $n$ fields connected by $m$ directed […]
Cow and Vacation
Bessie is planning a vacation! In Cow-lifornia, there are $n$ cities, with $n-1$ bidirectional roads connecting them. It is guaranteed that one can reach any […]
Two Regular Polygons
You are given two integers $n$ and $m$ ($m < n$). Consider a convex regular polygon of $n$ vertices. Recall that a regular polygon is a polygon […]
Adding Powers
Suppose you are performing the following algorithm. There is an array $v_1, v_2, \dots, v_n$ filled with zeroes at start. The following operation is applied […]
Count the Arrays
Your task is to calculate the number of arrays such that: each array contains $n$ elements; each element is an integer from $1$ to $m$; […]
Array Shrinking
You are given an array $a_1, a_2, \dots, a_n$. You can perform the following operation any number of times: Choose a pair of two neighboring […]
Attack on Red Kingdom
The Red Kingdom is attacked by the White King and the Black King! The Kingdom is guarded by $n$ castles, the $i$-th castle is defended […]
Auto completion
You are given a set of strings $S$. Each string consists of lowercase Latin letters. For each string in this set, you want to calculate […]
Ehab the Xorcist
Given 2 integers $u$ and $v$, find the shortest array such that bitwise-xor of its elements is $u$, and the sum of its elements is $v$. Input […]
Ehab and Path-etic MEXs
You are given a tree consisting of $n$ nodes. You want to write some labels on the tree’s edges such that the following conditions hold: […]
Ehab’s Last Theorem
It’s the year 5555. You have a graph, and you want to find a long cycle and a huge independent set, just because you can. […]
Ehab’s REAL Number Theory Problem
You are given an array $a$ of length $n$ that has a special condition: every element in this array has at most 7 divisors. Find […]
Sum of Odd Integers
You are given two integers $n$ and $k$. Your task is to find if $n$ can be represented as a sum of $k$ distinct positive odd (not […]
