Results of the third round of the Russian Code Cup 2017
On April 29, the third and final qualifying round of the Russian Code Cup 2017 was held . By tradition, we brag a little bit of the results and lay out the analysis of tasks.
A. Spreadsheets
B. Mortal combat
C. Slightly palindromic numbers
D. Tree and polynomials
E. Beautiful report
This time 5681 people registered (473 of them are new members) - again we beat our own records. According to the results of the round, we took another 202 participants in the qualifying round. All five tasks successfully solved five people.
Top three:
- In the first place with a significant margin from the pursuers (3 minutes) was Igor Pyshkin from St. Petersburg.
- The second place was taken by user xyz2606.
- In third place with a slight lag from second place (only 6 seconds) - Shik Chen from Taiwan.
In addition, the top 10 hit:
- Oleg Merkuryev, Yekaterinburg, Russia
- Ivan Smirnov, Moscow, Russia
- Alexander Ostanin, Moscow, Russia
- Dmitry Yakutov, St. Petersburg, Russia
- Maleki Mohammadreza, Tehran, Iran
- Kohji Liu, Tokyo, Japan
- Konstantin Khadaev, Novosibirsk, Russia
Congratulations to all who passed in the qualifying round, which is waiting for us on May 14. And now - analysis of tasks.
A. Spreadsheets
Time limit - 1 second
Memory limit - 256 megabytes
Petya is developing his own spreadsheet editor. In its editor, the columns will be called as follows: the first 26 columns - the corresponding letters of the Latin alphabet: A, B, C, ..., Z. The following columns, starting from 27, are called pairs of letters: AA, AB, ..., AZ , BA, BB, ..., BZ, ..., ZZ. Further three letters are used: AAA, AAB, AAC, ..., then fours, and so on.
Now Petya needs to determine his name by the column number. Help him write the appropriate code snippet.
Input Format
The input contains several test cases. The first line contains an integer t - the number of tests (1 ≤ t ≤ 1000).
The following t lines contain one integer k each (1 ≤ k ≤ 10 9 ).
Output format
For each test, print the name of the k- th column in a separate line.
Examples
Input data
four
one
ten
100
1000
Output
A
J
CV
ALL
We subtract from k the unit by going to the numbering of the columns with 0. We first find out how many characters are in the name of the column. To this end, we will successively subtract from k the degrees of the number 26 until the next power is greater than the remaining number k '.
Now, to get the column name, it suffices to translate k 'into the 26th number system with numbers A – Z and add leading zeros (more precisely, A characters) to the required number of characters. This can be done using standard programming language methods (although this will result in digits 0–9, A – P, they will have to be replaced) or by independently implementing an algorithm for transferring to a number system with a given base.
B. Mortal combat
Time limit - 1 second
Memory limit - 256 megabytes
Recently Vasya started playing a new computer game. At the end of the first level, the boss was waiting for him, whom he needed to win in order to continue to pass the game. Vasya has a squad of n characters, the i- th of whom has h i health units and a i attack units. The boss has H units of health and A units of attack.
The battle takes place as follows:
- If Vasya no longer has characters, he lost;
- Otherwise, he chooses one of them and fights against the boss;
- Let Vasya choose character number i . Then:
- The character attacks the boss and shoots him a i health units;
- If the boss is still alive, that is, his number of health units is positive, he attacks in response and removes character A health units;
- As long as both the character and the boss are both alive, the actions are repeated.
- If the boss is dead, the battle ends, Vasya wins. Otherwise, all actions are repeated.
- Since Vasya has yet to complete the following levels, he wants to lose as few characters as possible. Help him - find the minimum possible number of characters that he can lose in a battle with the boss. If Vasya does not win even using all the characters, output - 1.
Consider test examples.
In the first example, Vasya can first send a character 2 to fight, which will strike three times, reduce the number of health units of the boss by 12, and then die, and then send the character 3, who will immediately remove 6 health points from the boss and kill him . Thus, Vasya will lose only one character.
In the second example, even if Vasya sends all the characters one by one, the boss will not be killed.
Input Format
The input contains several test cases. The first line contains the number of tests t (1 ≤ t ≤ 1000).
Each of the following t tests is described as follows: the first line of the test description contains three integers n, H, A - the number of characters for Vasya, the number of health units and attacks for the boss, respectively (1 ≤ n ≤ 10 5 , 1 ≤ H, A ≤ 10 9 ).
Each of the next n lines contains two integers h i , a i - the number of health and attack units in the i- th character, respectively (1 ≤ h i , a i ≤ 10 9 ).
It is guaranteed that the sum n in all tests of one input data does not exceed 10 5 .
Output format
For each test, output the answer to it - the minimum number of characters Vasya can lose to defeat the boss, or - 1 if he loses the battle in any case.
Examples
Input data
2
4 18 4
4 5
9 4
sixteen
3 3
4 27 4
4 5
9 4
sixteen
3 3
Output
one
-one
Let us calculate the number of health units that the i- th character can take to the boss alone before his death: p i = a i • ⌈ h i / A ⌉. After that, we sort the characters in descending order of p i and send them to the boss one by one in this order until he is killed.
C. Slightly palindromic numbers
Time limit - 1 second
Memory limit - 256 megabytes
An integer will be called slightly palindrome if the first digit of its decimal notation without leading zeros coincides with the last. Your task is to count the number of slightly palindromic numbers on the segment from l to r , inclusive.
In the first test case, slightly palindromic numbers - 8, 9, 11 and 22.
In the second - 1251 and 1261.
Input Format
The input contains several tests. The first line contains the number t - the number of tests (1 ≤ t ≤ 5 · 10 4 ).
Each test is given in one line, which contains the integers l and r (1 ≤ l ≤ r ≤ 10 18 ).
Output format
For each test, print on a separate line the number of slightly palindromic numbers on a given segment.
Examples
Input data
3
8 25
1251 1266
12 21
Output
four
2
0
We will learn to count the number of slightly palindromic numbers among the first n natural numbers. To get the number of such numbers on the segment from l to r , you need to count their number among the first r and l - 1 natural numbers and subtract one from the other.
All numbers from 1 to 9 are slightly palindromic, so if n ≤ 9, then the answer is n . Otherwise, add 9 to the answer and calculate the number of slightly palindromic numbers on the interval from 10 to n . Consider the ten numbers from 10 k to 10 k + 9, where k ≠ 0. Among them, exactly one slightly palindromic, since the last digit should be equal to the first digit k . Thus, there is one slightly palindromic number on the segments from 10 to 19, from 20 to 29, etc.
Let n = 10 k + d , where 0 ≤ d ≤ 9. Then on the interval from 10 to n there are k slightly palindromic numbers, if d is not less than the first digit of k (and it is equal to the first digit of n ), and k - 1, if less.
D. Tree and polynomials
Time limit - 2 seconds
Memory limit - 256 megabytes
Nick is a freshman. On a course of algorithms, he studies trees. On the algebra course, Nick studies polynomials. Nick also loves what he sees. Recently, he came up with a problem, but can not solve it. Help him.
Given a hanging tree with n vertices numbered from 1 to n . Initially, the number 0 is written in each vertex of the tree. For the vertex v, we denote by d [ v ] the depth of the vertex v - the number of vertices on the path from the root of the tree to the vertex v , in particular, the root has a depth of 1.
Given the number k . Required to handle requests of two kinds.
- Given the vertex v and the polynomial q ( t ) = q 0 + q 1 t + q 2 t 2 + ... + qkt k . For each vertex u in the subtree of the vertex v, it is necessary to add the value q ( d [ u ]) to the value at this vertex.
- Given the vertex v and the polynomial q ( t ) = q 0 + q 1 t + q 2 t 2 + ... + qkt k . For each vertex u on the path from the root to the vertex v , inclusive, it is required to add the value q ( d [ u ]) to the value at this vertex.
All actions are performed modulo 10 9 + 7.
Help Nick understand what numbers will be written in the tree tops after performing all the operations.
Input Format
The input contains several tests. The first line contains the number t - the number of tests (1 ≤ t ≤ 10 5 ).
The following is a description of the tests. The test description starts with the number n - the number of vertices in the tree, and the number k - the maximum degree of polynomials (1 ≤ n ≤ 10 5 , 1 ≤ k ≤ 20).
This is followed by n numbers p 1 , p 2 , ..., p n , the number p i specifies the parent number of the vertex i , or is 0 if the vertex i is a root. It is guaranteed that the numbers p i define the correct hanging tree.
The next line contains the number q - the number of queries (1 ≤ q ≤ 10 5 ). The next q lines contain queries, the query description consists of the number t equal to 1 or 2 - the type of the query, followed by the number v - the number of the vertex, and then k + 1 integer q 0 , q 1 , ..., q k - polynomial coefficients (0 ≤ q i <10 9 + 7).
It is guaranteed that the sum of the values of n in all tests of one input data does not exceed 10 5 . Also, the sum of q values in all tests of one input data does not exceed 10 5 .
Output format
For each test, output n numbers, for each vertex, print the number that will appear in it after all the requests have been completed. Once again we recall that all calculations are carried out modulo 10 9 + 7.
Examples
Input data
one
4 2
2 4 2 0
3
1 2 0 1 0
2 3 1 0 0
2 1 0 0 1
Output
12 7 4 2
We formulate the key ideas of the solution. First, we note that the problem can be solved independently for two types of queries, since the operations are independent of the values at the vertices.
Secondly, instead of storing numbers at the vertices, we will store the sum of all polynomials, the results of which were applied to the values at the vertices. Then at the end, simply calculate the value of the polynomial at each vertex from its depth and obtain the value at the vertex.
However, we cannot execute queries explicitly, considering all the vertices appearing in the query and adding the polynomials from the query to the polynomials stored in them: such a solution will work in O ( n 2 • k ) and will not meet the time constraints. Therefore, we use the idea of deferred operations.
In queries of the first type, you need to add the polynomial q (x) to each vertex of the subtree v . To do this, just leave a note that it needs to be done: we will store the push1 [v] polynomial at the vertex v , and when we perform the first type of query, we add the q polynomial to the push1 [v] polynomial. Similarly, for requests of the second type, we will use the push2 [v] polynomial, which for each vertex will store the sum of polynomials from the second type of queries to this vertex.
Let now sum1 [u] be the sum of all polynomials that should have been taken into account at the top of u in queries of the first type. To calculate sum1 [u], perform a deep search from the root of the tree, which will support the polynomial cur , add the value push1 [v] to it when you visit the new vertex v and subtract it back when you exit it. Accordingly, being at the vertex u , we assign sum1 [u] = cur .
In the same way, let’s denote by sum2 [u] the sum of all polynomials that should have been taken into account at vertex u in queries of the second type. To calculate sum2 [u], we also use depth traversal. The value of sum2 [u] is equal to the sum of the values of sum2 [v] for children u and the values push2 [u] .
Having received polynomials sum1 [u] and sum2 [u] at each vertex, we calculate their value from d [u] and add, the result will be the answer. Solution time is O (nk) .
E. Beautiful report
Time limit - 5 seconds
Memory limit - 256 megabytes
Andrey is engaged in the analysis of the subscription graph in one social network. This graph is oriented: if user a is subscribed to user b , then user b is not necessarily subscribed to user a .
The manager Andrei asked him to calculate for each user x how many user y exist, such that from user x you can get in the subscription column to user y .
Typing the exact value does not make sense, because it looks ugly and instantly out of date, therefore, you are only interested in approximate value. Perform the task manager and find these values with an error no more than twice.
Input Format
The first line contains integers n and m (1 ≤ n , m ≤ 200 000) - the number of users of the social network and the number of situations when one user is subscribed to another.
Further, in m lines there is a description of the graph, the i -th of these lines contains two integers a i and b i (1 ≤ a i , b i ≤ n , a i b i ) and means that user a i is subscribed to user b i . Each ordered pair ( a i , b i ) occurs in the input data no more than once.
Output format
Print n integers q i - the estimate for the number of users y , such that you can get from user i in the subscription column to user y . If the present number of such pairs is z i , the inequalities q i ≤ 2 z i and z i ≤ 2 q i must be satisfied. In addition, it is permissible for no more than 10 users to output q i that does not satisfy the specified restrictions.
Note: The jury uses the exact number of users sought to check your answers. In this case, the jury does not guarantee that the exact number can be found within the limits of time and memory, and recommends using the opportunity to derive an approximate value.
In the example from user 1 you can reach all five users. However, the shown answer 7 is also admissible, since it differs from 5 no more than twice. Similarly, answer 2 for user 4 is valid.
Examples
Input data
5 6
12
13
2 4
2 5
3 5
4 2
Output
7
3
2
2
one
Before solving the main task, we solve the following problem, which is weakly connected with the original one: the input is a sequence of elements ( a 1 , a 2 , ..., a n ), and the number of different elements in the sequence must be calculated. The peculiarity of this task:
- The elements can be read only sequentially and only once: after reading the element a i there will be reading a i + 1, it is impossible to return to a i .
- You cannot use more O (1) additional memory.
To approach the solution of this subtask, recall that the expectation of the minimum of random variables uniformly distributed on the interval [0; 1] is 1 / ( m + 1). For example, if you take four random numbers from the interval [0; 1], then the minimum of these numbers will be on average 0.2.
Take the hash function h : A → [0; 1], mapping the elements a i to numbers on the interval [0; 1]. Calculate the value M = min {h (a 1 ), h (a 2 ), ..., h (a n )} . As a response to the problem, let us return 1 / M - 1. The problem with this solution: we may not be lucky — for example, h (a i ) will be very small, which will significantly affect the answer. To smooth this problem, we repeat the described process several times for different hash functions h 1 , h 2 , ..., h k for some fixed k and average the results obtained.
Let us return to our task of finding the number of reachable vertices. We first consider the case of an acyclic graph. It differs from the graph with cycles, including the fact that it has topological sorting: such a sequence of vertices, in which the edges of the graph go only from the vertices that are in a later order, to the vertices that are in the earlier order. Topological sorting will allow to calculate for the graph in which at each vertex a random number from the segment [0; 1] is written, which minimum number is reachable from each vertex. This can be done with the help of dynamic programming: viewing the vertices in the order of topological sorting will allow you to calculate the value for the current vertex based on those already found reachable from it. Considering the minimum attainable number M i from each vertex, you can specify the answer for this vertex 1 / M i - 1. The described need to be repeated several times and the results averaged.
However, in this problem there can be cycles in the graph. To solve this problem, we construct a condensation graph. In the obtained acyclic graph, in each vertex there are actually several vertices of the initial graph. For all these vertices the answer will be the same. The difference in calculating the answer will be that the vertex is written not a random number from [0; 1], but a minimum of wi random numbers from [0; 1], where w i is the number of vertices of the initial graph contained in the i top of the condensed.
A curious reader can learn more about the method of solving this and some other similar problems in the article “Size-Estimation Framework with Applications for Transitive Closure and Reachability” available here .
Qualifying round soon
We remind you: the qualifying stage will be held on May 14 from 1:00 pm to 3:00 pm Moscow time. Slightly more than 600 participants will take part in the round, and only 50 of the best will reach the final, which will be held on September 10.
Now, thanks to the official championship chat, you can ask your question directly to the organizers. And also to ask for advice, share suggestions on solving problems, talk on various topics related to sports programming. They will help you with fresh ideas and kind words.
')
Source: https://habr.com/ru/post/327592/
All Articles