ifsmirnov's blog

By ifsmirnov, history, 19 months ago, translation, In English,

667A - Pouring Rain

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.

667B - Coat of Anticubism

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 dp2, 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 dpk[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.

666C - Codeword

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 p1, ..., p|s|. No character sk + 1 may occur between pk and pk + 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 pi, 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 |xi - xj| or |yi - yj|. This is the set from where d will be chosen.

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

  1. 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 (x0, y0), than x0 must be some of xi, xi + d, xi - d, similarly for y0. Add all this values to the set.
  2. 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.

666E - Forensic Examination

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.

 
 
 
 
  • Vote: I like it  
  • +68
  • Vote: I do not like it  

»
19 months ago, # |
  Vote: I like it +69 Vote: I do not like it

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

»
19 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
19 months ago, # |
  Vote: I like it -32 Vote: I do not like it

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.

There are two points that move by perpendicular lines. So, at the point of intersection of these lines is the pinnacle of a square. Lower left to each coordinate point or coincides with it, or differs by d. The point of intersection lines has coordinates (xi, yj), then the lower left - (xi ± d, yj ± d) for some i and j. Add all the coordinates xi, xi + d, xi - d in fingering set.
All the points are moving along parallel lines. We assume that on the horizontal; vertical case is similar. Let's brute over again and move the permutation of each point so that after his motion coincide with the lower left vertex of the square. The second point should be shifted by the vector (- d, 0), the third - to (0, - d), the fourth - on (- d, - d). Thereafter, four points must be on the same line. Now the problem can be reformulated as follows: there are four points on a line, you need to move them to a single point so as to minimize the maximum shift. It is easy to see that the need to move into the middle of the resulting segment, ie the point (maxX - minX) / 2 (because of the requirement integer response can be rounded to either side). After going through all the permutations, we obtain another set in which it is necessary to sort out the coordinate of the first point of the desired square.

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.

»
19 months ago, # |
  Vote: I like it +32 Vote: I do not like it

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.

»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Div. 1 E:

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 ti. 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.

I'm sorry, but it is very hard for me to express the solution. Please, refer to my code if something is unclear. #rpw2E8

»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I'm so sorry but you forgot to update E

»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    NVM. I got it.

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain it?

      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like 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.

        • »
          »
          »
          »
          »
          18 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Got that! Thank you :)

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          hey . i am trying to solve this problem but what i don't understand in your comment is "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." is this the reason that we maintain highest and second highest distances ?Can you explain this thing ?

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please elaborate problem C ?

»
10 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.