Russian Code Cup 2012: Analysis of the tasks of the third qualifying round
The last qualifying round of the Russian Code Cup is over . In the semi-finals, in the qualifying round, passed the best 600 participants. On June 16th we will watch the battle of the minds, fifty winners will go to the final, where 18 thousand dollars will be played.
In this article I will examine in detail the tasks that were proposed for the third qualification . This material should be useful both for those who make the first steps in sports programming, and for participants who could not solve all five problems. Also welcome to the previous two tests: from the first and second qualifications.
')
A great problem with counting the minimum amount of negativity per employee from visitors in the queue, about watches filled with paint, about a chocolate bar that was not eaten by someone - I will try to share with you the pleasure of analyzing these wonderful tasks.
The tasks of the qualifying round will be much more complicated and even more interesting. Come "cheer"on June 16 at 11:00 on the site RussianCodeCup.Ru.
It is obvious that if any pair of “width of the left half” - “width of the right half” together does not give n - the width of the chocolate bar, we write “yes”.
As in the first two qualifications, the first task was the simplest one and it needed to be done as quickly as possible and on the first attempt. The best result for Gennady Korotkevich - 1 minute 40 seconds since the start of the tour. This time was enough to grasp the task, write and test the program and send it to the server.
Obviously, the easiest option is when the game ends in one move of the first player - when the goal and the starting position are at a distance less than or equal to the specified stroke range.
The key solution to this problem is to prove that in all other cases, players can play indefinitely if none of them makes the wrong moves. Otherwise, the first move cannot win the first move, because on every move of the first the second can return a piece back so as not to lose. The second cannot win either, because for every move of the second, the first one can return the second in place so as not to lose.
As a result, the solution of the problem turns out to be extremely simple - to display the victory of the first player in one move, if the distance between the points is less than or equal to the specified stroke range, and to output “Infinity” in other cases.
To begin, prepare a set of values ​​of the positions of the minute hand.
Similarly, we do with the clock hand:
Next we go through the whole product of these sets and check the correctness of the position of the arrows relative to each other.
The formula for checking the correctness of the situation is simple - 5 * h + mm / 12.
The auxiliary check function checks whether the mutual position of the minute and hour hands can exist and whether the positions of the arrows correspond to their visibility.
For each case, in a separate line, you should output the answer - the minimum total amount of negative that the official will receive. "
One of the examples to the problem demonstrates the described principle. In the example three officials came to the official. Two of them - at the beginning of the first hour with irritability "3" and "4", respectively. And one more - at the beginning of the second hour with irritability "5." It takes an hour to serve everyone, therefore at the beginning of the first hour there are two options - to let the visitor forward with irritability “4” or visitor with irritability “3”. Those who are not missed, go to the next hour, where another “5” visitor is added, and there appear two more options - to skip the beginner, or who is standing in line.
For two hours, the official receives minimal irritability 6.
The algorithm that solves this problem is quite simple, if one guesses the fact that at each moment in time it is most advantageous to serve a person who has already arrived at this point, not yet served, and the irritability of which is no less than that of the rest of the same people.
We prove this statement. Suppose we have a schedule, built on this rule and some optimal schedule. Consider the first time instant t 1 , in which they differ. Let the person, who at this moment is served in the optimal schedule, has irritability w 1 , and the person who is served at this moment in the second - irritability w 2 . In the optimal schedule, this person is served at some time point t 2 , and t 2 > t 1 (after all, before the time t 1, the schedules were the same). So, if in the optimal schedule you swap these two people, which can obviously be done, as at the time t 1 and at the time t 2 they are both available (since both schedules are valid), then the total anger in the optimal schedule changes to (t 2 - t 1 ) Ă— w 1 + (t 1 - t 2 ) Ă— w 2 , which is equal to (t 2 - t 1 ) Ă— (w 1 - w 2 ).
Since t 2 > t 1 (as mentioned above), and w 2 > w 1 (by building the study schedule), the indicated amount of anger change will be negative, which means that the optimal schedule has improved. Obviously, such reasoning for all other discrepancies will lead to the fact that the queue algorithm described above is correct.
Now you can think about the implementation of the solution described. We need a data structure in which all people who have already arrived, but not yet served, will be stored, and from which it would be possible to extract the maximum element in a small amount of time (a person whose irritability is no less than the rest). This structure is a priority queue. When implementing it, for example, using a binary heap, operations will be performed in O (log n), and the total asymptotic operating time of the solution will be O (n log n).
In Java and C ++, for example, the priority queue is implemented as the PriorityQueue and priority_queue classes, respectively. But for completeness, you should tell what it is for those who do not know.
The priority queue allows you to store pairs (key, value) and supports operations to add a pair, quickly find a pair with a minimum or maximum key, and retrieve such a pair. The binary heap is an effective and optimal way to implement this structure.
Binary heap with maximum accumulation is realized through a binary tree, in which any descendant node cannot be larger than its ancestor node, that is, the root is always the maximum, therefore getting it very quickly. Adding a new pair is made to any free end node (sheet), after which it moves towards the root, while the value of the ancestor is less than the value of the newly added key.
You can get acquainted with this algorithm in details here: http://www.rsdn.ru/article/submit/heap/heaps.xml#EKLAC
For a detailed statement of the problem, see RussianCodeCup.ru.
It will take too much time to iterate through all the34-bit numbers - which is 17 billion values. To optimize the brute force, they use a method called meeting in the middle (meet-in-the-middle).
The concept of meet-in-the-middle involves splitting the task in half and solving the “big task” through partial calculation for the halves. The classic problem solved by such an approach is the problem of the most efficient packing of a backpack. Each item is characterized by weight and value, you need to pack things with a maximum total value in a backpack with a weight limit. To solve it, a large set of things N is divided into two equal (or approximately equal) subsets, for which you can go through all the options in a reasonable time, and calculate the total weight and value for each, and then for each group from the first subset, find the group from the second maximum value at which the total weight will fit into the restrictions.
In our case, you need to calculate the hashes for the first n / 2 bits and separately for all possible options for nn / 2 bits. In each half, a maximum of 2 17 = 131072 options is obtained.
Since we need to get a message with a fixed known hash h, then each variant of the hash value for the first half of the bits h 1 matches not more than one hash value for the second half of the bits h 2 such that h = (h 1 + h 2 ) mod M .
It remains to learn for each variant h 1 to quickly find the corresponding value of h 2 . To do this, you can use data structures such as set in C ++ or TreeSet and HashSet in Java.
You can also sort all possible hash values ​​for the first and second half in ascending order and use the idea of ​​“two pointers”.
We will move the first pointer i through the hashes for the first half in ascending order of values. In the second half, we will search for the corresponding hash, starting from the previous suitable value, moving the second pointer j along the hashes for the second half in descending order of values. At that moment, when the pointer j reaches the minimum value, it will need to be moved to the maximum value. But, this will happen no more than once, therefore, the total pointer j will pass no more than two times over all values.
And, finally, it is necessary to choose from all the found pairs of suitable values ​​of h 1 and h 2 the one in which the minimum number of bits has changed compared with the received message m.
Aliyev Rauf,
Director of Research and Education
Mail.Ru Group
In this article I will examine in detail the tasks that were proposed for the third qualification . This material should be useful both for those who make the first steps in sports programming, and for participants who could not solve all five problems. Also welcome to the previous two tests: from the first and second qualifications.
')
A great problem with counting the minimum amount of negativity per employee from visitors in the queue, about watches filled with paint, about a chocolate bar that was not eaten by someone - I will try to share with you the pleasure of analyzing these wonderful tasks.
The tasks of the qualifying round will be much more complicated and even more interesting. Come "cheer"
"Chocolate"
In the Chocolate task, it was necessary to determine whether it was possible to assemble a whole from the two halves of a square chocolate. A progressive “sweep” is applied to the entrance - the width in segments alternately of the left half and the right half of each “line”. It is necessary to give an answer whether there are any missing segments: “yes” means that such a thing was discovered, and “no” if everything is in order. Detailed statement of the problem, see the official site of RussianCodeCup.ruIt is obvious that if any pair of “width of the left half” - “width of the right half” together does not give n - the width of the chocolate bar, we write “yes”.
As in the first two qualifications, the first task was the simplest one and it needed to be done as quickly as possible and on the first attempt. The best result for Gennady Korotkevich - 1 minute 40 seconds since the start of the tour. This time was enough to grasp the task, write and test the program and send it to the server.
"A game"
According to the condition of the problem, it is necessary to find a winner in a simple game in which players alternately move one piece along an infinite field. It is necessary, according to the known coordinates of the initial position and the target where the figure is to be brought, as well as a numerical parameter relating to the range of the figure, to report the outcome of the game and the number of the course at which the game ends and whose turn was last, or to bring Infinity, Players can play indefinitely ... For a detailed task, see the official site of RussianCodeCup.ruObviously, the easiest option is when the game ends in one move of the first player - when the goal and the starting position are at a distance less than or equal to the specified stroke range.
The key solution to this problem is to prove that in all other cases, players can play indefinitely if none of them makes the wrong moves. Otherwise, the first move cannot win the first move, because on every move of the first the second can return a piece back so as not to lose. The second cannot win either, because for every move of the second, the first one can return the second in place so as not to lose.
As a result, the solution of the problem turns out to be extremely simple - to display the victory of the first player in one move, if the distance between the points is less than or equal to the specified stroke range, and to output “Infinity” in other cases.
"Clock"
In the task it is necessary to find the number of different positions of the hands at the time of stopping the clock. According to the condition, the dial can be opened only partially, and if one of the hands or both hands hit the open sector at the time of stopping, their position becomes known, but the number of possible options is narrowed. It is also known that the positions of the hour and minute hands, as in the real clock, are directly dependent on each other. Required to find the number of options arrows. Full formulation of the problem with all the details is available on the site RussianCodeCup.ruTo begin, prepare a set of values ​​of the positions of the minute hand.
if (m == -1) { // , // mins = new int[60]; for (int i = 0; i < 60; i++) mins[i] = i; } else { // , () mins = new int[]{m}; } Similarly, we do with the clock hand:
if (h == -1) {// , // hours = new int[12]; for (int i = 0; i < 12; i++) hours[i] = i; } else { // , () hours = new int[]{h}; } Next we go through the whole product of these sets and check the correctness of the position of the arrows relative to each other.
| Minute hand | 0-11 | 12-23 | 24-35 | 36-47 | 48-59 |
| Hour hand (in min. divisions) | 5 * h + 1 | 5 * h + 2 | 5 * h + 3 | 5 * h + 4 | 5 * h + 5 |
| 5 * h + int (m / 12) | |||||
The formula for checking the correctness of the situation is simple - 5 * h + mm / 12.
for (int hh : hours) { // for (int mm : mins) {// int hhh = hh; // hhh – if (hours.length != 1) hhh = hhh * 5 + mm / 12; // // check . // a = // b = ans += check(a, b, hhh, mm, h == -1, m == -1) ? 1 : 0; } } The auxiliary check function checks whether the mutual position of the minute and hour hands can exist and whether the positions of the arrows correspond to their visibility.
boolean check(int a, int b, int hh, int mm, boolean hInside, boolean mInside) { // a = // b = // hh = // mm = // hInside = // mInside = boolean hOk = inside(a, b, hh) ^ hInside; boolean mOk = inside(a, b, mm) ^ mInside; return hOk && mOk && (hh % 5 == mm / 12); } // , m a,b boolean inside(int a, int b, int m) { if (a <= b) return a <= m && m <= b; return inside(a, 59, m) || inside(0, b, m); } GAS "Queue"
The condition of this task is to bring it here in full:“Over the past few years, electronic queues have become part of everyday life. In many public institutions you can find a terminal printing a piece of paper with a number, and without asking the usual question “Who is the last?”, Visitors will use the electronic scoreboard to find out how long they will have to wait and when their turn will come.
However, while such systems are far from perfect. For example, the standard principle of any queue raises questions: "The one who first arrived is served first." In the development of innovative GAS "Queue", it was decided to make it such that the implementation of this principle is not required. Instead, the new system is designed to minimize the amount of negative attributable to the official, at the reception to which people stand in line.
It is known that every person has such a criterion as irritability. If this parameter is equal to w, then after t hours of waiting in the queue this person will bring down on the head of the official exactly wt units of anger and abuse. So, if a visitor is served immediately after his arrival, the official will not suffer, and if the visitor arrives at the beginning of the third hour, and his service started only at the beginning of the fifth hour, the amount of anger will be 2w.
It is also known that the service of each visitor takes exactly one hour, and each visitor comes at the beginning of an hour. Your task is to determine, according to the indices of irritability and the arrival times of visitors, how much negativity the official will receive in the optimal order of customer service.
The first line contains a single integer t - the number of cases that you have to handle. Further t descriptions of cases follow.
The description of each case consists of: the number n in the first line - the number of visitors, and n descriptions of the visitors themselves. For each visitor there are two integers ri and wi (1 ≤ ri, wi ≤ 106) in the separate line - the number of the hour at the beginning of which the visitor came, and his irritability coefficient, respectively.
The total number of visitors in all cases of a single test does not exceed 1,000,000.
For each case, in a separate line, you should output the answer - the minimum total amount of negative that the official will receive. "
One of the examples to the problem demonstrates the described principle. In the example three officials came to the official. Two of them - at the beginning of the first hour with irritability "3" and "4", respectively. And one more - at the beginning of the second hour with irritability "5." It takes an hour to serve everyone, therefore at the beginning of the first hour there are two options - to let the visitor forward with irritability “4” or visitor with irritability “3”. Those who are not missed, go to the next hour, where another “5” visitor is added, and there appear two more options - to skip the beginner, or who is standing in line.
| Annoyance comers | Option 1 | Option 2 | Option 3 | Option 4 | |
| Beginning | 3, 4 | P (3), RF = 0 | P (3), RF = 0 | P (4), RF = 0 | P (4), RF = 0 |
| Beginning | five | P (4), RF = 4 Ă— 1 = 4 | P (5), RF = 4 Ă— 1 = 4 | P (3), RF = 3 Ă— 1 = 3 | P (5), RF = 3 Ă— 1 = 3 |
| Beginning | - | P (5), RF = 4 + 5 = 9 | P (4), RF = 4 Ă— 2 = 8 | P (5), RF = 3 + 5 = 8 | P (3), RF = 3 Ă— 2 = 6 |
| MINIMUM |
For two hours, the official receives minimal irritability 6.
The algorithm that solves this problem is quite simple, if one guesses the fact that at each moment in time it is most advantageous to serve a person who has already arrived at this point, not yet served, and the irritability of which is no less than that of the rest of the same people.
We prove this statement. Suppose we have a schedule, built on this rule and some optimal schedule. Consider the first time instant t 1 , in which they differ. Let the person, who at this moment is served in the optimal schedule, has irritability w 1 , and the person who is served at this moment in the second - irritability w 2 . In the optimal schedule, this person is served at some time point t 2 , and t 2 > t 1 (after all, before the time t 1, the schedules were the same). So, if in the optimal schedule you swap these two people, which can obviously be done, as at the time t 1 and at the time t 2 they are both available (since both schedules are valid), then the total anger in the optimal schedule changes to (t 2 - t 1 ) Ă— w 1 + (t 1 - t 2 ) Ă— w 2 , which is equal to (t 2 - t 1 ) Ă— (w 1 - w 2 ).
Since t 2 > t 1 (as mentioned above), and w 2 > w 1 (by building the study schedule), the indicated amount of anger change will be negative, which means that the optimal schedule has improved. Obviously, such reasoning for all other discrepancies will lead to the fact that the queue algorithm described above is correct.
Now you can think about the implementation of the solution described. We need a data structure in which all people who have already arrived, but not yet served, will be stored, and from which it would be possible to extract the maximum element in a small amount of time (a person whose irritability is no less than the rest). This structure is a priority queue. When implementing it, for example, using a binary heap, operations will be performed in O (log n), and the total asymptotic operating time of the solution will be O (n log n).
In Java and C ++, for example, the priority queue is implemented as the PriorityQueue and priority_queue classes, respectively. But for completeness, you should tell what it is for those who do not know.
The priority queue allows you to store pairs (key, value) and supports operations to add a pair, quickly find a pair with a minimum or maximum key, and retrieve such a pair. The binary heap is an effective and optimal way to implement this structure.
Binary heap with maximum accumulation is realized through a binary tree, in which any descendant node cannot be larger than its ancestor node, that is, the root is always the maximum, therefore getting it very quickly. Adding a new pair is made to any free end node (sheet), after which it moves towards the root, while the value of the ancestor is less than the value of the newly added key.
You can get acquainted with this algorithm in details here: http://www.rsdn.ru/article/submit/heap/heaps.xml#EKLAC
"Interference"
In this task, it was necessary to write an algorithm for recovering corrupted data (a set of messages of 34 bits) using known polynomial hashes. You must restore the message that is different from the original in the least number of bits that have the same hash.For a detailed statement of the problem, see RussianCodeCup.ru.
It will take too much time to iterate through all the
The concept of meet-in-the-middle involves splitting the task in half and solving the “big task” through partial calculation for the halves. The classic problem solved by such an approach is the problem of the most efficient packing of a backpack. Each item is characterized by weight and value, you need to pack things with a maximum total value in a backpack with a weight limit. To solve it, a large set of things N is divided into two equal (or approximately equal) subsets, for which you can go through all the options in a reasonable time, and calculate the total weight and value for each, and then for each group from the first subset, find the group from the second maximum value at which the total weight will fit into the restrictions.
In our case, you need to calculate the hashes for the first n / 2 bits and separately for all possible options for nn / 2 bits. In each half, a maximum of 2 17 = 131072 options is obtained.
int m = (len + 1) / 2; // ó Pair[] h1 = new Pair[1 << m]; // for (int i = 0; i < h1.length; i++) { h1[i] = new Pair(i, countHash(i)); // } Pair[] h2 = new Pair[1 << (len – m)]; for (int i = 0; i < h2.length; i++) { h2[i] = new Pair(i, countHash(((0L + i) << m))); // } Since we need to get a message with a fixed known hash h, then each variant of the hash value for the first half of the bits h 1 matches not more than one hash value for the second half of the bits h 2 such that h = (h 1 + h 2 ) mod M .
It remains to learn for each variant h 1 to quickly find the corresponding value of h 2 . To do this, you can use data structures such as set in C ++ or TreeSet and HashSet in Java.
You can also sort all possible hash values ​​for the first and second half in ascending order and use the idea of ​​“two pointers”.
We will move the first pointer i through the hashes for the first half in ascending order of values. In the second half, we will search for the corresponding hash, starting from the previous suitable value, moving the second pointer j along the hashes for the second half in descending order of values. At that moment, when the pointer j reaches the minimum value, it will need to be moved to the maximum value. But, this will happen no more than once, therefore, the total pointer j will pass no more than two times over all values.
And, finally, it is necessary to choose from all the found pairs of suitable values ​​of h 1 and h 2 the one in which the minimum number of bits has changed compared with the received message m.
Aliyev Rauf,
Director of Research and Education
Mail.Ru Group
Source: https://habr.com/ru/post/145735/
All Articles