Results of the first round of the Russian Code Cup 2017
The Sword of Midnight by Mischeviouslittleelf
On April 2, the first qualifying round of the Russian Code Cup 2017 was held , at which attendance records for the past three years were broken. We offer you a few figures and analysis of the tasks of the round:
A. Martian Volleyball
B. Coloring the wall
C. Magic artifact
D. Memory Manager
E. FOX
4552 participants registered for the round, of which 1001 are newcomers who discovered RCC for themselves only this year. This time there were twice as many active participants as in 2015 and 2016! A total of 6586 solutions were sent to us. As usual, the most popular is C ++ in different variations (2346 solutions - C ++ 14, 1425 on the pluses of the 11th version and approximately 500 solutions from GNU C ++ 6.2 and Visual C ++ 2013). The second most popular place is Java 8.0 (649), and the third is Python (402 in Python 3.5 + 60 solutions based on PyPy 2.4.0). The most unpopular for sports programming were Perl, D and Haskell (the latter wrote exactly one solution for the whole round). A list of all the languages we support can be found here .
Following the results of the round, 200 participants passed the qualification and got into the qualifying round, which will be held on May 14. But only eight of them solved all five tasks. You can see the general results here , but we will list those five who seriously broke away from the rest of the top in terms of the accumulated penalty time:
- Evgeny Kapun, St. Petersburg
- Stanislav Ershov, St. Petersburg
- Petr Mitrichev, Zurich, Switzerland
- Makoto Soejima, Tokyo, Japan
- Maxim Finyutin, Tolyatti
We congratulate all qualified. We wish everyone else good luck in the second qualifying round, which will take place this Sunday, April 16, from 12:00 to 14:00 Moscow time.
A. Martian Volleyball
Time limit - 2 seconds
Memory limit - 256 megabytes
A volleyball match on Mars is played by two teams with up to k points, while at the same time there should be at least 2 points for winning. For each ball, one of the teams gets exactly 1 point.
For the current match, the score of the first team is x , and the score of the second team is y . What is the minimum number of balls to be played before the end of the match?
Input data
The input contains several test cases. The first line contains the number of tests t (1 ≤ t ≤ 5000).
Each test case is described in one line containing three integers separated by spaces: k , x and y (1 ≤ k ≤ 100; 0 ≤ x , y ≤ 100).
It is guaranteed that the score could be obtained with the correct unfinished game.
Output
For each test in a separate line print the answer to it - the minimum number of balls that will be played before the end of the match.
The first observation that needs to be made: to minimize the duration of the game, only the team with the highest score should receive points. Consider the condition of victory of one of the teams. It is necessary to score at least k points and overtake the losing team by at least 2 points.
The final answer is max ( k , min ( x , y ) + 2) - max ( x , y ).
B. Coloring the wall
Time limit - 2 seconds
Memory limit - 256 megabytes
Girl Masha looks at the wall in her room. The wall is lined with square tiles, but lamps have been installed in place of some tiles. Thus, one can imagine that the wall is a checkered rectangle of size n × m , in some cells of which there are lamps.
Masha has paints of k different colors. Masha wants to paint all the tiles on the wall so that on any vertical or horizontal piece of tiles, bounded at each end by the edge of the wall or lamp, the colors do not repeat. At the same time, Masha’s lamps, without a trace, will not be painted. Masha does not need to use all the colors.
Masha asks you to figure out how to paint the wall.
Input data
The input contains several test cases. The first line contains the number of tests t .
Each of the tests is described as follows: the first line of the test description contains three numbers n , m , k (1 ≤ n , m ≤ 100, 1 ≤ k ≤ max ( n , m )) - the dimensions of the wall and the number of different colors of Masha.
The following n lines contain m numbers a ij each:
- a ij = 0 if the lamp is in position ( i , j );
- a ij = 1 if the tile is in position ( i , j ).
The total number of tiles and lamps for all tests does not exceed 10 5 .
Output
For each test in a separate line, first print the answer to it:
- NO, if there is no way to paint the wall as Masha wants.
- YES, if there is a way to repaint. In this case, in the next n lines output m numbers b ij - the color of the tile at position ( i , j ) or 0, if the lamp is at this position. If there are several suitable colorings, output any of them.
To solve the problem, find out how many minimum colors are needed for the conditions to be fulfilled. To do this, we find the longest continuous segment of tiles vertically or horizontally. Let the length of this segment be L.
Then we represent the square L × L , where the first line is a sequence of numbers from 1 to L , and each next one is obtained by cyclic shift of the previous one by one to the right. We square our original rectangle with such squares, throwing away the excess and not forgetting about the lamps. For example, if L = 4, the paving will start like this:
1 2 3 4 1 2 3 4 1 2
2 3 4 1 2 3 4 1 2 3
3 4 1 2 3 4 1 2 3 4
...
This tiling will satisfy the condition of the problem, since for any horizontal and vertical segment of length L it is satisfied that all colors are different in it, which means that for smaller lengths too.
If Masha has less flowers than L , then there is no answer.
C. Magic artifact
Time limit - 2 seconds
Memory limit - 256 megabytes
Maxim is playing a computer game. It consists of n levels, which are numbered from 1 to n . They can be passed in any order, for i- th level Maxim spends a i seconds.
In addition, Maxim can find a magical artifact that will strengthen his character. There is exactly one artifact in the game, and its location is unknown for sure - on the i- th level it is with probability p i . After receiving the artifact, it becomes much easier to play - with him, Maxim passes the i- th level in b i seconds ( b i ≤ a i ). Please note that the artifact does not work at the level at which Maxim found it.
Maxim wants to complete levels in such a way as to minimize the expectation of playing time. Help him figure out what minimum expectation he can achieve by choosing a certain order of passing levels. Maxim chooses the order of levels in advance; this order should not depend on what level the artifact will be on.
The mathematical expectation of a random variable is the sum over all possible outcomes of the product of the probability of this outcome by the value of the quantity. In this case, the outcomes correspond to what level the artifact will be at, and the magnitude of the value will indicate the transit time if the artifact is on this level, and Maxim passes the levels in the chosen order.
Input data
The input contains several test cases. The first line contains one number t - the number of tests (1 ≤ t ≤ 1000).
Each of the tests is described as follows: the first line contains the number n - the number of levels (1 ≤ n ≤ 10 5 ).
The following n lines describe the levels. Each of them is given by three integers: a i , b i , x i is the time it takes for the level to pass before and after finding the artifact and the value that helps to calculate the probability of finding the artifact at that level. The probability is calculated by the formula p i = x i / 10 7 (1 ≤ b i ≤ a i ≤ 10 5 ; 0 ≤ x i ≤ 10 7 ; the sum of all x i is equal to 10 7 ).
The sum n for all tests does not exceed 5 · 10 5 .
Output
For each test, output one number - the expected time of the game with the optimal choice of the order of passing levels. The answer will be considered correct if its absolute or relative error does not exceed 10 - 6 .
Let us designate as c i the time gain that Maxim receives from the artifact at the i -th level: c i = a i - b i .
Let the levels be passed in the order 1, 2, ..., n . If the artifact was found at the i -th level, the travel time is equal to the sum of the values of b j plus c 1 + ... + c i . Then the expectation of the passage time is:
b 1 + ... + b n + p 1 · c 1 + p 2 · ( c 1 + c 2 ) + ... + p n · ( c 1 + ... + c n ).
b 1 + ... + b n does not depend on the order of the levels, so we will strive to reduce the remaining amount. If you open the brackets, you can see that it is equal to the sum c i · p k over all pairs i , k , such that i ≤ k .
Let's see how the sum changes if you swap levels of i and i + 1. Among the terms c i · p k, only c i · p i + 1 changes - it changes to c i + 1 · p i . If the order of the levels is optimal, then c i · p i + 1 ≤ c i + 1 · p i (otherwise they could be swapped and improved the answer). Let's transform this inequality:
c i / p i ≤ c i + 1 / p i + 1.
In the optimal answer for all i from 1 to n - 1, this inequality is true. Hence, in the optimal answer, the levels are sorted by c i / p i , and in order to get it, you need to sort them. Note that if p i = 0, then we can assume that c i / p i = ∞.
Sort by c i / p i must be careful. If you make a division in floating-point numbers, then in the case when c i = p i = 0, you get NaN , which will lead to an error. If we compare fractions c i / p i and c k / p k using the comparator c i · p k < c k · p i , then in the case when c i = p i = 0, the result will always be false , which will also lead to wrong sorting. Therefore, the levels with c i = p i = 0 need to be processed separately. These levels can be completed at any time: it is easy to see that they do not contribute anything to the answer, except for the fixed terms b i . They can be placed, for example, at the very end.
After sorting you need to calculate the desired expected value. It is calculated using the above formula using the prefix sums c i .
D. Memory Manager
Time limit - 3 seconds
Memory limit - 256 megabytes
Petya is actively developing his own MEM 2.0 memory manager for storage based on 7D magnetic blocks. However, he was faced with the problem of optimal delivery of data from the repository to users.
In total, the Petit Manager stores n blocks with data numbered from 1 to n , and there are q requests for issuing data from one or more of them. Requests must be processed in the order in which they arrived.
Petya has k pointers for outputting data, each of which points to one of the blocks. Initially, Peter can put pointers to any set of blocks.
Petin manager can instantly output data from any number of blocks, if at least one pointer points to each of them. If this is not the case, the manager first rearranges the pointers so that the condition is fulfilled, and then gives the data — the execution time for this i- th query is s i milliseconds, you can rearrange any number of pointers.
Petya wants to implement the pointer relocation in the manager so that the total response time to all user requests is minimal. Requests must be processed in the order in which they are received; requests cannot be interchanged. Help him.
Consider the tests given in the example.
In the first test, Petya initially can put pointers to blocks 1, 2 and 4 - after that, the first two requests will be executed instantly. Before the third request for s 3 = 1 millisecond, he can put pointers to blocks 2, 3 and 5, and before the fourth request for s 4 = 1 millisecond he can put pointers to blocks 1, 3 and 5. The total time for all requests will be s 3 + s 4 = 2 milliseconds.
In the second test, Petya is unprofitable to execute the first two queries instantly (putting pointers to blocks 1, 2 and 4 initially), because then he will have to spend 10 milliseconds to put pointers to other blocks. Therefore, the optimal strategy for Petit is to initially put pointers to blocks 1, 2 and 3, before the second request for blocks 1, 3, 4 for s 2 = 1 millisecond, and before the last request to put pointers to blocks 1, 3 and 5 for s 4 = 3 milliseconds. Total cumulative response time to requests s 2 + s 4 = 4 milliseconds.
Input data
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 numbers n , k , q - the number of blocks in the manager, the number of pointers and the number of user queries, respectively (1 ≤ k ≤ n ≤ 10 5 , 1 ≤ q ≤ 10 6 ).
The next line contains q integers s i - the time required for interchanging pointers when responding to the i- th query (1 ≤ s i ≤ 10 4 ).
The following q lines contain the description of user requests, the i- th request is described in one line, where the first number c i describes the number of data blocks the user wants to receive (1 ≤ c i ≤ k ), and the next c i numbers describe the numbers of these blocks b i , j in ascending order (1 ≤ b i , j ≤ n ).
It is guaranteed that the sum n in all tests of one input data does not exceed 10 5 , and the sum c i in all tests of one input data does not exceed 10 6 .
Output
For each test, output the answer to it - the minimum total response time to all user requests.
To begin with, for each query q i, we find go i - the minimum j , such that among q j , q j + 1, ..., q i there are at most k different numbers: this will mean that before the jth query you can put pointers that j , j + 1, ..., i requests are executed instantly. This is done in O ( sum (| q i |)), for example, by two pointers, if you go from the end of the query array.
Now we will use dynamic programming, we calculate the values dp i - the minimum time during which the first i requests can be executed. If go i = 0, then dp i = 0. If not, then it is easy to see that dp i = min j = go i .. i ( dp j - 1 + s j ) - we choose query j , before which we will change pointers, and pay the corresponding cost. Since go i does not decrease, this value can be calculated either by supporting the set values of dp j - 1 + s j , or by using the queue with the operation "minimum".
E. FOX
Time limit - 3 seconds
Memory limit - 256 megabytes
Ilya works in the Laboratory for Learning String Algorithms (LISA). Now he is trying to solve this problem.
An array of strings s 1 , s 2 , ..., s n and q queries is specified. Each query is characterized by two integers l i and r i (1 ≤ l i ≤ r i ≤ n ). To answer the request, do the following. We call a string representable if it can be obtained as follows: choose two strings s x and s y , where l i ≤ x , y ≤ r i , choose a non-empty prefix of the string s x and a non-empty suffix of the string s y , take their concatenation. The answer to the request is the number of different representable lines for the given l i and r i .
For example, let s = [ abc , ab , ac , bcac ], choose l i = 2, r i = 3. The strings are representable:
x = 2, y = 2: ab = a + b, aab = a + ab , abb = ab + b , abab = ab + ab *.
x = 2, y = 3: ac = a + c , aac = a + ac , abc = ab + c , abac = ab + ac .
x = 3, y = 2: ab = a + b , aab = a + ab , acb = ac + b , acab = ac + ab .
x = 3, y = 3: ac = a + c , aac = a + ac , acc = ac + c , acac = ac + ac .
A total of 12 different representable lines.
Help Ilya solve the problem fairly quickly.
Input data
The first line contains two integers n and q - the number of words and queries, respectively (1 ≤ n , q ≤ 10 5 ).
Each of the following n lines contains non-empty words s i consisting of lowercase Latin letters. The total length of all words does not exceed 10 5 .
The next q lines contain pairs of numbers l i , r i (1 ≤ l i ≤ r i ≤ n ) - the left and right border of the i -th query, respectively.
Output
Print q lines, the i -th of them should contain a single integer - the answer to the i- th query.
We first consider the problem for two specific lines: calculate the number of occurrences of each letter in the first line and each letter in the second line, we will not take into account the first letter in the first line and the last letter in the second line, which must be taken in any case. To get the answer, it is necessary to calculate the product of the lengths of the lines and subtract from this value the sum of cnt1 [letter] * cnt2 [letter] for all letters. Proof of the statement will be left as an exercise, such a task was proposed at the northern quarterfinal - 2015 ( http://neerc.ifmo.ru/archive/2015/northern/north-2015-statements.pdf , task C). A wide range of participants could solve it at the Cup of three quarterfinals.
For n lines, the problem is solved in a similar way: add all the lines to the prefix boron, add all the lines to the suffix boron, count the number of vertices in the first boron and in the second boron (except the root), multiply these two numbers - we can generate so many lines by applying the path in the prefix boron to the suffix boron path. Now you need to subtract the repetition, it is done in the same way: in the prefix boron, the number of each letter on the edges, except the letter on the edges of the root, is calculated, these values are multiplied, this amount is subtracted from the product of the number of vertices in the forests.
It remains to learn how to respond to requests on the segment. We will use sqrt-decomposition, we will break lines in groups on the sum of lengths. Let's greedily type lines into a group until the total length in the group is greater than the root of the sum of lengths, the last line can be quite large.
Now we use the Mo algorithm, sort the requests by the block of the left border with an equal block by the right border, then between changes of the block of the left border the right border will move only to the right. To add a line to a boron or remove it from a boron, we will recalculate the number of vertices in a subtree and, accordingly, the number of occurrences of letters in a boron.
All for the second round!
We remind you: the second round is this Sunday, from 12:00 Moscow time. At the time of writing, more than 4,600 participants have already registered, it will be interesting. Join now !
In addition, we decided to try to open in the telegram group dedicated to RCC and sports programming in general. Welcome!
')
Source: https://habr.com/ru/post/326332/
All Articles