2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror...

Let's add 00 to the beginning of aa, then we'll increase LaIS by one and so it will always start from 00. 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][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]a[posi−1]≤a[posi]≥a[posi+1], but we can ease the constraints just to a[posi−1]≤a[posi]a[posi−1]≤a[posi], i. e. we can allow a[posi]<a[posi+1]a[posi]<a[posi+1], since aIS will still be aIS.

Now, note that between posi−1posi−1 and posi+1posi+1 we can choose any jj such that a[posi−1]≤a[j]a[posi−1]≤a[j], so we can always choose the first such jj, moreover we can precalculate such jj as nxtinxti for each aiai. Using stacks or something similar.

Now, we can note that each aiai is either minimum in LaIS or i=nxtji=nxtj for some other element ajaj. And we can write the following dynamic programming: let d[i]d[i] be the LaIS which finish in aiai 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 ii from left to right and store for each value xx the length of LaIS with the last minimum (not the last element) equal to xx in Segment Tree (ST).

So, didi is equal to "get maximum over segment [0,ai][0,ai] in ST" plus 11. And we update ST in two moments: firstly, right now with value didi in position aiai and secondly, after we meet the element nxtinxti with value di+1di+1 also in position aiai.

After we process all ii we'll get ST where for each xx the length of LaIS with last minimum equal to xx will be stored and the answer will be equal just to "maximum over all tree (segment [0,n][0,n])".

In total, we should calculate nxtinxti for each aiai (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(nlog(n))O(nlog⁡(n)) and the space complexity is O(n)O(n).

Let's look at all nn days with some fixed kk. 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=109k=109 and look at what happens when we gradually lower kk. With k=109k=109, we sell all bread that we baked on the same day, so all segments consist of one day [i,i+1)[i,i+1). Now, if we start lowering kk then at some moment segments will start to merge (and only merge), since kk is not enough to sell all bread in this interval. Since no segment will split up, there will be only n−1n−1 merging.

So we can look only at moments kk when either several segments merge or when we should answer the query. With what kk the segment [p1,p1)[p1,p1) will start to merge with the next segment [p1,p2)[p1,p2)? The answer is when (p2−p1)⋅k<∑p1≤i<p2ai(p2−p1)⋅k<∑p1≤i<p2ai or k=⌊(∑ai)−1p2−p1⌋k=⌊(∑ai)−1p2−p1⌋.

So, we can for each segment [pi,pi+1)[pi,pi+1) maintain its value kiki when it will start merging with next segment in set. And if we want to calculate the answer for a given kk from the queries, we should merge all segments with ki≥kki≥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+nlogn)O(m+nlog⁡n).

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

There are several solutions to this issue, I will describe two of them. The first solution is to treat each customer as a pair , where is the number of the customer. Then the first query means "insert a new pair", the second query — "remove the pair with minimum ", and the third query — "remove the pair with maximum ". To maintain them, we can use two balanced binary trees that store these pairs — one will store them sorted by , and the other — sorted by . 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 , where 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 , a heap for supporting the queries of type , 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 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 or , 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 amortized.

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 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 firecrackers. It's obvious that he wants to choose the firecrackers with minimum , but in which order he should drop them? If the -th firecracker he drops goes off in seconds, then it will explode on the -th second. We have to choose an ordering of the firecrackers that minimizes the maximum of 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 first, then the firecracker with the second maximum , and so on, and the maximum of is minimized (obviously, we consider only the firecrackers with minimum values of ).

This leads us to a solution with a binary search on in : we can check that the hooligan can explode at least firecrackers in (after sorting the sequence beforehand), and binary search requires to check it for only values of .

Suppose the values of , , , are sorted in non-descending order. Then the shorter side of the rectangle cannot be longer than , because one of the sides must be formed by a segment of length . Similarly, the longer side of the rectangle cannot be longer than , 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 .

It's easy to construct the rectangle with exactly this area by drawing the following segments:

• from to ;
• from to ;
• from to ;
• from to .

So, the solution is to sort the sequence , and then print .

Lets define for person with index their initial vision vector as vector (, ). 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 has initial vision vector (, ) and person - (, ). These vectors are collinear and oppositely directed, hence person and 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 that would take 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 (, ) should be divided by , and the normalized vector will be (, ). There is a special case for vectors, which have zero as one of the coordinates: (, ), (, ), (, ) and (, ), where is some positive integer. These should be normalized to vectors (, ), (, ), (, ) and (, ) 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 (, ) will make eye contact with each person from group with vector (, ). If the first group has vectors and the second group has vectors, in total there will be 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 . That would be when , which does not fit into signed int32.

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 relief points () and the Eye point . Each relief point defines its own angle , which is measured counter-clockwise between positive direction of the OX axis and the vector. Now, having two relief points and (), it can be said that is hidden from the Eye if . 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 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 is seen by the Eye. First of all let's note, that if the segment left point is hidden by its right point , 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 ), which is a point with minimal angle from all relief points, located to the right of our segment. Here three cases are possible:

• both and are hidden by  — in this case the entire segment is hidden and we switch to the next segment;
• both and are visible by the Eye (not hidden by the highest mountain ) — in this case the entire segment is visible and we should add its length to the answer;
• left segment point is visible by the Eye, but right segment point is hidden by  — in this case we need to find intersection point of the segment and the ray . What is left - add length of segment to the answer.

Now, let's conclude the final algorithm:

1. Iterate over all relief segments from right to left, keeping the highest mountain point .
2. Analyze how left and right points of the current segment are located relatively to each other and point .
3. Recalculate , taking points of the current segments as candidates for the highest mountain.

Since after each operation we erase exactly element from then if then the answer is NO.

Otherwise, if there is such element such that there are at least erased elements lower than and at least erased elements greater that , 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 elements and erase them excepts its median, so the median is exactly that element .

From the other side, let's prove that if there is such then we can always choose operations to get sequence . Let's make operations in such a way that in the last step we'll erase , elements lower and elements greater . Since, it doesn't matter which elements to take from left and right of , we will only consider number of such elements.

Let's denote and as the initial number of elements from left and right of to erase. We know that and . and we want to make both of them equal to .

Let and . We can think that we have free elements to erase from left and from the right. While let's take any free elements that should be erased and erase of them. Then we get situation , and . Since is divisible by , then it means that .

Let's look at what we can do now. We should take one of "reserved" elements to participate in erasing last free elements but it shouldn't break the situation with lower elements, and greater elements.

If , let's take one extra element which is lower than , then after erasing, the remaining median will also be lower than .

If , let's take one extra element greater than , then the remaining median will also be greater than .

In the end, we choose elements lower, and elements greater. Erase them except its median and get the desired array .

One of the solutions is to consider an infinite 2 dimensional plane and draw a grid with lines parallel to vectors (, ) and (, ). By doing so we will get a tiling of the plane with parallelepipeds, one of them will have corners at (, ), (, ), (, ), (, ).

All the parallelepipeds are same shape and all of them can be represented by translating one of them by vector (, ), where and 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 (, ) and (, ) 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  — absolute value of determinant of the matrix formed by the given vectors:

If given value is not equal to then there is no solution, in particular if there is no required pairs of integers.

Now let = and = , = . Let's go to the same problem with smaller integers — we divide , by and divide , by . Also we define (= so it is divisible by ). So firstly we need to find such points that all values are different. It is enough for solution, because we still have 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 , i.e. , . Let's prove that such set is correct. Assume that for some non-zero pair and for some we also have one of these points: = and = . Considering , we have . Since and are coprime (we have divided it by ) , for some integer . If we use this for equation, we will have: = . I.e. = = . Also so this equation has no solution for integer non-zero . Thus this set of points is correct.

Finally having such points we have to create an -points solution for the original problem. Obviously we need to multiply current answer coordinates by and . Then for each of these points, for each and for each we need to print a new point. So, the answer is for each , , .

We will consider two cases: the road network without roads having 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 is not connected, then we have to take several roads with into the answer. Since their speed limit is too high, we have to decrease the speed limit on them to . Then the required number of changes is , where is the set of roads that are added to the answer. To minimize this sum, we can set each road's speed limit to 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 maximum speed limit less than , not exactly . We have to choose a road with the current speed limit as close to as possible, i. e. the one with the minimum value of . After applying changes to it, we can choose roads having 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 of the graph to it, we can always find another edge to discard). So, in this case, the answer is .

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 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 actions will be spent on one such simulation. Therefore, to check all candidates, the total number of actions spent is will not exceed , which fits into the requirements for the running time (time limit) of a solution.

Let's find for each prime integer amount of integers among the given integers. If there are no more than 1 such integers, this prime is not interesting for us: if we add one such integer to the answer, we may always select exactly one divisor in a suitable sequence so it will not be friendly.

Otherwise let's call such important and find a group (with some size > 1) — all integers in the given set. So we have several () such groups with sizes , , ... . Now there are some different cases.

Case 1: required size .

If is odd and =2 for each , we have to find some integer that has minimum possible different important primes in factorization (and does not have not important primes). If there is no such , obviously, there is no solution. Now let there is that has different primes in factorization. If we may take all groups necessary for this integer and add some other groups in order to have exactly numbers in the result (if ).

If is even and = 2 for each , we may just take any groups by 2 integers.

If > 2 for some 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 and 'empty' space. If , we may just add integers from the next group. If , 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: > + + ... + .

First of all let's take all the groups 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 - - - ... - 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 with sizes at least 2. So each such group either has an integer or an integer with . To find all the numbers in the first case, we may just check for each given integer whether it is for some prime . For the second case we have , so we may find all the possible powers for each prime .

Let's define = , where is the total amount of integers. Now let's call a set of integers 'large' if its size is at least 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 separately. For each integer in we may set flag =1. Now for each other set with size we may calculate amount of integers in that satisfy condition =1 (i.e. amount of common integers with ) using operations. So, we will use operations for each large set . Since = we will have at most = large sets and will perform operations.

Now we have to check whether there are two similar small sets. For each small set let's find all pairs of integers , 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 and add all values to it. It is possible to check whether there are two equal integers in array in operations, where is the size of this array. Since the size of each small set is at most we will have at most pairs for each set of size and at most pairs in total. So we will perform = operations.

It is quite obvious that if , or , 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 , , by decreasing by ().

Now we have a problem with containers and only item types (-th and -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 , we should fit the maximum possible number of items of type there — that is, items. Similarly, we should fit the maximum possible number of items of type into the second container ( items). After that, we only have to check that all the remaining items can be fit into the third container.