Analysis of the tasks of the Technocub final 2016

    Company Mail.Ru Group in conjunction with MIPT and MSTU. N.E. Bauman summed up the results of the Technocub - the first programming olympiad for students in grades 8–11. Pupils from more than 20 cities of Russia and the CIS fought for the title of the most talented young programmer. In total, 2132 participants registered for the Olympiad, 113 came to the full-time final, which took place simultaneously at two venues: at MSTU. N. E. Bauman and MIPT. The award was held at the office of Mail.Ru Group. The Olympics were held on the Codeforces platform .



    The guys had three hours to solve seven problems, which were teachers and specialists from leading technical universities in Russia. The last, the most difficult, was decided only by one of the participants - Vladislav Makeev, who eventually took first place. In total, 27 participants of the Olympiad became winners, they divided diplomas of I, II and III degrees among themselves. Winners (diploma of I degree) received an additional eight points for admission, holders of diplomas of II and III degree - six points each. The first place was taken by Vladislav Makeev (Moscow, 11th grade), the second - Alexandra Drozdova (Nizhny Novgorod, 10th grade), the third - Grigory Reznikov (Moscow, 11th grade). The full list of winners is available here . In this post, we suggest that you familiarize yourself with the objectives of the finale and their solutions.





    Problem A. Level 80 Programmer


    The author of the idea: Mikhail Mirzayanov, SSU
    Development: Alexander Frolov, SSU
    Topic: modeling

    Condition


    Vasily dreams of becoming a k -level programmer . He has n days to carry out his plan - to increase his level from the 1st to the kth . To go from level x to level x + 1, you must solve x problems from the moment you receive level x . On the i- th day, a i tasks are published on one well-known site , and all of them are available for solving only on the day of publication. Every day, Vasily solves problems sequentially, one after another, while on the i- th day he can solve no more than a i

    tasks. As soon as the total number of tasks solved by Vasily from the moment of receiving the last level x becomes equal to x , he stops and does not solve more problems that day. In this case, at the end of the day he makes the transition to the next level x + 1. At the same time, he will never solve the problems that Vasily did not manage to solve that day.

    Solved problems do not accumulate when moving to the next level, that is, for each x to go to level x + 1, Vasily needs to solve x problems, namely as a level x programmer .

    Vasily can start classes any day from 1 to n, while he wants to minimize the difference between the day number when he becomes a k- th level programmer and the day he starts training.



    Input

    The first line of the input contains two integers n and k (1 ≤ n ≤ 500, 2 ≤ kn + 1) - the total number of days and the level that Vasily wants to achieve, respectively.

    The second line contains n integers a 1 , a 2 , ..., a n (1 ≤ a i ≤ 500), where a iequal to the number of tasks available for solving on the i- th day.

    Output

    Print a single integer - the minimum number of days during which Vasily will be able to reach the k- th level of programming.

    If Vasily fails to achieve the desired, print -1.

    Parsing


    To begin with, we note that in the process of solving problems it is never profitable to take breaks, since the surplus of tasks remaining on any day can simply not be used.

    Thus, the only thing that makes sense to change is the day the pumping starts. Let’s go through all the possible options for the first day and for each we simulate the programmer’s buildup process. The complexity of this solution is O (n 2 ) , since the possible options for starting day n and for each day are simulated in O (n) time .

    Task B. Replacing Letters


    Authors of the idea: Gleb Evstropov, HSE, and Mikhail Mirzayanov, SSU
    Development: Alexander Frolov, SSU
    Topics: Hamming distance, counting

    Condition


    Ivan loves to read newspapers, he is especially interested in political news and sports news. Also, Ivan has a favorite string s .

    Ivan has a lot of free time, and he reads very quickly, but there are not so many newspapers that are of interest to him in a day. Therefore, recently, after reading another newspaper, Ivan began to consider the number of occurrences of his favorite string s in the text t written in the newspaper as a substring. A substring of string x is a sequence of consecutive characters of string x .

    But soon Ivan began to cope very quickly with the count of occurrences, and he decided, after reading the next newspaper, to replace in his favorite line no more than kcharacters in such a way as to maximize the number of occurrences of the changed string s in the newspaper text t .

    Your task is to help Ivan and calculate the maximum number of occurrences of his favorite string s after replacing no more than k characters in the text of the newspaper t . Ivan does not have to replace exactly k letters, and perhaps he does not even have to replace a single letter. You can replace the letter from the string s with any other.



    Input

    The first line of input contains three integers n , m and k (1 ≤ nm≤ 250, 0 ≤ kn ) - the length of the string s , the length of the string t and the number of characters that Ivan can replace in his favorite string, respectively.

    The second line of the input contains a non-empty string s , consisting of n lowercase letters of the English alphabet - Ivan's favorite string.

    The third line of the input contains a non-empty string t , consisting of m lowercase letters of the English alphabet, - text written in the newspaper. It is guaranteed that the length of string s does not exceed the length of string t .

    Output

    Print a single integer - the maximum number of occurrences of Ivan's favorite line s after replacing no more than k characters in the text of newspaper t .

    Parsing


    A naive solution that goes through all the variations of the source string s and reads the answer for them has exponential complexity. However, we note that there will be no more different variants having at least one occurrence than | t | - | s | + 1, that is, the number of ways to “attach” string s to string t .

    We change the order of calculations, we sort through all possible positions of the application of string s to string t and for each we calculate which positions and symbols we need to change to get an entry in this position (or determine what fits into kchange is not possible). It is required in some way to encode the necessary changes, in order to then be able to distinguish whether the line requires the same changes for two different positions of the application or different. In this problem, there were small restrictions on the length of the strings t and s , so it was allowed to use almost any polynomial solution. For example, the necessary changes could simply be represented as an array of length | s |.

    Now select the groups of the same changes and find the group of the same size. This can be done in many different ways, for example using sorting or hashes.

    Problem C. Prize Fund


    The author of the idea and development: Alexey Dmitriev, MIPT
    Topic: mathematics

    Condition


    HackerCook held its grand sports programming championship with a large prize pool, but the distribution of prize money has not yet been announced. The only thing that is known about the final distribution is that a participant with a higher place will receive no less prize money than a participant with a lower place.

    Now one HackerKook employee wants to distribute the prize fund so that his friends receive a total of as much money as possible. Determine how much of the prize fund each participant will receive, provided that the employee distributes the money optimally.



    Input

    The first line of input contains two integers n and k (1 ≤ kn≤ 1,000,000) - the total number of participants and the number of friends of the HackerKook employee.

    The second line contains k different integers a i (1 ≤ a in ) in ascending order - the places that the friends of the cunning developer took.

    Output

    Print n non-negative integers b 1 , b 2 , ..., b n ( ), which mean that the participant who has taken the i- th place should receive a part of the prize pool.

    If there are several possible answers, it is allowed to print any.

    It is guaranteed that there is an optimal answer satisfying the condition described in the output format.

    Parsing


    Briefly: we consider all options for distributing all the money equally among the first few participants, at least one of these options will be the best answer.

    How to prove it? Consider some optimal answer. Let some two participants A and B in it receive a different positive amount of money, we denote their earnings a and b (then 0 < a < b ). We will divide all participants with a positive amount of money for those who received at least b and those who received less than b . Suppose that in these groups X and Yparticipants, respectively, and among them x and y friends, respectively (at least one of the numbers x and y is positive).

    Suppose we choose the number k and increase the earnings of each participant in the first group by k / X , and in the second group we decrease by k / Y (note that the total amount is preserved). Then the friends' earnings change by k (x / X - y / Y) . Note that we can choose both positive and negative k so that after the change no participant receives more money than those above him, as well as all earnings are non-negative. Since our answer is optimal, x / X = y / Y (otherwise, choosing a numberk of the desired sign, we could improve it). We choose k so that in the second group one of the participants has 0 money. The number of participants with a positive win has decreased; we will repeat this process until all participants with a positive amount winnings equal.

    Technically, the task is very simple: among all the prefixes of the sequence, one must choose such that the share of friends in it is maximum. This is done by a simple linear approach and saving the current answer as a fraction of a / b .

    Problem D. Flowers


    The author of the idea and development: Mikhail Mirzayanov, SSU
    Topics: greed, event handling

    Condition


    Vasya wants to give Masha a bouquet on March 8th. He knows one secret path in the forest outside the city, along which beautiful, and most importantly, free flowers grow. The path can be represented as a straight line, and we can assume that Vasya initially appears on it at point 0 and moves at a speed of 1, without wasting time on picking flowers.

    Flower number i grows at the point of the path with the coordinate x i , and after Vasya picks it up, the flower remains alive for another t i units of time. Naturally, Vasya must pick an odd number of flowers into the bouquet, and all of them must be alive at the moment when he brings them to point 0 to meet with Masha (if the i- th flower is brought exactly through t iunits of time after tearing it off, then it is no longer considered alive).

    Vasya is a straight man, and even for the sake of Masha he is not ready to turn (that is, change his direction of movement along the path) more than two times. Help him collect the largest bouquet of odd size.



    Input

    The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) - the number of flowers growing along the path.

    Each of the next n lines contains two integers x i and t i (–10 9x i ≤ 10 9 , 0 ≤ t i ≤ 109 ) - the coordinate of the i- th flower and the time that it will be alive after it is picked, respectively. More than one flower can grow at one point.

    Output

    Print a single number - the maximum possible number of flowers in a bouquet. If it is impossible to collect a bouquet even from one flower, print 0.

    Parsing


    The condition that Vasya is ready to change the direction of motion no more than twice clearly defines the form of the answer: first we go to one of the two sides to the stop, then, returning, we collect all the flowers, go through 0 and go the other way until some point , then turn around again and go to 0, again collecting all the flowers in its path. On how far we move away from point 0 before the last turn, it depends, on the one hand, how many flowers we can collect on the way back, and on the other, how many flowers collected in the first section will have time to fade.

    Without loss of generality, we assume that we first went from point 0 to the left (negative coordinates), and then to the right. Then “turn the world” and solve the symmetric problem. Of course, we will pick up a bouquet of the maximum size, and then just find the odd number closest to this maximum.

    The flower located to the right of point 0 can be brought to Masha if x i < t i for the corresponding i . Let us go to the right from point 0 to the coordinate R. Then the flower i , located to the left of point 0, can be managed to inform Masha if it is t i + x i - 2 R > 0 or R <(t i + x i ) / 2. Thus, along the ray with positive coordinates there are n events, each of which either adds a new flower or removes it. We go from 0 to the coordinates of the maximum event and find the maximum positive balance. It is necessary to carefully handle events located at one point and between integer points (here the problem will be solved by multiplying all coordinates by 2).

    Challenge E. Berland Hockey League


    The author of the idea and development: Alexander Ostanin, MIPT
    Topics: mathematics, graphs

    Condition


    The Berland Hockey League Championship is attended by n teams. The tournament is held in a round robin system: each team plays exactly one match with each, while there are no draws in the tournament. Unlike traditional tournaments, the distribution of prizes in the Berland Hockey League does not depend on the final place of the team, but on the number of victories. Namely: prizes are awarded to all teams that have won at least w games. Hockey expert Don Berry is wondering if exactly k teams can receive prizes based on the results of this tournament . If such a tournament exists, you need to withdraw the winner for each match.



    Specifications Input

    The only input line contains three numbers n , w and k(2 ≤ n ≤ 1000, 0 ≤ wn , 0 ≤ kn ) - the number of participating teams, the minimum number of victories to receive a prize and the number of tournament winners predicted by the expert.

    Output

    If a tournament with such properties does not exist, print “NO” (without quotes) in a single output line.
    Otherwise, in the first line print “YES” (without the quotes). Then print n lines of length n , the jth character of the i- th of them should correspond to the match between teams i and j . If i =j , then the corresponding character must be 0. If team i defeated team j , then this character is 1, otherwise 0. For all i ≠ j, exactly one of the two characters corresponding to the meeting of these teams should be 1.

    Parsing


    We will solve a more complex problem: we will build such a tournament that the minimum points among the first k teams are as high as possible, and the maximum points among the last n - k teams are as low as possible (it is stated that in some tournament the optimal values ​​of these values ​​are achieved simultaneously). Then either this tournament is the answer, or there is no answer.

    Obviously, in an optimal tournament, each of the first k teams must win against each of the last n - k , it remains to decide how all the first teams will play among themselves and how all the last teams will play. We would like the minimum points in the microtournament among the first k teams to be as high as possible, and in the tournament among the last teams the maximum points should be as low as possible.

    Let m teams participate in the tournament and m odd. Then, in a complete graph on m vertices, all degrees of the vertices are even, which means that there is an Eulerian cycle in it (and it can be constructed in time O (m 2 ) ). If we orient the edges along the cycle and say that the edge leads from the winning team to the loser, we get a tournament in which each team won exactly (m-1) / 2 times.

    Now let m be even. Then it is impossible to build a tournament with the same number of points for all teams and the last team will have no more than (m-2) / 2points. But a tournament with this property can be built if you throw one vertex, apply the algorithm from the previous paragraph to the remaining m - 1 teams, and then set the winning team for half of the remaining teams. In the resulting tournament, half of the teams (m-2) / 2 points, and the other half - m / 2 points.

    This way of building the most “even” tournament is suitable for both the first k teams and the last n - k teams. In the end, we verify that it really is the answer (that is, all the first teams won at least w times, and the rest won less than w times).

    Problem F. Carlson


    Authors of the idea and development: Gleb Evstropov, HSE, and Mikhail Mirzayanov, SSU
    Topics: greed, dynamic programming

    Condition


    Twenty years have passed. Carlson is fat and no longer flies. The kid got a job, became a top manager and now lives in a huge house on the nth floor.

    Carlson decided to visit the Kid. Of course, he is not going to climb on foot, so on the first floor Carlson enters the elevator.

    The buttons in the elevator are located from the bottom up so that a person with height h can reach any button corresponding to the floor from 1 to h inclusive. At the same time, on the i- th floor, Carlson has a friend with the growth of h i , and he can be asked to click on any button that he can reach. Of course, to ask a friend with iof the first floor, press the button, first you need to be on floor i . Carlson wants to get to Toddler, turning to the smallest possible number of friends for help.

    Unfortunately, over time, Carlson's character also deteriorated, so sometimes he quarrels with his friends, but no more than one friend at a time. Carlson wants for each i to determine the minimum number of friends who will have to turn for help if he quarrels with friend i and cannot contact him with a request to press the button.



    Input

    The first line of the input contains two integers n and h (2 ≤ n ≤ 10 6 , 1 ≤h ≤ 10 9 ) is the number of the floor on which the Kid lives, and Carlson's height, respectively. The next line contains integers h 1 , h 2 , ..., h n - 1 (1 ≤ h i ≤ 10 9 ), the i- th of which corresponds to the growth of Carlson's friend, who lives on the i- th floor.

    Output

    Print n - 1 the number ans 1 , ans 2 , ..., ans n - 1 , where ans iequal to the minimum number of friends who have to ask for help if Carlson quarrels with a friend living on the i- th floor. If, having quarreled with the i- th friend, Carlson cannot get to the Kid, print -1 instead of the corresponding value ans i .

    Parsing


    First, we solve the problem, provided that Carlson is friends with all his friends. At each moment in time, we can assume that he has access to some floor prefix, since if Carlson could get to floor x , then he could get to all the intermediate ones. Then, obviously, the most profitable move will be to use the help of the highest friend on this prefix. The complexity of such a solution is O (n) .

    This immediately gives us a way to solve the initial problem in quadratic time - to sort out which of the friends Carlson quarrels with and solve the problem for each case. Now note that on each prefix we are only interested in two maximum values, and we calculate the following quantities:

    f i- the minimum number of steps for which Carlson can get to the Kid if he has access to the floor prefix from 1 to i and at the same time he does not quarrel with the highest friend on this prefix;
    g i - the minimum number of steps for which Carlson can get to the Kid if he has a floor prefix from 1 to i and he has a falling out with the highest friend on this prefix (which means he will have to ask for a second-highest friend for help).

    By a i we denote the highest friend among the first i , and by b i - the second highest. Then f i = f ai + 1, and g i =g bi + 1 if a i = a bi , and g i = f bi + 1 otherwise.

    Now we will learn how to calculate the answer using these values. If one of Carlson's friends did not initially enter the optimal answer, then the answer for the case of a quarrel with this friend is optimal. If he entered, then the answer for this i will be k - 1 + g i , where k is the sequence number of this friend in the optimal answer.

    Problem G. Stone, scissors, paper


    The author of the idea and development: Konstantin Semenov, MIPT

    Condition


    Petya and Vasya play the famous game “Stone, scissors, paper”. The game takes place in n rounds. In each round, Petya and Vasya choose one of three figures: a stone, scissors or paper. If the figures of the players do not match, the winner is determined in the standard way (the stone defeats the scissors, the scissors defeats the paper, the paper defeats the stone), otherwise a draw is declared. For a victory w points are awarded , for a draw - d points, for a loss - 0 points. The final score of each player is the sum of points for all rounds.

    Petya determined in advance which figure he would choose in each round, and wrote it down as a string of length n from the letters r , s and p . Here the letter r is onThe i- th position in the line means that in the i- th round, Petya will choose a stone, s - scissors, and p - paper.

    Vasya got some cyclic shift of Petya’s line and wants to use this information to maximize his final score. Find the maximum score that Vasya can guarantee himself, no matter what kind of cyclic shift of the source line is the line known to Vasya.



    Input

    The first line of input contains three integers n , w and d (1 ≤ n ≤ 100 000, 0 ≤ dw ≤ 10 9) - the number of rounds, the number of points for a victory and the number of points for a draw, respectively.

    The second line contains a string of length n , consisting of the characters r, s, p , which is a cyclic shift of the string written by Petya.

    Output

    Print one number - the maximum score that Vasya can guarantee himself.

    Parsing


    Suppose we have already seen the first few characters of Petya’s string and they make up the string t . Denote by f (t) the maximum score that we can provide for ourselves; the answer to the original problem is f (empty string) . If the length of the string t is n , the game is over and f (t) = 0.

    Let the length t be less than n . If our next move, for example, is r (stone), in the worst case we will earn the minimum among the numbers: f (t + p) (the next Petya move is paper, we lost), d + f (t + r), w + f (t + s) . If any of these values ​​is undefined (for example, if the stringt + p is not a prefix of any cyclic shift), we put by definition f (t) = ∞. For the remaining two possible moves, the result is calculated in the worst case in the same way; since we can choose our next move, among the results for the three possible moves we choose the maximum, this maximum is equal to f (t) .

    This method allows us to calculate the answer to the problem. All possible values ​​of string t for which f (t)it’s not infinity, it’s convenient to imagine a tree in the form of a root tree, in which a letter is mapped to each edge and a line is mapped to any path from the root — a sequence of letters along which the path passes. The previous algorithm can be represented as dynamic programming on a tree, in which all cyclic shifts of the original string are present. The tree size and the complexity of the algorithm are O (n 2 ) .

    For optimization, we need an advanced structure - a compressed suffix tree. We construct a pine forest that contains all the suffixes of the string s , after which we “squeeze” into one edge the chain of vertices from which only one transition originates (now a line of some length is written on each edge). The resulting tree will containO (| s |) vertices and edges; in addition, it can be constructed in linear time (for example, using the Ukkonen algorithm or using a suffix automaton).

    Let's get back to our task. If we calculate the value of f at the vertex from which only one transition originates, we simply add w to the value of f for the only son of this vertex. This means that the calculation method f can be easily transferred to a “squeezed” boron: when passing along an edge of length L, we add w ( L - 1) to the result .

    Build a compressed suffix tree for the doubled source string. This tree contains all the cyclic shifts of the original row, so you can calculate the values ​​of the function from itf , carefully analyzing the cases when we go to the peaks at a depth greater than n . The final solution works in linear time.

    If you are interested in such tasks, you can take part in the Russian Code Cup 2016 and compete for a cash prize!

    Also popular now: