To know how much water you consume per second you should divide consumed volume, *v*, by the area of the cup, . Then you should compare thisit with *e*. If your speed of drinking is greater, then you'll drink all the water in seconds. Otherwise you would never do it.

It is possible to make a convex polygon with given side lengths if and only if a generalized triangle inequality holds: the length of the longest side is less than the sum of lengths of other sides. It is impossible to make a convex polygon from a given set, so there is a side which is longest than (or equals to) than sum of others. Assume it is greater by *k*; then it is sufficient to add a rod of length *k* + 1. More, it is clear that adding any shorter length wouldn't satisfy the inequality. Thus the answer for the problem is .

666A - Reberland Linguistics / 667C - Reberland Linguistics

This problem is solved with dynamic programming. We can select an arbitrary root of any length (at least five). Let's reverse the string. A boolean value *dp*_{2, 3}[*n*] denotes if we could split a prefix of length *n* to a strings of length 2 and 3 so that the last string has a corresponding length. Transitions: . Similarly, . If any of *dp*_{k}[*n*] is true we add the corresponding string to the set of answers.

666B - World Tour / 667D - World Tour

You are given the oriented graph, find four distinct vertices *a*, *b*, *c*, *d* such that each vertex if reachable from previous and the sum of shortest paths between consequitive vertices is as large as possible. First let's run a BFS from each vertex and find three most distant vertices over given graph and its reverse. Afterwards loop through each possible *b* and *c*. Having them fixed, loop through *a* among three most distant vertices from *b* in the reversed graph and through *d* among three most distant vertices from *c* in tie initial graph. This is sufficient, because if we've fixed *b* and *c* and *d* is not one of three furthest from *c* then we could replace it with one of them and improve the answer.

The first thing to notice: string itself does not matter, only its length does. In each sequence of length *n* containing a fixed subsequence *s* we can select *s*'s lexicographically minimal occurance, let it be *p*_{1}, ..., *p*_{|s|}. No character *s*_{k + 1} may occur between *p*_{k} and *p*_{k + 1} - 1, because otherwise the occurence is not lex-min. On the other hand, if there is an occurence which satsfies this criterion than it is lex-min.

Given this definition we can count number of strings containing given string as a subsequence. At first select positions of the lex-min occurance; there are ways to do it. Next, you can use any of Σ - 1 characters at first *s* intervals between *p*_{i}, and any of Σ at the end of the string. (Here, Σ denotes alphabet size).

Looping through *p*_{}|*s*| — the position of last character in *s* in the lex-min occurence, we can count that there are exactly strings containing *s* as a subsequence. So, having |*s*| fixed, answer for each *n* could be computed in linear time.

A final detail: input strings can have at most different lengths. Thus simply applying the overmentioned formula we get a solution, which was the expected one.

666D - Chain Reaction / 667E - Chain Reaction

You are given four points on the plain. You should move each of them up, down, left, or right, such that the new configuration is a square with positive integer sides parallel to coordinate axes.

Choose some *d*, length of the square side, and (*x*, *y*), the position of the bottom-left point. A set from where to choose will be constructed later. Then fix one of 24 permutations of initial points: first goes to the bottom-left point of the square, second goes to the bottom-right, etc. Having it fixed it is easy to check if this configuration is valid and relax the answer if needed. The only question is where to look for *d*, *x* and *y*.

First we deal with *d*. You can see that there are always two points which move among parallel but not the same lines. In this case *d* is the distance between these lines, i.e. one of |*x*_{i} - *x*_{j}| or |*y*_{i} - *y*_{j}|. This is the set from where *d* will be chosen.

Now fix *d* from the overmentioned set and look at two cases.

- There are two points moving by perpendicular lines. Then there is a square vertex in the point of these lines intersection. In each coordinate this point either equals to bottom-left point of the square or differs by exactly
*d*. Thus if bottom-left point has coordinates (*x*_{0},*y*_{0}), than*x*_{0}must be some of*x*_{i},*x*_{i}+*d*,*x*_{i}-*d*, similarly for*y*_{0}. Add all this values to the set. - All points are moving among parallel lines; WLOG horisontal. Let's fix a permutation of points (yes, once again) and shift each point in such a way that after moving it would equal the bottom-left vertex of the square. Second point should be shifted by ( -
*d*, 0), third by (0, -*d*), fourth by ( -*d*, -*d*). All four points must be on the same line now; otherwise this case is not possible with this permutation. Now the problem is: given four points on a line, move it to the same point minimizing the maximal path. Clearly, one should move points to the position (*maxX*-*minX*) / 2; rounding is irrelevant because of the constraint of integer answer. So, having looked through each permutations, we have another set for bottom-left vertex possible coordinates.

By the way, the 10th test (and the first test after pretests) was case 2; it was intentionally not included in pretests.

Why does it work fast? Let *D* and *X* be the sizes of corresponding lookup sets. . Now for each *d* there are 4·3 = 12 coordinates in the first case and no more than 4! = 24 in the second. Thus *X* ≤ 12·(12 + 24) = 432. The main part works in ; however, it is impossible to build a test where all permutations in the second case give a valid position, so you can reduce this number. Actually, the model solution solves 50 testcases in 10ms without any kind of pruning.

You are given string s and m strings ti. Queries of type ``find the string ti with number from [l;r] which has the largest amount of occurrences of substring s[a, b]'' approaching. Let's build segment tree over the texts t_i. In each vertex of segment tree let's build suffix automaton for the concatenation of texts from corresponding segment with delimeters like a#b. Also for each state in this automaton we should found the number of text in which this state state occurs most over all texts from the segment. Also for each state v in this automaton we should find such states in children of current segment tree vertex that include the set of string from v. If you maintain only such states that do not contain strings like a#b, it is obvious that either wanted state exists or there is no occurrences of strings from v in the texts from child's segment at all. Thus, to answer the query, firstly we find in root vertex the state containing string *s*[*a*;*b*], and after this we go down the segment tree keeping the correct state via links calculated from the previous state.

Please refer to the code if something is unclear.

Can you write a editorials in English?thanks...

It seems that we should start to learn Russian. I hope it will not be so difficult :D Thanks for the editorial.

It might be TooDifficult !

English Editorial

667A — Heavy rain

To find out how much water you consume per second, you have to divide the amount drunk per second v on the bottom area equal. Next, you should compare this value with e. If your speed is higher, then you empty the cup in seconds. Otherwise you will not be able to empty it.

667B — Coat antikubizmu

To set of lengths can be folded convex polygon should be performed generalized triangle inequality longest side length must be less than the sum of the lengths of the remaining sides. Once the current set of lengths of folded convex polygon is not possible, there is a party, the length of which is not less than the amount remaining. Let it more than this amount on k; then add enough rod length k + 1. In addition, it is clear that no lesser length can not be dispensed. Thus, the answer to the problem -.

666A — Reblyandskaya linguistics / 667C — Reblyandskaya linguistics

The solution — dynamic programming. We can take any large root. Therefore, we develop and support dp2 line, 3 [n] — if we can break the prefix of length n on the length of the lines 2 and 3 so that the latter was a line of a certain length. Conversion:. Similarly. If dpk [n] = 1, add the appropriate line in the set of answers.

666B — World Tour / 667D — World Tour

Given a directed graph, you need to find these 4 different vertices a, b, c, d, that each successive reachable from the previous one and the sum of the shortest paths between adjacent peaks greatest. To solve this problem for each node using the bypass wide calculate distances to all the other vertices on the forward and reverse edges and keep the three most remote peaks. Then Let's brute over the top of b, c, and a and d will search only among the three most distant edges on the reverse for b, and three at the farthest edges straight for c. This will be enough, because if we have fixed the vertices a and b, then if we d is not the most distant of the three for c, we can exactly replace it with one of them and to improve the response.

666C — Codeword

The first useful observation is irrelevant string s itself for us, but only its length. Any sequence of length n that contains a predetermined subsequence of s, it is possible to allocate minimum occurrence lexicographically. It is especially the fact that between symbols ak and ak + 1 can not meet the symbol ak + 1, otherwise not entering lexicographically minimal. Conversely, if an occurrence with this property, it will be the lexicographically minimal.

Based on this, it is possible to count the number of lines containing this subsequence like. First, we will select the item tokens. min. joining means. Further, in any of | s | segments, we can only use q — 1 characters, where q — the size of the alphabet, and can take any word in the last leg. In other words, the free symbols on the left of the last occurrence we choose the alphabet size q — 1, and the right — size q.

Looking over the last character position in Lex. min. entering, we see that these lines. Thus, if we fixed | s |, we can easily calculate the desired response for all n. Moreover, here you can bring a more simple recurrent formula: dn let us know the answer to length n. Then. Indeed, either the last character does not coincide with the last position in the Lex. min. entry and we will go for the first term, or coincide, then we can clearly count the number of nadposledovatelnostey that is equal to the number in the second term.

The final touch: note that different lengths among the input lines can only be, then deciding on the forehead by this formula, we obtain a solution for.

666D — Chain Reaction / 667E — Chain Reaction

In task given four points in the plane. Required to move each of them up, down, left or right to get a square with sides parallel to the coordinate axes. It is necessary to minimize the maximum distance that the point will be shifted.

Brute over a square side length of d, the position of the lower left point (x, y) (among which to sort, it will be seen later). In addition, Let's brute over permutation points so that the first moved to the lower left point of the square, the second — in the lower right, etc. After that is easy to check whether a permutation of the points you can get such a square, and if so, to calculate the maximum displacement. The question remains, where to touch d, x and y.

First, we define the d. It is easy to notice that there are always two points of a square, moving in parallel but not coincident straight. In this case, Stron square — is the distance between the lines, that is one of the numbers | xi — xj | or | yi — yj |. It is set in which will move d.

To understand where to sort the x and y, Let's brute over d of the above-constructed sets and consider two cases.

How much does it work? Denote respective sets of dimensions D and X. Then, D = C42 · 2 = 12. Now each d is generated in the first case 4 x 3 = 12 coordinates in the second — not more than 4! = 24. Total X ≤ 12 · (12 + 24) = 432. The main part of the solution works for; but it is impossible to construct a test, which implemented all possible configurations with the movement on parallel lines, so really have to sort through a lot less.

666E — Forensics

Given a string s, as well as m lines ti. There have been questions like `` count in any of the rows with numbers from the interval [l; r] substring s [a, b] is the most common ''. Generally speaking, it was assumed that the task will require online-solutions, but in the end the idea was abandoned, so it may be technically a combination of well-known algorithms. We will not detail disassemble offline-solution, and immediately move on to online.

We construct a tree of segments on the texts. At each vertex of the tree we construct a machine for the concatenation of texts through separators that have the appropriate number of top subsegment and for each state in this machine will find a number of text from the subsegment in which it is found the greatest number of times, and the number of entries in this position. Furthermore, for each state condition in children find tree tops of segments that contain it (if any). Obviously, all the substrings of one state will be in the same state in the left half. In the right half of the same, in general, the lines that crossed the middle of the text segment can go into a different state or disappear, but it does not matter. To cope with this problem, simply look no condition for the rows that are in the same state, but a state for lines that do not meet the separator and which are in this state, since all the lines that cross the middle are of the form X # Y and are not interested in us. So, to answer the query, we can find at the root node state corresponding to the required substring, and further down the tree, moving in already counted transitions for states.

Friends, I'm terribly sorry for delaying English editorial for several days. Travelling to Ural Championship onsite consumed almost but all my time. Even now I'm writing these line sitting in the intercity train :) Anyway, here it is, all but problem Div1E by now.

Never mind. Thanks again, and good luck (Y)

Div. 1 E:

You are given string

sandmstringst_{i}. Queries of type ``find the stringt_{i}with number from [l;r] which has the largest amount of occurrences of substrings[a,b]'' approaching.Let's build segment tree over the texts

t_{i}. In each vertex of segment tree let's build suffix automaton for the concatenation of texts from corresponding segment with delimeters like a#b. Also for each state in this automaton we should found the number of text in which this state state occurs most over all texts from the segment. Also for each statevin this automaton we should find such states in children of current segment tree vertex that include the set of string fromv. If you maintain only such states that do not contain strings like a#b, it is obvious that either wanted state exists or there is no occurrences of strings fromvin the texts from child's segment at all. Thus, to answer the query, firstly we find in root vertex the state containing strings[a;b], and after this we go down the segment tree keeping the correct state via links calculated from the previous state.I'm sorry, but it is very hard for me to express the solution. Please, refer to my code if something is unclear. #rpw2E8

What does "a#b" means?

Should I add '#' at the end of each string?

I'm so sorry but you forgot to update E

Hello editorialist, could you please be clearer with the editorial "World tour"?

Can someone explain World Tour (Div2 D / Div1 B)? Thanks!

NVM. I got it.

Can you please explain it?

World Tour (Div2 D / Div1 B) :

Let us say our final answer is: W X Y Z (Each city has to be distinct). i.e. d(W,X) + d(X,Y) + f(Y,Z) is maximum.

We will take all possible pairs of cities for X and Y, (X != Y).

For some X = x1 and Y = y1, we want to choose W, Z such that d(W,X) + d(X,Y) + f(Y,Z) is maximum.

If we choose some W = a such that d(a,x1) is maximum for a belong to [1,n] (a != x1 && a!= x2), then we have to choose some Z = b such that b belong to [1,n] (b!= a && b!= x1 && b != y1).

But we also have to keep in mind that a could have been a possibility for Z too. so we need to check that too.

We can keep maximum 3 cities and their distances, from and to both, to find W and Z.

Got that! Thank you :)

Can anyone please elaborate problem C ?

Click

I'm having trouble understanding the DP solution in 667C (Reberland Linguistics). Firstly, i am not able to comprehend that "How could I think in direction of reversing the string? (How could we know, that doing this would make it a DP problem?)". Also, i have tried implementing the method using pen paper, but still the intuition and approach towards the problem remains unknown to me.