Russian Code Cup - in the wake of the qualifying round
May 14th was the qualifying round of the Russian Code Cup 2017 . By tradition, lay out the analysis of tasks and sum up.
A. Small numbers
B. New keyboard
C. Folding figure
D. acute triangles
E. Combining arrays
F. Two subtrees
603 people participated in the round: approximately 200 best programmers from each qualifying round. According to the results of the qualifying round, we took 55 participants to the final.
All six tasks of the qualifying round could not be solved by any participant. With five tasks handled 15 people. With four - 55 more participants.
Top three:
- In the first place with a significant margin from his pursuers (15 minutes) was Ipatov Michael from Kostroma.
- Second place went to Mikhail Tikhomirov from Moscow.
- In third place - Igor Pyshkin from St. Petersburg.
In addition, the top 10 hit:
- Mitrichev Peter, Zurich, Switzerland
- Gennady Korotkevich, St. Petersburg, Russia
- Alexander Ostanin, Dolgoprudny, Russia
- Yershov Stanislav, St. Petersburg, Russia
- Djokic Nikola
- Danilyuk Alexey, Odintsovo, Russia
- Du Yuhao, Beijing, China
All participants and rating table of the round can be found here .
Congratulations to all who passed to the final, which will be held in September 2017. And now - analysis of tasks.
A. Small numbers
Time limit - 2 seconds
Memory limit - 256 megabytes
The boy Vlad has two favorite numbers a and b . Recently he was taught at school to divide and multiply, and he immediately ran to divide and multiply his favorite numbers.
First, he wrote in the notebook the numbers a and b , after which he decided that he would consistently perform one of the three operations with them:
- Divide both numbers by one of their common divisors;
- Divide a by one of its divisors g , and b multiplied by g ;
- Divide b by one of its divisors g , and a multiply by g .
After each operation, he erases the old numbers, writes the two resulting numbers back into the notebook and can continue operations with them.
Since Vlad is still small, he likes smaller numbers, so he seeks to minimize the sum of the numbers written in the notebook. He himself can not cope. Help Vlad to determine the minimum amount of numbers that can be obtained by such operations, and give an example of a pair of numbers that can be the result.
Input Format
The input contains several test cases. The first line contains the number of tests t (1 ≤ t ≤ 500).
Each test is described as follows: the single line of the test description contains two numbers a and b (1 ≤ a , b ≤ 10 9 ) - Vlad's favorite numbers.
Output format
For each test in a separate line print the answer to it - a pair with the minimum amount that can be obtained by applying the operations from the condition.
If there are several answers, then it is allowed to display any of them.
Examples
Input data
2
4 5
4 6
Output
15
2 3
First, decompose the numbers a and b into simple ones.
Now we note that if some prime number p enters the product ab to degrees higher than the first, then we can either divide both numbers by the number p at once, or if one of the numbers is not divisible by p , then we transfer the factor p from another number, then divide by p .
Obviously, the parity of the occurrence of primes in the product ab does not change in all operations. Then let's leave everything simple in the first degree. The numbers p 1 , p 2 , ..., p n remain . Let's call the product of all these primes d , d ≤ ab . It is argued that these primes cannot be greater than 14. If 1 ≤ a , b ≤ 10 9 , then the product ab ≤ 10 18 and the product of the first 15 primes exceeds 10 18 ). Now note that the final answer is a pair of numbers ( x , y ) such that xy = d . From this it follows that the second element of the pair is determined uniquely by the first. Enumerate all possible divisors d of x for O (2 n ), and choose the best pair.
B. New keyboard
Time limit - 2 seconds
Memory limit - 256 megabytes
Petya bought a new keyboard. It supports n layouts. In each layout, you can type a subset of the lowercase letters of the Latin alphabet. We number the layouts from 1 to n .
Peter wants to type some message consisting of m lowercase Latin letters. Initially, the first layout is active. Petya can perform the following actions:
- Toggle layout. Then, if the current layout had the number i , the new layout will have the number i mod n + 1, where mod is the modulo operation of the remainder. If Petya also switched the layout to the previous action, this action will take b milliseconds, otherwise this action will take a milliseconds.
- Type a character. Petya can add to the end of the current message any letter contained in the current layout. He will spend c for this action c milliseconds.
Help Petya determine the minimum time required to type a message, or find out that it is impossible to type a message. The layout, which will remain enabled after typing the message, can be any.
Input Format
The first line contains four integers n , a , b and c - the number of layouts at the keyboard, and the number of milliseconds required to complete the switch layout and character set (1 ≤ n ≤ 2 000, 1 ≤ b ≤ a ≤ 10 9 , 1 ≤ c ≤ 10 9 ).
The following n lines contain a description of the layouts. Each layout is described by a non-empty string, in which each lowercase letter of the Latin alphabet occurs no more than once - a subset of letters that can be typed in this layout. The letters in this line are sorted alphabetically.
The last line contains the string s - the message that Peter wants to type (the length of the string s is from 1 to 2,000). Line s consists of lowercase Latin letters.
Output format
Print a single integer - the minimum number of milliseconds required to type the message. Output - 1 if you cannot type a message.
Examples
Input data
5 3 2 1
abc
d
e
f
def
abcdef
Output
15
Input data
1 1 1 1
a
z
Output
-one
Use to solve the dynamic programming method. The state is d [i] [j] [k], where i is a flag denoting the type of the previous action (0 if it was a layout switch, and 1 if it was a character set), j is the number of the current layout, and k is number of characters typed. The value is the minimum time required to reach this state.
Let's go over k . For a fixed k, let's go over j from 1 to n twice. Update d [0] [j% n + 1] [k] = min (d [0] [j% n + 1] [k], min (d [0] [j] [k] + b, d [ 1] [j] [k] + a)). It is necessary to iterate j from 1 to n twice because after typing the kth character the layout can be included with a number greater than the layout in which the next character will be typed, and it will be necessary to switch layouts along the cycle to the desired one. After that, let's look at j again and update the values for k + 1. If the j- th layout contains the k- th message symbol, d [1] [j] [k + 1] = min (d [0] [j] [ k], d [1] [j] [k]) + c.
At the end, the answer is min (d [1] [j] [m]), where m = length (s) , for all j from 1 to n .
C. Folding figure
Time limit - 2 seconds
Memory limit - 256 megabytes
Petya, as always, became bored in a mathematics lesson, so he began painting the cells in his notebook. When he got tired of it, he noticed that he had got a connected checkered figure of k cells - between any two painted cells there is a path through other painted cells, and the neighboring cells in this way have a common side.
Carefully cutting it out of the notebook, he folded it in half along the line of the checkered grid (horizontally or vertically — he did not remember exactly), and also drew a copy of the folded figure in the notebook. And for good reason! Petya lost a figure, and all he had left was a copy of the folded figure, drawn in a notebook. Now he wants to restore the original figure.
It is not always possible to unequivocally restore the original figure, however, Petya decided that it would be enough for him to draw at least some figure of k cells that can be folded in half so that the folded figure he has is formed. Help him - find any initial connected figure of k cells that satisfies this condition.
Consider the second test example from the condition. In it the folded figure represents the letter “P”, and the initial figure consists of 12 cells. One of the possible variants of the original figure is shown in the figure (the fold occurs in a straight line y = 3):
Input Format
The input contains several test cases. The first line contains the number of tests t (1 ≤ t ≤ 200).
Each of the following t tests is described as follows: the first line of the test description contains two integers n , k is the number of filled cells that make up the folded Vasya figure and the number of cells in the original figure (1 ≤ n < k ≤ 10 5 ).
Each of the next n lines contains two numbers x i , y i - the coordinates of the left lower corner of the i -th filled cell (- 10 8 ≤ x i , y i ≤ 10 8 ). It is guaranteed that all painted cells are different and form a connected figure.
It is guaranteed that the sum k in all tests of one input data does not exceed 10 5 .
Output format
For each test output the answer to it. It is necessary to display a description of the shape and the way to bend it to get the shape from the input file.
In the first line print the fold line, and in the next k lines, two integers each ( x ' i , y' i ) are the coordinates of the cells of the connected figure, which can be folded in half along the derived fold line to get a figure in the input data.
The bend line should be displayed in one of 4 ways:
- L num - the fold is made in a straight line x = num , the left side is superimposed over the right;
- R num - the fold is made in a straight line x = num , the right side overlaps the left;
- U num - the fold is made in a straight line y = num , the upper part is superimposed over the lower one;
- D num - the fold is made in a straight line y = num , the lower part is superimposed over the upper one.
All x ' i , y' i , as well as the coordinate of the fold line in the module should not exceed 10 9 . It is guaranteed that such a figure exists. If there are several suitable answers, it is allowed to display any of them.
Examples
Input data
2
7 14
0 0
0 1
0 2
12
2 2
2 1
20
7 12
0 0
0 1
0 2
12
2 2
2 1
20
Output
L 0
0 0
0 1
0 2
12
20
2 1
2 2
-ten
-eleven
-12
-2 2
-3 2
-3 1
-thirty
U 3
0 0
0 1
0 2
12
2 2
2 1
20
0 3
13
2 3
0 4
2 4
Note that there are exactly four possible fold lines: two horizontally and two vertically, since the figure must lie completely on one side of the fold and also touch it.
Take any of the cells of the folded figure with the minimum coordinate along the axis OX - the cell ( x i , y i ). For the fold line we take the vertical line x = x i , touching this cell. Now, on the left, you need to restore the k - n cells of the original shape, so that after laying the left part along the bend line on the right, you get a folded figure from the input. Since k - n ≤ n (otherwise, after folding, there would be more n cells), it suffices to separate out from the folded figure k - n cells that form a connected shape containing the cell ( x i , y i ). This can be done by simply going deeper.
D. acute triangles
Time limit - 4 seconds
Memory limit - 256 megabytes
Quite recently, Moscow’s tenth-grader Dmitry Zakharov overtook everyone in building a set of points in d- dimensional space, such that all triangles with vertices at these points are acute-angled.
Tanya decided to challenge themselves with Dmitry. Of course, she plans to use a computer. For starters, she wants to solve the following problem. Given n points on the plane, you need to find the number of acute triangles with vertices at these points. A triangle is called an acute angle if all its angles are strictly less than 90 degrees.
Input Format
The input contains several test cases. The first line contains the number of tests t (1 ≤ t ≤ 666).
Each of the tests is described as follows: the first line of the test description contains the number n (3 ≤ n ≤ 2000) - the number of points.
The following n lines contain two numbers x i , y i (- 10 9 ≤ x , y ≤ 10 9 ) - the coordinates of the points. It is guaranteed that all points in one test are different.
The total number of points in all tests of some input data does not exceed 2000.
Output format
For each test in a separate line print the answer to it - the number of acute triangles with vertices at the given points.
Examples
Input data
2
five
eleven
2 2
3 3
4 1
6 4
five
0 0
3 1
5 1
5 -1
13
Output
3
four
To calculate the acute triangles, it suffices to subtract from the total number of triangles the number of rectangular and obtuse triangles. We will consider three points on one straight line as a degenerate obtuse triangle.
The total number of triangles that can be constructed with vertices at given points is C n 3 .
Note: the number of rectangular and obtuse triangles is equal to the number of right and obtuse angles with vertices at given points.
It remains to calculate the number of angles not less than 90 degrees with vertices at given points. Let's iterate over the corner point and sort by the angle relative to this all other points. We use the method of two pointers. Let's iterate over the second point that will form an angle. To count the number of suitable third points, it is sufficient to note that all points that form an angle of at least 90 degrees with two other points lie on the segment in a sorted order and that the segment is shifted only in the direction of increasing angle.
Solution run time: O (n 2 log (n)) .
E. Combining arrays
Time limit - 4 seconds
Memory limit - 256 megabytes
Consider two arrays of positive integers A = [ a 1 , a 2 , ..., a n ] and B = [ b 1 , b 2 , ..., b m ]. Let us call them k- union a lexicographically minimal array of numbers R of length k , which is split into two non-empty subsequences, the first of which is a subsequence of the array A , and the second is a subsequence of the array B.
Formally speaking, it is necessary to find a lexicographically minimal array R = [ r 1 , r 2 , ..., r k ], for which there exist non-empty sets of indices 1 ≤ i 1, 1 < i 1, 2 <... < i 1, t ≤ n and 1 < j 1, 1 < j 1, 2 <... < j 1, k - t ≤ m in the original arrays, as well as sets of indices 1 ≤ i 2, 1 < i 2, 2 <.. < i 2, t ≤ k and 1 ≤ j 2, 1 < j 2, 1 <... < j 2, k - t ≤ k , such that:
- For any 1 ≤ p ≤ t , 1 ≤ q ≤ k - t , i 2, p ≠ j 2, q ;
- For any 1 ≤ p ≤ t , we have a i 1, p = r i 1, p ;
- For any 1 ≤ p ≤ k - t , b j 1, p = r j 1, p .
For example, if A = [1, 2, 1, 3, 1, 2, 1], B = [1, 2, 3, 1], and k = 9, then their k -note will be R = [1, 1 , 1, 1, 2, 1, 2, 3, 1] (a subsequence from the first array - [1, 1, 1, 2, 1], a subsequence from the second array - [1, 2, 3, 1]).
For the two given arrays A and B , as well as the number k, find their k- union R.
Input Format
The first line of the input contains the number n - the size of the array A (1 ≤ n ≤ 3000).
The second line contains n numbers a i - array A (1 ≤ a i ≤ 3000).
The third line contains the number m - the size of the array B (1 ≤ m ≤ 3000).
The fourth line contains m numbers b i - array B (1 ≤ b i ≤ 3000).
The last line contains the number k (2 ≤ k ≤ n + m ).
Output format
Output k- union of the arrays specified in the input file.
Examples
Input data
7
1 2 1 3 1 2 1
four
1 2 3 1
9
Output
1 1 1 1 2 1 2 3 1
We present two solutions to this problem: for O (k 2 • log (k)) and O (k 2 ) .
Solution in O (k 2 • log (k))
We divide the solution of the problem into three points:
- For each array X ( A or B ) and each length 1 ≤ length ≤ | X | find minSubsequenceX [length] - a lexicographically minimal subsequence X of length length.
- We iterate over the length of the subsequence in the first array - 1 ≤ t ≤ min ( k - 1, | A |). If 1 ≤ k - t ≤ | B |, take minSubsequence A [t] and minSubsequence B [k - t] , they must be combined.
- We combine two subsequences into one, thereby obtaining a lexicographically minimal subsequence of length k , updating the answer.
To find the minSubsequence X [length] for each length , do this:
- Calculate next [i] [c] , which will store the next after i occurrence of the character c in X.
- Calculate firstSymbol [length] [i] - the first character of the lexicographically minimal subsequence of the array X [ i .. | X | - 1] length . To do this, note the following:
- If j 1 = next [i] [1] exists, then firstSymbol [1] [i] , firstSymbol [2] [i] , ... firstSymbol [| X | - j 1 ] [i] begin with 1;
- If j 2 = next [i] [2] exists, then firstSymbol [| X | - j 1 + 1] [i] , ..., firstSymbol [| X | - j 2 ] [i] begin with 2;
- ...
- If j | alphabet | = next [i] [| alphabet | exists, then firstSymbol [max (| X | - j 1 , | X | - j 2 , ..., | X | - j | alphabet | - 1 ) + 1] [i], ..., firstSymbol [| X | - j | alphabet | ] [i] start with | alphabet | .
where alphabet is the maximum possible number in the X array.
- By counting firstSymbol [length] [i] , you can restore the lexicographically minimal subsequence X for each length iteratively one letter.
This item works for O (| X | 2 ) .
Having found two lexicographically minimal subsequences S A and S B , they must be combined into one lexicographically minimum length k . We will move along the subsequences with two pointers p 1 and p 2 . If S Ap 1 ≠ S Bp 2 , then move the pointer on a smaller number. If S Ap 1 = S Bp 2 , use the binary search to find the largest common prefix S A [p 1 .. | S A |] and S B [p 2 .. | S B |] and compare the following numbers. For comparison of subracks S A and S B you can use hashes.
This item works for O ((| S A | + | S B |) • log (max (| S A |, | S B |))) = O (k • log (k)) .
Total, summing up all three points, we obtain the asymptotics O (| A | 2 + | B | 2 + k 2 • log (k)) = O (k 2 • log (k)) .
Solution for O (k 2 )
Call array A zero, and array B the first. We will build the answer on one element. We will also support the auxiliary value dp [i] [j] , where i is the array number (0 or 1), and j is the index in this array. dp [i] [j] is equal to the minimum index in the array 1 - i , from which you can continue to build the answer, if in the array i we dwell on the index j .
At the t- th of k iterations of the construction of the answer, we will find the minimal element, such that, adding it to the answer, the sequence can be completed, i.e., the remaining elements are at least k - t - 1. You also need to take into account that both subsequences of both the arrays from which the response is constructed must be non-empty.
After adding the found element v to the answer for O (| A | + | B |), we update the values of dp . For this, we will use the next array calculated in the previous solution.
F. Two subtrees
Time limit - 4 seconds
Memory limit - 256 megabytes
Consider a hanging tree. Consider a vertex v having at least one vertex in a subtree at a distance k from v . We call a k- subtree of a vertex v a tree obtained from a subtree of a vertex v by deleting all the vertices whose distance from v to v is greater than k . For example, in the illustration below, the 2-subtree of vertex 3 is marked with red.
We will call two trees the same if we can renumber the vertices of the first so as to get the second, while changing the order of the children at the vertices is not allowed. For example, the following two trees are not the same:
Given a hanging tree. It is required to determine the greatest k such that it has two identical k- subtrees whose roots are different. These subtrees may intersect.
The figure shows the trees from the examples.
In the first example, the roots of the same 1-subtrees are vertices 2 and 3.
In the second example, the roots of the same 3-subtrees are vertices 1 and 4.
In the third example, the roots of the same 0-subtrees are vertices 1 and 2.
Input Format
The first line contains the number t - the number of tests (1 ≤ t ≤ 10 4 ).
Each of t tests is described as follows: the first line contains the number n - the number of vertices (2 ≤ n ≤ 10 5 ).
Then follow n lines. In the i -th of them the number cnt i is given - the number of children of the vertex i , followed by cnt i numbers - the numbers of the children of the vertex i . Vertices are numbered from one. The root of the tree is vertex 1. It is guaranteed that the given graph is a tree with root at 1.
The sum n over all tests in the same input data does not exceed 2 · 10 5 .
Output format
For each test, print on a separate line the maximum k such that there are two identical k- subtrees with different roots.
Examples
Input data
3
five
2 2 3
14
15
0
0
eight
12
2 3 4
0
15
2 6 7
0
18
0
2
12
0
Output
one
3
0
By condition, in the k -tree, there are necessarily vertices at the depth k . Temporarily cancel this requirement.
Consider all k -trees for some k . They can be divided into equivalence classes. To each vertex we associate c k [v] with the label of the equivalence class to which its k -tree belongs.
For k = 0, all c 0 [v] are equal, since the 0-subtree of any vertex is itself.
When k = 1, c 1 [v] is equal to the number of children of the vertex.
Let's learn to build an array of c k + m [v] using arrays c k [v] and c m [v] . To begin with, we assign to each vertex v an array of arr k + m [v] , which will uniquely define the equivalence class of its k + m - subtree. Let u 1 , ..., u s be descendants of a vertex v at a distance k in the traversal order of dfs . Then we associate with the vertex v the array arr k + m [v] = c k [v], c m [u 1 ], ..., c m [u s ] . That is, k + m - a subtree of a vertex is given by a k- subtree of a vertex and m- subtrees of the lower part of a k- subtree. Below is an illustration for k = 3 and m = 1.
To get for each vertex a list of its descendants at a distance k , run a search in depth from the root. We will support the path to the root on the stack and put each vertex in an array for its ancestor at a distance k .
To convert arrays k + m [v] arrays to c k + m [v] numbers, you can hash them, use boron or unordered_map from an array to a number. The running time will be O (n) , since each vertex is found in the arr lists only once.
Having an array c k [v] , you can easily verify that there are two identical k- subtrees. To do this, we find two vertices with the same c k , and only vertices that have descendants at a distance k from it (this is the requirement that we canceled at the beginning) should be considered.
To find the maximum k , we calculate c 1 [v], c 2 [v], ..., c 2 t [v] (2 t is the maximum power of two that does not exceed n ). After that, we use the analog of binary ascents in k : we start with k = 0 and in turn try to add 2 t , 2 t - 1 , ..., 2 0 to it .
Solution run time: O (nlog (n)) .
Future plans
Do not forget that in September there will be a final round. After it we will also lay out the conditions of the tasks and their analysis. You can feel yourself in the shoes of the finalists and solve hardcore tasks.
And finally, we are sharing with you one of the ideas: maybe next year we will make special nominations like “Best in Language”. Then, for example, the owner of the best solution in C ++ will receive a separate prize. What do you think?
')
Source: https://habr.com/ru/post/329476/
All Articles