Month: May 2020
Minus and Minus Give Plus
Everyone knows that two consecutive (adjacent) “minus” signs can be replaced with a single “plus” sign. You are given the string $s$, consisting of “plus” […]
Decoding of Integer Sequences
Polycarp is developing a method for transmitting $n$ integer sequences over a network. This method should support the transmission of an arbitrary number of integer […]
Sliding Doors
Imagine that you are the CEO of a big old-fashioned company. Unlike any modern and progressive company (such as JetBrains), your company has a dress […]
Longest Saw
You are given the sequence $a_1, a_2, \dots, a_n$. You can choose any subset of elements and then reorder them to create a “saw”. The […]
Graph Decomposition
You are given an undirected graph consisting of $n$ vertices and $m$ edges. Recall that a cycle is a path that starts and ends in […]
Good Subsets
You are given $n$ segments on the $Ox$ axis. The $i$-th segment is given as a pair $l_i, r_i$, where $l_i$ is the position of […]
Another One Bites The Dust
Let’s call a string good if and only if it consists of only two types of letters — ‘a’ and ‘b’ and every two consecutive letters are distinct. […]
Crazy Diamond
You are given a permutation $p$ of integers from $1$ to $n$, where $n$ is an even number. Your goal is to sort the permutation. […]
Born This Way
Arkady bought an air ticket from a city A to a city C. Unfortunately, there are no direct flights, but there are a lot of […]
Dirty Deeds Done Dirt Cheap
You are given $n$ pairs of integers $(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)$. All of the integers in the pairs are distinct and are […]
Foo Fighters
You are given $n$ objects. Each object has two integer properties: $val_i$ — its price — and $mask_i$. It is guaranteed that the sum of all prices […]
Earth Wind and Fire
There are $n$ stones arranged on an axis. Initially the $i$-th stone is located at the coordinate $s_i$. There may be more than one stone […]
Gold Experience
Consider an undirected graph $G$ with $n$ vertices. There is a value $a_i$ in each vertex. Two vertices $i$ and $j$ are connected with an […]
Matching vs Independent Set
You are given a graph with $3 \cdot n$ vertices and $m$ edges. You are to find a matching of $n$ edges, or an independent set of […]
Welfare State
There is a country with $n$ citizens. The $i$-th of them initially has $a_{i}$ money. The government strictly controls the wealth of its citizens. Whenever […]
Rectangle Painting 2
There is a square grid of size $n \times n$. Some cells are colored in black, all others are colored in white. In one operation […]
Rectangle Painting 1
There is a square grid of size $n \times n$. Some cells are colored in black, all others are colored in white. In one operation […]
