Results of the Russian Code Cup 2014 and analysis of tasks


    On October 4, the final round of the largest in Russia annual sports programming Olympiad Russian Code Cup was held . The winner of the Russian Code Cup 2014 and the winner of the main prize - $ 10,000 - was Gennady Korotkevich. The second place was taken by Peter Mitrichev - he received $ 5000. Yegor Kulikov finished third, his cash prize was $ 3,000. Also this year, for the first time, all the participants included in the top ten were awarded: owners of 4-10 places each received $ 1000.

    The final was held in a new online format for the championship. Unlike the last year’s offline final, the participants didn’t have to come to Moscow now, and the finalists solved all the proposed tasks online in a comfortable atmosphere for them. For the title of best programmer, 50 finalists who overcame qualifications and qualifying rounds fought. 23 people from this year's finalists participated in the 2013 RCC finals.

    Interesting Finale Facts

    The simplest task is A, 45 finalists solved it. The most difficult is F, there was no attempt on it. If we consider only the solved problems, then the most difficult was the task E, it was solved only by 3 finalists, and the first to do it was Eugene Kapun. And Alexey Shlyunkin solved only this problem.

    Finalists used only 2 programming languages ​​to solve problems!
    C ++ - 254 decisions, of which 91 are accepted
    Java - 52 decisions, 24 of them are accepted

    The first correct decision is Pyotr Mitrichev in 23 minutes, this is the most difficult final on this indicator.

    The winner - Gennady Korotkevich - passed the fifth task 1 minute 51 seconds before the end of the contest and came out on top. Having passed the fifth task, Peter Mitrichev, Yegor Kulikov or Dmitry Dzhulgakov could get ahead of him.

    Jacob Dlugach passed 3 tasks in the last hour, two in the last 16 minutes and burst into the top ten in 7th place.

    Parsing tasks

    Problem A . The game

    The task
    Time limit: 2 seconds
    Memory limit: 256 megabytes

    The king of Baytland holds an annual intellectual game. According to the rules of the game, all participants are divided into two teams, and each of the players is informed of a set of tips. During the game, participants can exchange tips according to the following rules: Each player of the first team can go up to one player of the second and ask him for a hint that he does not yet know. If there are several such clues, the participant of the second team tells him any of his choice. Each member of the first team may ask for a hint from only one player of the second team, while several players may contact the player of the second team. The first team wins if it succeeds in collecting all the tips. Help her captain find out if his team will be able to collect all the clues, regardless of the answers of the second team.

    Input formatThe first line of the input file contains three integers n, m (1 ≤ n , m ≤ 500) and k (1 ≤ k ≤ 5000) - the sizes of the commands and the number of prompts, respectively. The next n + m lines contain information about the prompts available to players at the beginning of the game in the following format. The first number in the line corresponds to the number of hints the player has, and the following numbers contain hint numbers - natural numbers not exceeding k .

    Output format.If the first team can collect all the hints, print 1. On the first line of the output file, print n numbers, for each member of the first team, indicate which of the players of the second team should contact him for a hint. If there are several answers, print any. If the first command cannot collect all the prompts in the first and only line print 2.

    Idea: Anna Malova
    Implementation: Anna Malova
    Analysis: Anna Malova

    Consider a bipartite graph - the first team, the second team. On the edge it is written what tips a member of the second team owns that the member of the first team does not yet know, that is, the difference in the sets of tips of the participants. We leave only those edges on which one number is written. Among such edges, we leave only those on which only one number is written.

    Using the constructed graph, we compose another bipartite graph: the vertices of the first beat are the participants of the first team, the vertices of the second beat are those tips that are still unknown to the first team. There is an edge between two vertices, if there was an edge in the previous bipartite graph, coming out of the same vertex on which this information was recorded. If the maximum matching is found in the graph, then the first team can win. Otherwise, the first team cannot win.

    To keep within the given time limits, one needs to use a bitset to find the difference of sets. In addition, before running the Kuhn algorithm to find the maximum matching, you need to compare the size of the shares, if the size of the share with the tips exceeds the size of the share of the participants, then the answer is immediately generated 2. Without this check, the solution does not fit into the time limit.

    Video Preview:



    Task B . Building painting

    The task
    Time limit: 2 seconds
    Memory limit: 256 megabytes

    One company decided to repaint the gray wall of their office n meters long in corporate colors: blue and orange. To do this, they bought an innovative robot painter.

    The robot can paint the walls in accordance with the program recorded in it. A program is a sequence of commands. Each command is given by two integers and a color and tells the robot which section of the wall to which color to paint. For example, a wall with a BBOOO painting plan can be obtained using a program consisting of two commands: paint in blue from the first meter to the fifth, and then - in orange from the third to the fifth.

    One of the programmers of the company was instructed to write a program, by executing which, the robot would paint the walls in accordance with a given scheme. He easily coped with the task and even wrote a program containing the minimum possible number of teams. After that, he wondered: how many programs exist of the same length that will paint the wall in accordance with the painting plan?

    Input format The first line contains the number T - the number of tests. The following are descriptions of T tests.

    The only line of the test contains a line consisting of the letters B and O , where the letter at the i- th position is responsible for whether i needs to be colored blue or orange1st meter of the wall.

    The total length of the lines does not exceed 500,000.

    The format of the output. For each of the T test cases print one number - the number of programs of minimum length programs that lead to painting the fence accordingly. Since the answer can be large, print the answer modulo 10 9 + 7.

    Idea: Vitaly Aksyonov
    Implementation: Nikolay Vedernikov
    Analysis: Nikolay Vedernikov

    The task required to paint the strip in two colors. We can paint any sub-line in some color. It was necessary to calculate the number of ways to paint the strip for the minimum number of paints.

    In this problem, there are two cases: the ends of the strip are painted in one color or in different. Consider the first case.

    The ends are painted in the same color, which means that the total lengths are 2 k + 1. We show how much minimum paint is needed. Consider the final coloring of the strip, if the last segment we painted the segment in the middle, then the total number of segments increased by two (we split some segment into two and added a new one). In this way we can extractk segments and at the end will be 1. Total, we spent k + 1 moves. If at some point we took a segment not from the middle, but from the edge, we will spend more moves than necessary.

    Now let's count the number of ways. Consider the final coloring and the last move we painted the segment in the middle, then the number of ways to choose this segment is equal to the total number of segments minus the extreme ones, total 2 k - 1. Thus, we reduced the problem to a smaller problem. Continuing in this way, we get the final answer (2 k - 1) · (2 k - 3) · ... · 3 · 1, which is equal to (2 k - 1) !! ..

    Consider the case in which the ends are painted in different colors then total segments 2 k. Consider the final coloring of the strip. Suppose that at the beginning we extracted segments from the middle l times, and then we extracted a segment from the edge. Then we spent l + 1 and we had 2 k -2 l -1 segments left , and the ends turned out to be the same color. According to the previous reasoning, we will not be able to colorize it faster than for k - l . Total: k + 1 moves. In addition, the fact follows that we paint the first step, a segment from one of the ends.

    Now let's count the number of ways. We call the first segment black. Let the first move we painted a segment from the left edge. Let’s go over it, he will paint, and everything that is to his right will have to be painted white, according to our reasoning. Note that now we have got two previous tasks, in which the ends are painted in the same color. Let there be l black segments in the left segment , then the answer on this segment will be ((2 l - 1) - 2) !!, and on the right ((2 k - (2 l - 1)) - 2) !! .. Except Moreover, we can paint the segments from the left half and from the right in any order. That is, the product of the segments must also be multiplied by choose ( l - 1, k), since we have already painted one segment, it remains for us to make another k paints, and in the left it remains to make l - 1 paints. In addition, we could paint the first segment further, because on top we still paint the right segment. And such options are equal to the length of the right side. Total, for a fixed number l, the answer will be (( l - 3) !!) · ((2 k - 2 l -1) !!) · choose ( l - 1, k ) · (suff_lenl). Thus, we sort through l and sum. Similarly, count for the other end.

    If we calculate the factorials and inverse factorials modulo, then for one lwe can be responsible for O (1). Total run time is O ( n ).

    Video Preview:



    Problem C . Backpack problem

    The task
    Time limit: 2 seconds
    Memory limit: 256 megabytes

    As a homework on computer science, Pete and Vasya were asked to write a program that solves the backpack problem. The problem is formulated as follows: N things are given with weights a i , is it possible to choose a subset of things with a total weight equal to exactly W ?

    Petya and Vasya successfully completed the task, having received Accepted in the testing system. But when discussing the problem, it turned out that Petya and Vasya used different approaches to the solution.

    It turned out that Vasya actually counted the number of ways to choose a subset of things weighing W, and when outputting the answer, I compared this number with zero. To simplify the implementation, Vasya did not consider the number of methods itself, but its remainder after dividing by a certain number m . Petya immediately stated that Vasya’s decision was incorrect, but could not come up with a test on which it gives the wrong answer. Can you find such a test?

    Given m, come up with a test for the backpack problem in which the number of ways to gain weight W is divided by m without a remainder.

    Input format The only line of the input file contains the integer m (1 ≤ m ≤ 10 18 ) - the module by which the calculations were performed in Vasya's program.

    Output format.If such a test does not exist, print a single number -1. Otherwise, in the first line print two space-separated integers N and W (1 ≤ N ≤ 200, 1 ≤ W ≤ 500). In the next line, print N integers a i (1 ≤ a iW ).

    Идея: Борис Минаев
    Реализация: Артем Васильев
    Разбор: Артем Васильев

    В данной задаче требуется найти такой тест для задачи о рюкзаке, что количество способов набрать вес W делится на число M.

    Далее будем считать W равным 500. Основная конструкция авторского решения основывается на генерации такого набора n вещей небольшого веса так, чтобы их сумма была меньше W/2. Подсчитаем для этого набора количество способов набрать подмножество вещей с суммарным весом k для всех k от 0 до W/2 и обозначим это число за ck. We require that for our set, any number from 1 to 10 18 is represented as the sum of no more than 200 - n numbers ck .

    Suppose that there is such a set of things that for every x there is k such that ck = 2 x, then this property would be obvious: for each x , if the binary notation M contains one at position x , we will add a thing with weight W - x to our set. Since the sum of the things added before this step was less than W / 2 , it is easy to see that the number of ways to get the weight of W isM. Заметим, что такой процесс можно описать следующим жадным алгоритмом: пока M больше нуля, мы находим максимальное ck ≤ M, добавляем вещь с весом W — k и вычитаем из M число ck.

    К сожалению, такой набор вещей получить трудно, поэтому необходимо придумать какой-то другой набор вещей, обладающий тем свойством, что вышеописанный жадный алгоритм находит решение для любого M. Для этого возьмем набор вещей со случайным небольшим весом и суммой меньше W/2. Можно проверить и убедиться, что если мы выберем наш набор таким образом и посчитаем для него числа ck, то жадный алгоритм с большой вероятностью вернет корректное разбиение любого числа M на слагаемые ck. Таким образом, можно построить набор вещей, удовлетворяющий этому свойству, и с помощью жадного алгоритма добавить вещей таким образом, чтобы количество способов собрать W стало равным 0 по модулю M.

    Видеоразбор:



    Задача D. Организация сети

    Условие задачи
    Time limit: 2 seconds
    Memory limit: 256 megabytes

    In one progressive country, the development of information technologies is in full swing! At high speed, highways were laid that will be used for data transmission. For ease of control over data flows and saving money on laying, the mains were laid in such a way that data can reach from any city to any other in a unique way.

    However, it is not enough just to lay wires; routing algorithms must also be developed. During the discussions, the following data routing model was: k cities are declared key points and each of them is renamed as “Serverrad- i". After that, each city receives a network address. The network address of city v will be an array of k elements, in which the i- th element is equal to the number of cities through which traffic must pass in order to get from city v to Serverrad- i .

    In order to avoid routing problems, each city must have a unique address. Also, the government wants Servergrad to be as small as possible. Help the government decide which cities to designate server cities.

    Input format The first line contains the number n (2 ≤ n ≤ 100 000) - the number of cities in the country. Next, in n- The first line contains pairs of cities between which the highway is laid.

    Output format. Print the number k - the minimum number of Server cities that are enough to ensure the correct routing of all cities. Next, print k different integers from 1 to n, where the i- th number is responsible for which city will be selected as Servergrad- i- th.

    Idea: Boris Minaev
    Implementation: Andrey Komarov
    Analysis: Andrey Komarov

    In the problem, a tree was given and it was necessary to mark the minimum possible number of vertices so that the distance vectors from each vertex to the selected ones were different.

    Let us consider separately the case when the given tree is a chain : the vertices can be ordered so that the first is associated only with the second, the last only with the penultimate, and the rest only with two neighbors. If the tree is a chain, then, obviously, one of the ends of this chain can be taken as an answer: all vertices will be removed from it at different distances.

    Otherwise, there is a vertex of degree greater than two in the tree. We hang a tree for this top. We calculate the following dynamics for each subtree: the minimum number of labels that must be placed in this subtree so that the distance vectors for each pair of vertices of this subtree are different, provided that there is at least one labeled vertex somewhere above the root of the subtree. We call the value of this dynamics min ↑. Note that this is not exactly what you need to calculate in the problem, but it will coincide with the task if you remove the restriction on existence above the root of the marked vertex. We call this dynamics min . Note that min ↑ ≤ min . So, if we can give an answer of exactly exactly min↑, then this will be the answer to the problem. We solve the problem in two stages - first we calculate the values ​​of min ↑, and then we get an answer of this size.

    Suppose we want to count min ↑ for some vertex v . We calculate these values ​​for its subtrees. It turned out that in some of them there is at least one label, and in the rest there are no labels. Let the number of subtrees in which there are no tags be equal to k . Then in the answer for v you need to add at least k- 1 tagged vertex (one in each unlabeled subtree, except for one). Let us add less. Then at least two untagged subtrees remained. Then the roots of these subtrees will be indistinguishable: there are no marked vertices in their subtrees, but the distances to all the others are the same. Now we show that these additions are enough. Consider any two vertices from different subtrees. They can be either at the same or at different depths. Let them at different depths. Then the distances from them to the supposed marked peak above the root are different (the lengths of the paths to the root are different). Let them be at the same depth. Then, by construction, at least one of the subtrees in which these vertices lie has a labeled vertex. Then the distances to it from these two selected vertices will be different: from the one from whose subtree the marked vertex is selected,

    We now construct an answer of size min ↑. The root we have chosen has at least three children. So, by construction, min ↑, at least in two subtrees of the root there is a labeled vertex. This means that for each subtree there is a marked vertex outside this subtree. Take it as the required min ↑ labeled vertex above. Then the answer will be the union of the answers min ↑ for all children of the root.

    All the considered operations can be done with a single walk in depth. So, the total runtime is O ( n ).

    Video Preview:



    Task E . Boolean tree

    The task
    Time limit: 2 seconds
    Memory limit: 256 megabytes

    Vitalik thought for a long time how to solve a simple problem, and in the process of inventing a solution he drew a graph on the board. This graph, by coincidence, turned out to be a root tree. At that moment, Borya came up to the board, and began to write expressions in some vertices of the tree in which different values ​​were assigned to Boolean variables.

    After that, they introduced a rule according to which for each vertex of the tree it is possible to determine the value of the variable at this vertex. Namely, if the assignment of this variable to a value was recorded at this vertex, then the last such value is used. If it was not possible to determine the value in this way, then the value of this variable is taken in the closest ancestor of this vertex, in which the assignment of the value to this variable is recorded. If the vertex does not have such an ancestor, then the value is not defined.

    After several operations, they wanted to calculate for a given variable in how many leaves of the tree the value of this variable is true, how many false, and how many not defined. And then they realized that it was difficult, and that they could not do this. Therefore, they ask you to help them, and after each addition of a record on assigning a value to a variable, determine for how many leaves the value of this variable is true, for how many false, and for how many not defined.

    Input format The first line contains the number T - the number of tests. The following is a description of the T tests.

    The first line of the test gives two positive integers n and m (1 ≤ n , m ≤ 10 5), where n is the number of vertices of a given tree, and m is the number of additions of new records about assigning a value to a variable. The second line contains n numbers, where the i- th number is the number of the ancestor of the i- th vertex. For the root, this number is zero. It is guaranteed that you are given exactly the tree. Next are m lines - descriptions of records. Each of these lines contains three numbers: v is the number of the vertex, x is the number of the variable, and b is zero or one if the value of the variable is false or true, respectively. The variable number is a positive integer not exceeding 10 5 .

    In each input data set, the sum of alln and the sum of all m does not exceed 10 5 .

    Output format. For each of the test cases, output m lines containing three numbers each — the number of tree leaves for which the value of the variable just written is true, false, and undefined, respectively.

    Idea: Boris Minaev
    Implementation: Demid Kucherenko
    Analysis: Vitalik Aksenov

    First, we reduce our problem to the problem of one variable. Let's start a tree for each variable in which the root of the original tree and a link to it will be in the initial state. The link in the tree will always point to the top in whose subtree we are now. Let's go around our tree in depth. If we go to the vertex in which some variable is set, then we create a new child at the vertex in the corresponding tree and rearrange the link to it. If we exit the top, then we rearrange the link in the corresponding tree to its ancestor. We squeezed the trees. We must also remember to store in each vertex the number of leaves in its subtree.

    We will now solve the problem on the tree for one variable. We will process all requests for this variable sequentially. We need to be able to do two things:
    • how many leaves are affected only by this peak;
    • find the nearest ancestor in which some value is set for this variable.

    If we implement this, processing the request is not very difficult:
    • we find the number of leaves affected by this vertex - x ;
    • we find the closest ancestor in which some value for this variable is set - p ;
    • if p has the same value as our vertex, then the quantity does not change;
    • if p has a different value than at our vertex, then the quantity changes to x ;
    • if p does not exist, then the number changes to x * then the number of "unknown" leaves decreases by x ;
    • in p you need to reduce the number of leaves affected by x

    To implement queries, you need to expand the tree into a tree of segments, where you can make a request on a subtree. Then, requests of the first kind are very easy to process using the sum in the subtree. To find the right ancestor, we will do the following: when we make a request to a vertex, we add one to all the vertices in the subtree, except for it, that is, we say that they are covered by another vertex. Then, in order to find the ancestor, we will look for the first position in binary elevation, in which the value differs by one - it will be the desired ancestor.

    Total run time: O ( mlog 2 n ), where n is the size of the tree, m is the number of requests.

    Video Preview:



    The task of the F . Robot

    The task
    Time limit: 8 seconds
    Memory limit: 256 megabytes

    A robot travels along a rectangular cell field consisting of n columns and m rows. He can begin his journey in any cell of the first row. Then he can make some (possibly zero) number of moves. Let the robot stand in column x and row y , then in one move it can go either to the cell ( x + 1, y + 1), or to the cell ( x - 1, y + 1). Of course, the robot cannot go beyond the boundaries of the field.

    The robot’s journey is complicated by the fact that there are rectangular barriers on the field, the sides of which are parallel to the sides of the field. The robot cannot go into the cage, which is covered by an obstacle. No two obstacles intersect, but may touch.

    You need to calculate the number of cells that the robot can get into.



    Input format The first line contains the number T - the number of tests. The following is a description of the T tests.

    The first line of the test contains two integers n and m (1 ≤ n , m ≤ 10 9 ) - the number of columns and rows in the field. The next line contains a single integer k (1 ≤ k ≤ 10 5) - the number of obstacles in the field. The next k lines describe the barriers. Each such line consists of four integers x 1 , y 1 , x 2 , y 2 , indicating the coordinates of the opposite corners of the obstacle (1 ≤ x 1x 2 ≤ n, 2 ≤ y 1y 2m ). It is guaranteed that the obstacles do not cross.

    The total number of obstructions in the input file does not exceed 10 5 .

    Output format. For each of Tprint one single number - the number of cells the robot can visit.

    Idea: Boris Minaev
    Implementation: Boris Minaev
    Analysis: Boris Minaev

    In the task it was necessary to calculate the number of cells that are reachable from the first line of the field. The main difficulty is that the sizes of each side of the field can reach 10 9 cells.

    Firstly, due to the fact that the robot moves diagonally, it is convenient to separately examine cells of different parity. The robot can reach all the cells of the first row of the field. We will increase yand recount reachable cells. It is most convenient to store a set of reachable cells for a row in the form of a union of disjoint segments. Then you can easily recount the set when moving to the next line. Namely, to each segment one cell will be added on each side. Some segments may be combined into one, and some intersect with field boundaries or obstacles.

    We will learn how to effectively change this set of segments. It is best to store it in a data structure that allows you to find a segment that intersects a given coordinate in O (log n ). Additionally, each segment will store information about whether the segment can increase left and right. Let's carefully consider all the events that may occur:
    • Two segments combined. This is the simplest case. You just need to combine them in a data structure.
    • The segment expanded to such an extent that it intersected with the edge of the field or obstacle. Then it is necessary to put a mark in the description of the segment that it can no longer grow in some direction.
    • The barrier began. It is necessary to consider all segments that intersect with the barrier. Some of them need to be completely removed, some trimmed, and some divided into two parts. It is also necessary to create events that will occur when neighboring segments grow so much that they cross the current obstacle.
    • The barrier is over. It is necessary to find two adjacent segments and mark them that they can grow in the direction of the rectangle. It is also necessary to add an event that should happen between neighbors. For example, if two neighbors are segments, then they can merge at some point. If one of them is a segment and the other is an obstacle, then they can intersect. In other cases, nothing needs to be added.

    Also note that all segments must be stored lazily. That is, changing their size, as well as recounting the total number of reachable cells, is necessary only when an event occurs that affects a given segment.

    The run time of the solution is O ( n log ( n )), where n is the total number of obstacles.

    Video Preview:


    Also popular now: