2020-2021 ICPC, Northern Eurasia, Southern and Volga Russian Regional Contest

Russia, Saratov, November, 15, 2020

Problem A. LaIS
Let’s add 0 to the beginning of a, then we’ll increase LaIS by one and so it will always start from 0. Let’s
look at any almost increasing subsequence (aIS) and underline elements, which are minimums in at least
one consecutive pair, for example, [0, 1, 2, 7, 2, 2, 3].
Note that underlined elements form increasing subsequence (IS) and there is no more than
one element between each consecutive pair. What constraints these elements have? Obviously,
a[posi−1 ] ≤ a[posi ] ≥ a[posi+1 ], but we can ease the constraints just to a[posi−1 ] ≤ a[posi ], i. e. we
can allow a[posi ] < a[posi+1 ], since aIS will still be aIS.
Now, note that between posi−1 and posi+1 we can choose any j such that a[posi−1 ] ≤ a[j], so we can
always choose the first such j, moreover we can precalculate such j as nxti for each ai . Using stacks or
something similar.
Now, we can note that each ai is either minimum in LaIS or i = nxtj for some other element aj . And
we can write the following dynamic programming: let d[i] be the LaIS which finish in ai and it’s the last
minimum (we can think that the last element of LaIS is minimum in the imaginary pair). To calculate it,
we can iterate i from left to right and store for each value x the length of LaIS with the last minimum
(not the last element) equal to x in Segment Tree (ST).
So, di is equal to “get maximum over segment [0, ai ] in ST” plus 1. And we update ST in two moments:
firstly, right now with value di in position ai and secondly, after we meet the element nxti with value
di + 1 also in position ai .
After we process all i we’ll get ST where for each x the length of LaIS with last minimum equal to x will
be stored and the answer will be equal just to “maximum over all tree (segment [0, n])”.
In total, we should calculate nxti for each ai (we can do it in linear time using stack) and maintain
Segment Tree with two basic operations: range maximum and update in position. The time complexity is
O(n log(n)) and the space complexity is O(n).

Problem B. Bakery
Let’s look at all n days with some fixed k. Obviously, the seller works like a stack, so let’s divide all days
into segments in such a way, that the stack is emptied between consecutive segments. We can note that
after we’ve got these segments — the answer is the maximum length among all segments. Why? Because
the stalest bread on the bottom of the stack and we can’t sell it until we empty the stack.
Now, let’s set k = 109 and look at what happens when we gradually lower k. With k = 109 , we sell all
bread that we baked on the same day, so all segments consist of one day [i, i + 1). Now, if we start lowering
k then at some moment segments will start to merge (and only merge), since k is not enough to sell all
bread in this interval. Since no segment will split up, there will be only n − 1 merging.
So we can look only at moments k when either several segments merge or when we should answer the
query. With what k the segment [p1 , p1 )jwill
P
startk to merge with the next segment [p1 , p2 )? The answer
P ( ai )−1
is when (p2 − p1 ) · k < ai or k = p2 −p1 .
p1 ≤i<p2

So, we can for each segment [pi , pi+1 ) maintain its value ki when it will start merging with next segment in
set. And if we want to calculate the answer for a given k from the queries, we should merge all segments
with ki ≥ k, while updating the current maximum length among all segments.
Since merging two segments require two operations with the set then the total time complexity is
O(m + n log n).

Problem C. Berpizza
The hardest part of this problem is to efficiently implement the third query, i. e. finding the customer
with the greatest value of m and erasing it. Simply iterating on all of them is too slow, since there may
be up to 2.5 · 105 such queries and up to 5 · 105 customers at the pizzeria.

Page 1 of 7
 2020-2021 ICPC, Northern Eurasia, Southern and Volga Russian Regional Contest
Russia, Saratov, November, 15, 2020
There are several solutions to this issue, I will describe two of them. The first solution is to treat each
customer as a pair (id, m), where id is the number of the customer. Then the first query means “insert a
new pair”, the second query — “remove the pair with minimum id”, and the third query — “remove the
pair with maximum m”. To maintain them, we can use two balanced binary trees that store these pairs
— one will store them sorted by id, and the other — sorted by m. Then the second query means “find
the leftmost element in the first tree and erase it from both trees”, and the third query means “find the
rightmost element in the second tree and erase it from both trees”. Balanced binary trees can perform
these operations in O(log n), where n is the size of the tree. Note that in most languages you don’t have to
write a balanced binary tree from scratch — for example, the containers std::set in C++ and TreeSet
in Java already support all of the required operations.
The second solution maintains three data structures: a queue for supporting the queries of type 2, a heap
for supporting the queries of type 3, and an array or set that allows checking whether some customer was
already deleted by a query. Finding the customer that came first using a queue or has a maximum value
of m using a heap is easy, but deleting some element from queue/heap is much harder (because we have
to delete some arbitrary element, not necessarily the element at the head of the queue/heap). Instead,
we can do it the other way: when we delete some customer from one of these data structures, we mark
it as deleted. And while processing the following queries of type 2 or 3, we should check the element in
the head of the data structure and, if it is marked as deleted, remove it before processing the query. Note
that there can be multiple such elements, so it should be done in a loop. Since each element is deleted at
most once, this solution works in O(n log n) amortized.

Problem D. Firecrackers
The first crucial observation that we need is the following one: it is optimal to light and drop some
firecrackers, and only then start running away from the guard (that’s because running away doesn’t
actually do anything if none of the firecrackers are lit). The hooligan shouldn’t drop more than |a − b| − 1
firecrackers, because otherwise he will be caught before starting running away, and the last firecracker he
dropped won’t go off.
Okay, now suppose the hooligan wants to explode exactly f firecrackers. It’s obvious that he wants to
choose the f firecrackers with minimum si , but in which order he should drop them? If the i-th firecracker
he drops goes off in sj seconds, then it will explode on the (i + sj )-th second. We have to choose an
ordering of the firecrackers that minimizes the maximum of (i + sj ) in order to check that the hooligan
has enough time to see all the firecrackers he dropped explode. It can be shown that we can drop the
firecracker with the maximum sj first, then the firecracker with the second maximum sj , and so on, and
the maximum of (i + sj ) is minimized (obviously, we consider only the firecrackers with f minimum values
of si ).
This leads us to a solution with a binary search on f in O(n log n): we can check that the hooligan
can explode at least f firecrackers in O(n) (after sorting the sequence s beforehand), and binary search
requires to check it for only log n values of f .

Problem E. Four Segments

Suppose the values of a1 , a2 , a3 , a4 are sorted in non-descending order. Then the shorter side of the
rectangle cannot be longer than a1 , because one of the sides must be formed by a segment of length a1 .
Similarly, the longer side of the rectangle cannot be longer than a3 , because there should be at least two
segments with length not less than the length of the longer side. So, the answer cannot be greater than
a1 · a3 .
It’s easy to construct the rectangle with exactly this area by drawing the following segments:

• from (0, 0) to (a1 , 0);

• from (0, a3 ) to (a2 , a3 );
• from (0, 0) to (0, a3 );

Page 2 of 7
 2020-2021 ICPC, Northern Eurasia, Southern and Volga Russian Regional Contest
Russia, Saratov, November, 15, 2020
• from (a1 , 0) to (a1 , a4 ).

So, the solution is to sort the sequence [a1 , a2 , a3 , a4 ], and then print a1 · a3 .

Problem F. Full Turn

Lets define for person with index i their initial vision vector as vector (ui − xi , vi − yi ). It is possible to
prove that two persons will make eye contact during 360 rotation if and only if their initial vision vectors
are collinear and oppositely directed. Note that the position of the persons does not matter, only their
vision vectors.
E.g. lets assume that person A has initial vision vector (3, −4) and person B - (−6, 8). These vectors are
collinear and oppositely directed, hence person A and B will make eye contact during the rotation.
If we try to check separately for each pair of persons if they will make eye contact, that would take too
much time. For example for n = 105 that would take ≈ 5 ∗ 109 checks.
Instead we should use a different approach. First, lets normalize vision vector of each person by dividing
its coordinates by GCD of absolute values of the coordinates. Here GCD stands for greatest common
divisor. E.g. vector’s coordinates (6, −8) should be divided by GCD(|6|, | − 8|) = GCD(6, 8) = 2, and
the normalized vector will be (3, −4). There is a special case for vectors, which have zero as one of the
coordinates: (0, C), (0, −C), (C, 0) and (−C, 0), where C is some positive integer. These should be
normalized to vectors (0, 1), (0, −1), (1, 0) and (−1, 0) respectively.
After normalization all collinear and co-directed vectors will have exactly the same coordinates. Lets
group such vectors and count the number of vectors in each group. Then it is obvious that each person
from group with vector (x, y) will make eye contact with each person from group with vector (−x, −y).
If the first group has k vectors and the second group has l vectors, in total there will be k ∗ l eye contacts
between members of these two groups. And also members of these two groups will not make eye contact
with members of any other groups.
So fast algorithm should create a map, where key would be group’s vector and value - number of persons
in the group. Then the algorithm should iterate over groups in the map, for each group find the oppositely
directed group, and add to the answer multiplication of these groups’ sizes.
Note that the maximum possible answer is (n/2)2 . That would be 2.5 ∗ 109 when n = 105 , which does not
fit into signed int32.

Problem G. Hobbits
Let’s start with the general idea of the solution. To solve the problem, we need to iterate over all relief
segments and understand, which part the segment is seen by the Eye. A segment point can be hidden from
the Eye by several mountains, but it is enough to track only the highest mountain. Generally speaking,
the relief segments can be processed in any order, bit it would be more convenient to iterate on them
backwards — i.e. in the order from the Eye to the start point. Processing the segments in reversed order
will allow to recalculate the highest mountain easier.
Let’s now discuss implementation details. Formally speaking, there are n relief points pi = (xi , yi )
(1 ≤ i ≤ n) and the Eye point E = (xn , yn + H). Each relief point defines its own angle αi , which
is measured counter-clockwise between positive direction of the OX axis and the (E, pi ) vector. Now,
having two relief points pi and pj (i < j), it can be said that pi is hidden from the Eye if αi > αj . When
this check is implemented in the solution, to avoid the precision loss, it is recommended to use vector
product and analyse its sign to understand the relation of the angles. This check is done in O(1) time.
Being able to understand when a point is hidden from the Eye by another point, it is possible to calculate,
which part of a segment (pi , pi+1 ) is seen by the Eye. First of all let’s note, that if the segment left point
pi is hidden by its right point pi+1 , then the entire segment is hidden from the Eye. Now, we have the
situation when left segment point is not hidden from the Eye by its right point. But the segment or its
part can still be hidden by the highest mountain (point M ), which is a point with minimal angle from all
relief points, located to the right of our segment. Here three cases are possible:

Page 3 of 7
 2020-2021 ICPC, Northern Eurasia, Southern and Volga Russian Regional Contest
Russia, Saratov, November, 15, 2020
• both pi and pi+1 are hidden by M — in this case the entire segment is hidden and we switch to the
next segment;

• both pi and pi+1 are visible by the Eye (not hidden by the highest mountain M ) — in this case the
entire segment is visible and we should add its length to the answer;

• left segment point pi is visible by the Eye, but right segment point pi+1 is hidden by M — in this
case we need to find intersection point I of the segment (pi , pi+1 ) and the ray (E, M ). What is left
- add length of (pi , I) segment to the answer.

It is very convenient to implement segment and ray intersection in a parametric way, when intersection
point I is represented as I = pi + t1 ∗ (pi+1 − pi ) = E + t2 ∗ (M − E) and then parameters t1 and t2 are
found as solutions of linear equation system.
Now, let’s conclude the final algorithm:

1. Iterate over all relief segments from right to left, keeping the highest mountain point M .

2. Analyze how left and right points of the current segment are located relatively to each other and
point M .

3. Recalculate M , taking points of the current segments as candidates for the highest mountain.

Total algorithm complexity is O(N ).

Problem H. K and Medians

Since after each operation we erase exactly k − 1 element from a then if (n − m) 6≡ 0 (mod (k − 1)) then
the answer is NO.
Otherwise, if there is such element bpos such that there are at least k−1
2 erased elements lower than bi and
k−1
at least 2 erased elements greater that bi , then answer is YES, otherwise NO.
Let’s prove this criterion in two ways. From the one side, in the last step, we should choose k elements
and erase them excepts its median, so the median is exactly that element bpos .
From the other side, let’s prove that if there is such bpos then we can always choose operations to get
sequence b. Let’s make operations in such a way that in the last step we’ll erase bpos , d = k−1
2 elements
lower bpos and d elements greater bpos . Since, it doesn’t matter which d elements to take from left and
right of bpos , we will only consider number of such elements.
Let’s denote x and y as the initial number of elements from left and right of bpos to erase. We know that
x ≥ d and y ≥ d. and we want to make both of them equal to d.
Let x0 = x − d and y 0 = y − d. We can think that we have x0 free elements to erase from left and y 0 from
the right. While x0 + y 0 ≥ k let’s take any k free elements that should be erased and erase k − 1 of them.
Then we get situation 0 ≤ x0 < k, 0 ≤ y 0 < k and x0 + y 0 < k. Since (n − m) is divisible by (k − 1), then
it means that x0 + y 0 = k − 1.
Let’s look at what we can do now. We should take one of “reserved” elements to participate in erasing
last x0 + y 0 free elements but it shouldn’t break the situation with d lower elements, bpos and d greater
elements.
If x0 ≥ y 0 , let’s take one extra element which is lower than bpos , then after erasing, the remaining median
will also be lower than bpos .
If x0 < y 0 , let’s take one extra element greater than bpos , then the remaining median will also be greater
than bpos .
In the end, we choose d elements lower, bpos and d elements greater. Erase them except its median bpos
and get the desired array b.

Page 4 of 7
 2020-2021 ICPC, Northern Eurasia, Southern and Volga Russian Regional Contest
Russia, Saratov, November, 15, 2020

Problem I. Plane Tiling

One of the solutions is to consider an infinite 2 dimensional plane and draw a grid with lines parallel to
vectors (dx1 , dy1 ) and (dx2 , dy2 ). By doing so we will get a tiling of the plane with parallelepipeds, one
of them will have corners at (0, 0), (dx1 , dy1 ), (dx1 + dx2 , dy1 + dy2 ), (dx2 , dy2 ).
All the parallelepipeds are same shape and all of them can be represented by translating one of them by
vector (a · dx1 + b · dx2 , a · dy1 + b · dy2 ), where a and b are all possible integer pairs. Thus, if we “rasterize”
one of them, we will get a correct solution.
To do so, we can represent the parallelepiped as two triangles and rasterize each of them individually. To
rasterize a triangle, we need to select those cells which center is either inside of it, or located on the “top”
or “left” edge of it. A “top” edge is an edge that is perfectly horizontal and whose defining vertices are
above the third one. A “left” edge is an edge that is going up if we go in triangle’s clockwise order.
This way, no cell is going to be selected twice in case we “rasterize” two triangles sharing an edge, and
since we are tiling the plane with given parallelepipeds rasterized cells are exactly our solution.
If vectors (dx1 , dy1 ) and (dx2 , dy2 ) are either collinear or one of them is zero, the answer is “NO”.
Also there is another solution. First of all we have to calculate d — absolute value of determinant of the
matrix formed by the given vectors:
d = |det((dx1 , dy1 ), (dx2 , dy2 ))| = |dx1 ∗ dy2 − dx2 ∗ dy1 |
If given value n is not equal to d then there is no solution, in particular if d = 0 there is no required n
pairs of integers.
Now let n=d and dx = gcd(dx1 , dx2 ), dy = gcd(dy1 , dy2 ). Let’s go to the same problem with smaller
integers — we divide dx1 , dx2 by dx and divide dy1 , dy2 by dy . Also we define m = n/(dx · dy )
(n=d so it is divisible by dx · dy ). So firstly we need to find such m points (xi , yi ) that all values
(xi + a · dx1 + b · dx2 , yi + a · dy1 + b · dy2 ) are different. It is enough for solution, because we still
have m equal to the absolute value of the determinant of the new matrix.
It turns out that it is easy to find such set of points. In particular we may choose points
(0, 0), (0, 1), · · · , (0, m − 1), i.e. xi = i, yi = 0. Let’s prove that such set is correct. Assume that for
some non-zero pair (a, b) and for some j we also have one of these points: xi = xj + a · dx1 + b · dx2 and
yi = yj + a · dy1 + b · dy2 . Considering yi = yj = 0, we have a · dy1 + b · dy2 = 0. Since dy1 and dy2
are coprime (we have divided it by dy ) a = k · dy2 , b = −k · dy1 for some integer k. If we use this for x
equation, we will have: xi − xj = k · dy2 · dx1 − k · dy1 · dx2 . I.e. xi − xj = k · (dx1 · dy2 − dx2 · dy1) =
±k · m. Also −m < xi − xj < m so this equation has no solution for integer non-zero k. Thus this set of
points is correct.
Finally having such m points we have to create an n-points solution for the original problem. Obviously
we need to multiply current answer coordinates by dx and dy . Then for each of these points, for each
0 ≤ rx < dx and for each 0 ≤ ry < dy we need to print a new point. So, the answer is (i · dx + rx , ry ) for
each 0 ≤ i < m, 0 ≤ rx < dx , 0 ≤ ry < dy .

Problem J. Road Reform

We will consider two cases: the road network without roads having si > k is either connected or not.
Checking that may be done with the help of DFS, BFS, DSU, or any other graph algorithm/data structure
that allows checking if some graph is connected.
If the network without roads having si > k is not connected, then we have to take several roads with
si > k into the answer. Since their speed limit
P is too high, we have to decrease the speed limit on them to
k. Then the required number of changes is max(0, si − k), where R is the set of roads that are added
i∈R
to the answer. To minimize this sum, we can set each road’s speed limit to max(0, si − k) and find the
minimum spanning tree of the resulting graph.
Unfortunately, this approach doesn’t work in the other case — we may build a road network having the

Page 5 of 7
 2020-2021 ICPC, Northern Eurasia, Southern and Volga Russian Regional Contest
Russia, Saratov, November, 15, 2020
maximum speed limit less than k, not exactly k. We have to choose a road with the current speed limit
as close to k as possible, i. e. the one with the minimum value of |si − k|. After applying |si − k| changes
to it, we can choose n − 2 roads having si ≤ k to form a spanning tree with the chosen road (it is always
possible due to the properties of the spanning tree: if we have a spanning tree and we want to add an edge
m
of the graph to it, we can always find another edge to discard). So, in this case, the answer is min |si − k|.
i=1

Problem K. The Robot

It is obvious that the cell that can be the answer must belong to the original path of the robot. Thus,
there are at most n candidate cells in the answer. In order to make sure that a candidate cell is indeed the
answer; it is necessary to simulate the movement of the robot, taking into account this cell as an obstacle.
No more than n actions will be spent on one such simulation. Therefore, to check all n candidates, the
total number of actions spent is will not exceed n2 , which fits into the requirements for the running time
(time limit) of a solution.

Problem L. Prime Divisors Selection

Let’s find for each prime integer p ≤ 109 amount of integers pq among the given integers. If there are no
more than 2 such integers, this prime p is not interesting for us: if we add one such integer to the answer,
we may always select exactly one divisor p in a suitable sequence so it will not be friendly.
Otherwise let’s call such p important and find a group Xp (with some size ki > 1) — all integers pq in the
given set. So we have several (t) such groups with sizes k1 , k2 , . . . kt . Now there are some different cases.
Case 1: required size k ≤ k1 + k2 + · · · + kt .
If k is odd and ki =2 for each i, we have to find some integer y that has minimum possible different
important primes in factorization (and does not have not important primes). If there is no such y,
obviously, there is no solution. Now let there is y that has u different primes in factorization. If u ≤ (k−1)/2
we may take all u groups necessary for this integer y and add some other groups Xp in order to have
exactly k numbers in the result (if u < (k − 1)/2).
If k is even and ki = 2 for each i, we may just take any k/2 groups by 2 integers.
If kj > 2 for some j it is easy to check that we may always find the ideal sequence. Let’s start to add
groups with the maximum sizes while it is possible. Now we have total size k1 ≤ k and q = k − k1 ‘empty’
space. If q ≥ 2, we may just add q integers from the next group. If q = 1, we may remove one integer
from the greatest group (because its size is at least 3) and add 2 integers from the next group.
Case 2: k > k1 + k2 + . . . + kt .
First of all let’s take all the groups Xp to the answer. Now each of the remaining integers is either
represented as a product of important primes, or not. If it is represented, then we can add it to the answer
and the set will remain ideal. Otherwise if we add such number, we can choose any prime divisor from it
that is not important and the set will not be ideal. So, we just have to check whether there are enough
integers that are represented as a product of important primes and add any k - k1 - k2 - . . . - kt of them
to the answer. If there are not enough such integers, there is no solution.
How to find all important primes? We are interested only in groups Xp = pq with sizes at least 2. So each
such group either has an integer p2 or an integer pq with q ≥ 3. To find all the numbers in the first case,
we may just check for each given integer whether it is p2 for some prime p. For the second case we have
p ≤ 106 , so we may find all the possible powers for each prime p ≤ 106 .

Problem M. Similar Sets

Let’s define D = m1/2 , where m is the total amount of integers. Now let’s call a set of integers ‘large’ if
its size is at least D and ‘small’ otherwise.
Firstly let’s check whether there is a large set that has two common integers with some other (small or
large) set. Let’s try to find a similar set for each large set S separately. For each integer x in S we may

Page 6 of 7
 2020-2021 ICPC, Northern Eurasia, Southern and Volga Russian Regional Contest
Russia, Saratov, November, 15, 2020
set flag w[x]=1. Now for each other set T with size k we may calculate amount of integers x in T that
satisfy condition w[x]=1 (i.e. amount of common integers with S) using O(k) operations. So, we will use
O(m) operations for each large set S. Since D=m1/2 we will have at most m/D = D large sets and will
perform O(D ∗ m) = O(m3/2 ) operations.
Now we have to check whether there are two similar small sets. For each small set S let’s find all pairs
of integers (x, y), x < y in this set. If there are two equal pairs in different sets, that sets are similar.
To find such pairs we may just create a separate array for each integer x and add all values y to it. It is
possible to check whether there are two equal integers in array in O(k) operations, where k is the size of
this array. Since the size of each small set is at most D we will have at most D ∗ k pairs for each set of
size k and at most D ∗ m pairs in total. So we will perform O(D ∗ m) = O(m3/2 ) operations.

Problem N. Waste Sorting

It is quite obvious that if c1 < a1 , c2 < a2 or c3 < a3 , the answer is NO because it is impossible to fit
even the items that fit only into one container. Otherwise, let’s get rid of a1 , a2 , a3 by decreasing ci by ai
(1 ≤ i ≤ 3).
Now we have a problem with 3 containers and only 2 item types (4-th and 5-th), the fourth item type
fits only into the first and into the third container, the fifth item type — into the second and into the
third container. Since the first container accepts only items of type 4, we should fit the maximum possible
number of items of type 4 there — that is, min(a4 , c1 ) items. Similarly, we should fit the maximum possible
number of items of type 5 into the second container (min(a5 , c2 ) items). After that, we only have to check
that all the remaining items can be fit into the third container.

Page 7 of 7