651A - Joysticks

Idea author: fcspartakm, preparation: fcspartakm.

Main idea is that each second we need to charge the joystick with lowest power level. We can just emulate it or get an O(1) formula, because process is very simple.

651B - Beautiful Paintings

Idea author: fcspartakm, preparation: fcspartakm.

Lets look at the optimal answer. It will contain several segment of increasing beauty and between them there will be drops in the beautifulness. Solution is greedy. Lets sort all paintings and lets select which of them will be in the first increasing segment. We just go from left to right and select only one painting from each group of several paintings with the fixed beauty value. We continue this operation while there is at least one painting left.

With the careful implementation we will get solution.

But this solution gives us the whole sequence, but the problem was a little bit easier — to determine number of such segments. From the way we construct answer it is easy to see that the number of segments always equal to the maximal number of copies of one value. Obviously we can't get less segments than that and our algorithm gives us exactly this number. This solution is O(n).

651C - Watchmen/650A - Watchmen

Idea author: ipavlov, preparation: ipavlov.

When Manhattan distance equals to Euclidean distance?

d_eu² = (x₁ - x₂)² + (y₁ - y₂)²

d_mh² = (|x₁ - x₂| + |y₁ - y₂|)² = (x₁ - x₂)² + 2|x₁ - x₂||y₁ - y₂| + (y₁ - y₂)²

So it is true only when x₁ = x₂ or y₁ = y₂. This means that to count the number of such pair we need to calculate number of points on each horizontal line and each vertical line. We can do that easily with the use of std::map/TreeMap/HashMap/Dictionary, or just by sorting all coordinates.

If we have k points on one horizontal or vertical line they will add k(k - 1) / 2 pairs to the result. But if we have several points in one place we will count their pairs twice, so we need to subtract from answer number of pairs of identical points which we can calculate with the same formula and using the same method of finding equal values as before.

If we use TreeMap/sort then solution will run in and if unordered_map/HashMap then in O(n).

651D - Image Preview/650B - Image Preview

Idea author: fcspartakm, preparation: fcspartakm.

What photos we will see in the end? Some number from the beginning of the gallery and some from the end. There are 4 cases:

• We always go right.
• We always go left.
• We initially go right, then reverse direction, go through all visited photos and continue going left.
• We initially go left, then reverse direction, go through all visited photos and continue going right.

First two cases are straightforward, we can just emulate them. Third and fourth cases can be done with the method of two pointers. Note that if we see one more picture to the right, we spend more time on the right side and the number of photos seen to the left will decrease.

This solution will run in O(n).

Alternative solution is to fix how many photos we've seen to the right and search how many we can see to the left with binary search. For this method we will need to precompute times of seeing k pictures to the right and to the left. But this is solution is , which is slightly worse then previous one, but maybe it is easier for somebody.

651E - Table Compression/650C - Table Compression

Idea author: LHiC, preparation: iskhakovt.

First we will solve our problem when all values are different. We will construct a graph, where vertices are cells (i,  j) and there is an edge between two of them if we know that one is strictly less then the other and this relation should be preserved. This graph obviously has no cycles, so we can calculate answer as dynamic programming on the vertices:

for ( (u, v) : Edges) {
	dp[v] = max(dp[v], dp[u] + 1);
}

We can do this with topological sort or with lazy computations.

But if we will construct our graph naively then it will contain O(nm(n + m)) edges. To reduce this number we will sort each row and column and add edges only between neighbours in the sorted order. Now we have O(nm) edges and we compute them in time.

But to solve the problem completely in the beginning we need to compress all equal values which are in the same rows and columns. We can construct second graph with edges between equal cells in the same way as before and find all connected components in it. They will be our new vertices for the first graph.

650D - Zip-line

Idea author: LHiC, preparation: LHiC.

We need to find the longest increasing subsequence (LIS) after each change if all changes are independent.

First lets calculate LIS for the initial array and denote its length as k. While calculating it we will store some additional information: len_l[i] — maximal length of LIS ending on this element. Also we will need len_r[i] — maximal length of LIS starting from this element (we can calc it when searching longest decreasing sequence on reversed array).

Lets solve the case when we take our new element in the resulting LIS. Then we just calculate max_{i < a, h[i] < b}(len_l[i]) + 1 + max_{j > a, h[j] > b}(len_r[j]). It can be done online with persistent segment tree or offline with scanline with regular segment tree in time. This is the only case when answer can be larger then k, and it can be only k + 1 to be exact. Second case is when we change our element and ruin all LIS of size k. Then answer is k - 1. Otherwise we will have at least one not ruined LIS of size k and it is the answer.

Lets calculate number of different LIS by some modulo. It can be done with the same dynamic programming with segment tree as just finding LIS. Then we can check if liscount = liscount_left[a] * liscount_right[a]. This exactly means that all sequences go through our element.

But if you don't want the solution with such "hashing" there is another approach. For each element we can calc if it can be in LIS. If so then we know on which position it will go (len_l[i]). Then for each position we will know if there are several elements wanting to go on that position or only one. If only one then it means that all LIS are going through that element.

Overall complexity is .

P.S. We can solve this without segment tree, just using alternative approach to calculating LIS with dynamic programming and binary search.

650E - Clockwork Bomb

Idea author: Zlobober, preparation: Zlobober.

First idea is that answer is always equals to the number of edges from the first tree, which are not in the second one. This means that if we have an edge in both trees we will never touch it. So if we have such edge we can remove this edge and merge its two vertices together, nothing will change.

Second idea that if we will take any edge from the first tree there always exists some edge from the second tree, which we can swap (otherwise second graph is not connected, but the tree is always connected). So the order of adding edges from the first tree can be arbitrary.

Third idea is that if we will select leaf node in the first tree, then cut its only edge, then we can add instead of it any edge going from this vertex in the second tree.

Overall algorithm: we store linked lists of edges in vertices, when edge is in both trees we use disjoint-set union to merge vertices and join their lists. We can simply traverse first tree to get any order of edges in which the current edge will always contain leaf as one of its vertices.

Complexity is O(nα), which in practice is almost linear.

625A - Guest From the Past

Idea author: collaboration, preparation: feldsherov.

If we have at least b money then cost of one glass bottle is b - c. This means that if a ≤ b - c then we don't need to buy glass bottles, only plastic ones, and the answer will be . Otherwise we need to buy glass bottles while we can. So, if we have at least b money, then we will buy glass bottles and then spend rest of the money on plastic ones. This is simple O(1) solution.

625B - War of the Corporations

Idea author: gustokashin, preparation: thefacetakt.

Lets find leftmost occurrence of the second word in the first one. We need to add # to remove this occurrence, so where we would like to put it? Instead of the last symbol of this occurrence to remove as many others as we can. After that we will continue this operation after the new # symbol. Simplest implementation of this idea works in O(|S|·|T|), but with the power of string algorithms (for example, Knuth–Morris–Pratt algorithm) we can do it in O(|S| + |T|) time.

Hint/Bug/Feature: in Python language there is already function that does exactly what we need:

print(input().count(input()))

625C - K-special Tables

Idea author: Elena Andreeva, preparation: wilwell.

Lets fill our table row by row greedily. We want to have maximal possible number on k-th place in the first row. After it we need at least n - k numbers greater than ours, so its maximum value is n² - (n - k). If we select it then we are fixing all numbers after column k in the first row from n² - (n - k) to n². On the first k - 1 lets put smallest possible numbers 1,  2,  ... ,  k - 1. If we do the same thing in the second row then in the beginning it will have numbers from k to 2(k - 1), and from k-th position maximum possible values from n² - (n - k) - (n - k + 1) to n² - (n - k + 1). And so on we will fill all rows. With careful implementation we don't need to store whole matrix and we need only O(1) memory. Our algorithm works in O(n²) time.

625D - Finals in arithmetic

Idea author: Sender, preparation: Sender.

Lets say that input has length of n digits, then size of answer can be n if we didn't carry 1 to the left out of addition, and n - 1 otherwise. Lets fix length m of our answer and denote i-th number in the representation as a_i. Then we know from the rightmost digit of the sum. Lets figure out what does equals to. If the remainder is 9, it means that , because we can't get 19 out of the sum of two digits. Otherwise the result is defined uniquely by the fact that there was carrying 1 in the leftmost digit of the result or not. So after this we know a₁ + a_m. It doesn't matter how we divide sum by two digits, because the result will be the same. After this we can uniquely identify the fact of carrying after the first digit of the result and before the last digit. Repeating this m / 2 times we will get candidate for the answer. In the end we will have O(n) solution.

If you've missed the fact that every step is uniquely defined, then you could've wrote basically the same solution, but with dynamic programming.

625E - Frog Fights

Idea author: Elena Andreeva, preparation: iskhakovt.

We want to efficiently simulate the process from the problem statement. Lets have a data structure with times of key events that could've happened during simulation (some frog removed other frog from the board). Lets remove earliest event from our data structure and apply it to the board, make a critical jump. After that the speed of the first frog will decrease and we will be forced to recount times of collision of this frog this its 2 neighbors. This data structure could be set from C++, TreeSet from Java or self-written Segment Tree. To quickly find out who are we gonna remove from the board after the jump lets store double-linked list of all frogs sorted by their positions. Technical part is to calculate time of the collision, but it can be easily done with the simple notion of linear movement of two points on a line. There could be at max n - 1 collisions, so whole solution will be .