Russian Code Cup 2013: analysis of the tasks of the first qualification round

    On Saturday, April 13, 2013, at 19 o’clock the first qualifying round took place. Despite the seemingly unlucky date, for many this day turned out to be, on the contrary, very successful.
    In this post, we will briefly talk about the results of the first qualification round and analyze in detail the tasks that we proposed to the participants.
    In today's analysis involved:
    • Olympics in Gnomland
    • One day Anton Sergeevich and his students
    • Problems of storage of muran in Flatland nuclear laboratory
    • Actual issue of protecting the planet from meteorites
    • Teleports and what obstacles they create for treasure hunters

    Let's start with the totals. 765 people took part in the qualification (note that this is the number of participants who sent their solution options; there were noticeably more registrants).
    Participants were given 2 hours to solve problems. The tasks themselves were published on the site directly at the beginning of the qualification round, therefore, none of the participants could familiarize themselves with them in advance - all were on an equal footing.
    The geographical distribution of the participants turned out to be truly global, although, of course, the number of Russian participants was the maximum. So, in descending order:

    Russia - 540
    Ukraine - 81
    Belarus - 46
    USA - 21
    Armenia - 20
    Kazakhstan - 15
    Uzbekistan - 6
    Georgia - 6
    Germany - 6
    Switzerland - 5
    Sweden - 2
    United Kingdom - 2
    Netherlands - 2
    Kyrgyzstan - 2
    Poland - 2
    Iceland - 1
    Tajikistan - 1
    Ireland - 1
    Japan - 1
    Spain - 1
    Lithuania - 1
    Israel - 1
    Czech Republic - 1

    201 people entered the qualifying round. Below is a list of 10 participants who were the first to qualify:
    1. Vladislav Epifanov
    2. Sergey Rogulenko
    3. Ivan Popelyshev (3rd place)
    3. Pyotr Mitrichev (another 3rd place)
    5. Anton Raichuk
    6. Vladislav Isenbaev winger
    7 Anton Lunev
    8. Egor Kulikov
    8. Gennady Korotkevich
    8. Roman Rizvanov
    As you can see from the list, some participants shared places with the same number, as they scored the same number of points.
    Now let's move on to the analysis of tasks. Participants will be able to verify their decisions, and those who have not yet passed the qualification will be able to practice and check their versions (by the way, the following qualifying rounds are May 11 and June 2).

    Problem A. Olympiad
    Idea: Vitaly Aksyonov
    Implementation: Vitaly Aksyonov
    Analysis: Vitaly Aksyonov
    Detailed statement of the problem
    Time limit - 1 second
    Memory limit - 256 megabytes
    Now preparations are being made for the upcoming Olympics in Gnomland. The gnome-brigadier was given the task of building fields for playing hurtball, Jordanball and Medveball. Each field is a rectangle. In accordance with the rules of the game, the fields must be located so that their sides are parallel to the north-south and west-east directions.
    Land in Gnomland is very expensive, so game organizers want to spend as little money as possible on buying land. Since the Hertball, Jordanball and Medwebol competitions will be held at different times, the fields may overlap.
    Help the dwarves find the minimum area that three fields can occupy after construction.
    One of the possible optimal field layouts in the first example is shown in the figure.

    Input format
    Input data contains no more than 1000 lines, each of which contains a description of three fields - six natural numbers, each of which does not exceed 10000.
    The first and second numbers indicate the sizes of the first field, the third and fourth - the sizes of the second field, fifth and the sixth is the size of the third field.
    The input ends with a string of six zeros. This request does not need to be processed.
    Output format
    For each set, print a number - the minimum area that three fields can occupy.

    In order to solve the problem, you can notice that there is an optimal solution in which all three given rectangles have one of the corners in common.
    Enumerate how to put each field - vertically or horizontally. After we fixed the position of the fields, it is enough to simply calculate the area of ​​the union of the rectangles. It can be calculated as follows: S = S 1 + S 3 + S 3 - S 12 - S 23 - S 13 + S 123 , where S i is the area of ​​the ith rectangle, S ij is the intersection area of ​​two rectangles with numbers i and j, and S 123- the intersection area of ​​all three rectangles.

    Problem B. Trapezoidal map and trapezoid
    Idea: Vitaliy Demyanyuk
    Implementation: Vitaly Demyanyuk
    Analysis: Vitaly Demyanyuk
    Detailed statement of the problem
    Time limit - 2 seconds
    Memory limit - 256 megabytes
    Once, Sergey Sergeevich told students the algorithm for constructing trapezoid cards. As a warm-up, he gave them the task of trapeze. He drew n segments on the board. The length of the ith segment is ai. Students are required to find the number of different sets of four segments from which you can make an isosceles trapezoid of non-zero area.
    Recall that an isosceles trapezoid is a quadrangle, the two opposite sides of which are parallel, and the other two are equal. An example of an isosceles trapezoid is shown in the figure.

    Two sets are considered different if there is a segment belonging to the first set and not belonging to the second. The numbers of the taken segments in each set should be pairwise different.
    Help students find the number of such sets.
    Input format
    The first line contains the number t - so many times Anton gave his students this task. The following 2t lines contain descriptions of all tasks.
    The description of each task consists of two lines. The first line of the description contains the number n - the number of segments drawn on the board. The second line of the description of the problem gives n integers ai - their lengths (4 ≤ n ≤ 5000, 1 ≤ ai ≤ 108 for all i from 1 to n).
    The total number of all segments in all tasks does not exceed 5000.
    Output format
    For each task in a separate line print one number - the desired number of sets.

    Denote the lengths of the smaller and larger parallel sides of the trapezoid by a and b, respectively, and by c the length of the sides. Then a trapezoid can be made only if a + 2c> b. Going over a, b and c, we get a solution in O (n 3 ).
    Note that for fixed b and increasing c, the minimum possible a decreases. We will iterate over b in increasing order and, for a fixed b, we will iterate over c also in increasing order. When iterating over c, we will maintain a pointer to the minimum possible a. Knowing b, c, the minimum possible a, and using simple combinatorial formulas, it is easy to calculate the number of sets of four segments that form a trapezoid with given parameters.
    Also, do not forget to handle the cases in which a = b, a = c, b = c, and carefully make sure that in each four the numbers of the segments are pairwise different. The resulting complexity is O (n 2 ).

    Problem C. Storage of Mluran
    Idea: Vitaly Aksenov
    Implementation: Pavel Krotkov
    Analysis: Pavel Krotkov
    Detailed statement of the problem
    Time limit - 2 seconds;
    Memory limit - 256 megabytes.
    The chemical element muran discovered in 2345 is very radioactive. Improper handling of muran can lead to unpredictable consequences, therefore, special care must be taken when using it, storing and transporting it.
    There are many different isotopes of murano, each of which is characterized by one natural number - its atomic mass. During long-term storage together any pair of isotopes, the sum of the masses of which is equal to one of k “critical numbers”, this pair of isotopes reacts and an explosion occurs. It is known that all critical numbers are non-negative powers of two.
    In the Flatland nuclear laboratory, samples of murano are stored in two special warehouses. Scientists managed to get n different isotopes of muran, the masses of which are numbers from 1 to n. Now you need to distribute the isotopes in the warehouses for storage. Safe methods of storage are those in which each isotope is stored in exactly one warehouse, and any two different isotopes, the sum of the masses of which is equal to one of the “critical numbers”, are stored in different warehouses.
    Help scientists figure out how many different safe ways to store Mluran.
    Input format The input
    to the task contains several test suites. The description of each set consists of two lines.
    The first line of the description contains two integers n and k (1 ≤ n ≤ 1018, 1 ≤ k ≤ 61) - the number of isotopes that need to be stored, and the number of “critical numbers”. The next line contains k different natural numbers, each of which is a power of two and does not exceed 2n - critical numbers. Critical numbers are separated by spaces.
    The number of data sets in each test does not exceed 10000. The last line of the test contains two zeros.
    Output format
    For each test set on a separate line print the number of safe methods for storing all isotopes in two warehouses, taken modulo 109 + 7.

    First we implement a solution that works in linear time. We consider the mass of isotopes in increasing order, starting with 1. Let k be the current number, and 2 t be the minimum power of two greater than k. In this case:
    • if k is a power of two or 2 t does not lie in the set of “critical numbers”, the isotope of mass k can be stored in any warehouse
    • otherwise, an isotope of mass k can only be stored in that warehouse where there is no isotope of mass 2 t - k

    Note that the answer is 2 x + d , where d is the number of powers of two not less than 1 and not greater than n, and x is the number of numbers that are not powers of two such that their minimum large power of two does not lie in the set of “critical numbers ". Therefore, it is possible to divide all numbers from 1 to n into log 2 n segments, the boundaries of which are adjacent powers of two, then select the necessary segments and sum their lengths.

    Task D. Protection of the planet
    Idea: Vitaly Aksyonov
    Implementation: Nikolay Vedernikov
    Analysis: Nikolai Vedernikov
    Detailed statement of the problem
    Time limit - 2 seconds
    Memory limit - 256 megabytes
    After the recent fall of a meteorite in the Urals, many governments have thought about protecting the Earth from asteroids. For this, the International Anti-Meteorite Agency (MAMA) was created, in which the best scientists in the field of astrophysics were invited.
    For several weeks, scientists have found that n asteroids fly in the immediate vicinity of the Earth, and if the asteroid is strictly greater than R from the Earth, then it does not pose a danger to it. For simplicity, scientists suggested that all asteroids near the Earth fly in a straight line, and determined their position and velocity vector at zero time. Now, scientists want to learn how to respond to queries about how many asteroids pose a danger to the Earth at some point in time.
    For convenience, we introduce a rectangular Cartesian coordinate system. Let the Earth have coordinates (0, 0, 0). All asteroids and the Earth are considered material points in space.
    Several queries were asked about specific points in time. For each of them, it is required to determine how many asteroids at this moment pose a danger to the Earth.
    Input format
    The first line contains two integers n and R (1 ≤ n ≤ 100000, 1 ≤ R ≤ 106) - the number of asteroids and the radius of the danger zone.
    Each of the next n lines contains six integers xi, yi, zi, vxi, vyi and vzi (−106 ≤ xi, yi, zi ≤ 106, −100 ≤ vxi, vyi, vzi ≤ 100) - the coordinates that specify the initial position and velocity vector of the i-th asteroid. It is guaranteed that the velocity vector is not equal to 0.
    The next line contains a single integer m (1 ≤ m ≤ 100000) - the number of times that scientists are interested in.
    Each of the next m lines contains one integer ti (0 ≤ ti ≤ 107) - a point in time that interests scientists.
    Output format
    For each moment in time, print a single integer - the number of asteroids that are in the danger zone.

    Consider each meteorite and find the times of entry and exit into the danger zone. To do this, in the equation of the sphere x 2 + y 2 + z 2 = R 2 we substitute the equation of a straight line that defines the trajectory of the meteorite, that is, x = x 0 + dx • t, ​​y = y 0 + dy • t, ​​z = z 0 + dz • t. We get a quadratic equation for time. The roots will be the times that interest us. In this problem, problems with the accuracy of floating-point numbers could arise, therefore, if the root of the equation was close enough to an integer, it had to be rounded.
    Add these times to the queries and sort them in ascending order. If the time coincides, then those times that correspond to the time of entry will go first, then requests, and at the end - the times of leaving the danger zone. We’ll start a counter that counts how many meteorites we have in the danger zone. If the current time is the entry time, then increase it; if it’s a request, then we write down the answer to this request, otherwise we decrease the answer.
    Opening hours O ((n + m) • log (n + m))

    Problem E. Teleports
    Idea: Anna Malova
    Implementation: Boris Minaev
    Analysis: Boris Minaev
    Detailed statement of the problem
    Time limit - 2 seconds
    Memory limit - 256 megabytes The
    year 2112 was drawing to a close, and you, together with a small team of like-minded people, decided to go in search of treasures in one abandoned country. The cities of this country are connected by roads along which you can move in both directions. You know that the inhabitants of this country loved to bury their treasures along these roads. Therefore, you want to drive along all the roads of this country and find buried treasures. You need to make an effective travel plan in advance. To do this, choose a city from which to start your journey. Then, moving along the roads, visit some more cities. The plan drawn up is called effective if each road will be visited by you exactly once.
    Planning is complicated by one fact. Some pairs of cities are connected by teleporters. For example, if the city A and the city B are connected by teleport, then, having arrived on a road to the city A, you will immediately teleport to the city B and can continue driving only along the roads that are connected to the city B. Similarly, if you came by the road to city ​​B, then immediately teleport to city A and continue on the roads that are connected to city A.
    Each city can be teleported to no more than one other city. You need to make an effective travel plan.
    Input format
    The input contains a description of several tests. Each test has the following structure. The first line contains three integers n, m, k (1 ≤ n ≤ 105, 1 ≤ m ≤ 105, 0 ≤ k ≤ 105) - the number of cities, the number of roads and the number of teleporters. The next m lines contain two different numbers - the numbers of cities that are connected by the next road. Next, k lines contain two different numbers that describe pairs of cities that are connected by teleporters.
    There can be several roads between two cities. No city is connected by a road with itself. No city is teleported to itself. Any city is teleported to no more than one other city.
    It is guaranteed that the total number of cities in all tests does not exceed 105. Similarly, the total number of roads and the total number of teleporters also do not exceed 105. The last line of input contains three zeros. They do not need to be processed.
    Output format
    For each data set, output the answer in the following format: if an effective visit plan cannot be drawn up, print No. in a single line. Otherwise, in the first line print Yes, and in the second - m numbers indicating the road numbers. Roads should be displayed in the order in which they must be visited. Roads are numbered from one in the order in which they are given in the input. For each test, roads are numbered independently.

    For convenience, we denote the number of roads that lead to city i, as with i . First, we need to determine if there is an effective travel plan at all. Firstly, if there are two cities i and j such that with i ≠ 0 and with j ≠ 0 and there is no way between i and j, then we cannot build a plan. It should be noted that the path can contain not only roads, but also teleporters.
    Suppose we have already built some path that runs through all the roads. It is clear that for all cities that are not connected by teleports are not the first or last city on the way, with i should be even. If two cities i and j are connected by teleport and none of them is neither the first nor the last city on the way, then with ishould be equal to j .
    Consider what happens to the cities that lie at the ends of the path. Firstly, if city i is teleported to j and lies at the end of the path, then with i = с j + 1 (except for the case when j is also the end of the path). Moreover, if the path begins and ends in city i, then with i = с j + 2. If the city is not connected by teleport to another and is at one end of the path, then it with i may be odd.
    As a result, in order to verify the existence of a path, the following must be done. We calculate for each city a certain value a i . If city i is connected to j teleport, then a i = max (0, ci - c j ). Otherwise, a i = с i mod 2. If the sum of all a i is equal to two or zero, then the path exists, otherwise not.
    The construction of a plan to visit the country is similar to the construction of the Euler path in a regular column. It is necessary to start the search from the top with a i ≠ 0; if there is none, then with anyone with i ≠ 0. When moving to the next vertex, if it is connected to another vertex by teleport, you just need to go to it and continue searching for the way further. The proof that the path is indeed found completely is similar to the proof of the existence of the Euler path in a regular graph.
    The resulting difficulty is O (n + m + k).

    All solutions to problems will also be published on the official website of the Russian Code Cup . Those who have read to the end and feel the excitement can register for the next qualifying rounds - there is still time!

    Also popular now: