Report on the passage of the first round of the Russian Code Cup
On Saturday, April 19, the first qualifying round of the Russian Code Cup championship was held. We bring to your attention a report on how the round passed, what difficulties we encountered, about the objectives of the round and its results.
The start of the championship surprised everyone with unexpectedly high performance: at the time of the start of round 1, more than 5,000 participants registered to participate in the championship. For comparison, in 2013, more than 3,500 programmers participated in the championship. And the number of applications is constantly growing, because you can register until the beginning of the last qualifying round.
')
A record number of participants for all the years - 1255 took part in the round itself! This have not happened before! Last year there were 754 participants in the first round. The reverse side of such popularity and increased load became technical problems with the server, observed throughout the entire round. Pages with tasks and results were unavailable or accessible with a long delay. And if the server had not fallen, at least 3,000 participants would have taken in the first round, judging by the logs data on the number of requests.
But the round still went to the end. Due to technical problems, the results of the round are not completely reliable. It would be logical to make it “unrated” and hold a new qualifying round instead. On the other hand, many participants spent time and energy trying to still take part in the round and solve problems, and we would like them to encourage their efforts and perseverance. Therefore, we made the following decision:
1) 200 best participants , who nevertheless took part in the round despite the difficulties, pass to the qualifying round.
2) On Sunday, June 1, 2014 at 1-00 pm, another, fourth qualifying round will be held. According to the results, another 200 best participants will also qualify for the qualifying round. Thus, 800 programmers will take part in it, and not 600. RCC 2014 T-shirts will be sent to all those who passed to the qualifying round.
We understand that this is a rather controversial decision and it has its drawbacks, but we hope for an understanding of the community. For our part, we will make all possible efforts to ensure that the remaining rounds are completed without overlays and the 50 strongest programmers reach the final and fight for the title of champion of the Russian Code Cup 2014.
Participants sent 5945 decisions, of which 1982 were accepted by the system as correct. The programming languages used are as follows:
All five problems were solved by only three people (to qualify for the qualifying round, it was necessary to solve three problems with a penalty of no more than 233 minutes).
Task A. Game .
Idea: Andrei Komarov.
Realization: Anna Malova.
Analysis: Anna Malova.
In this problem, it was necessary to check whether the playing field is good. A good field was a field containing a free cell or two adjacent cells with the same numbers.
The solution of the problem is to check all the cells of the playing field and the pairs of neighboring cells, whether they meet the above conditions. Total complexity: O (n2).
Problem B. Timer .
Idea: Vitalik Aksyonov.
Realization: Artem Vasilyev.
Analysis: Artem Vasilyev.
In the task, you need to find the maximum possible number that can occur on the timer after t seconds, if it is allowed to replace the number on the timer no more than k times with the smallest number not less than x and divisible by y.
In the given constraints, it is always possible to get a number that is divisible by y. Consider the first time that such a number appeared on the timer. It can be shown that this number will be the smallest among the numbers not smaller than x and divisible by y. Denote it by z.
There are no more than two different optimal ways to get z on the timer. The first way is to exploit the vulnerability up to the first timer tick. In this case, we spend one use of vulnerability and zero seconds. The second way is not to waste use of the vulnerability and wait for the required number of seconds. This method is possible only when z is x ≤ t and spends z - x seconds and zero exploit vulnerabilities.
Denote the time after receiving z as to, and the remaining number of uses as ko.
After z appeared on the timer, Petya's actions become unambiguous. It is beneficial for us to use as many vulnerabilities as possible, because they add an additional y -1 seconds.
Hence the answer is z + min (to, ko) • (y -1) + to.
It remains to check both ways to get the number z, calculate the answer for the resulting to and ko and choose the maximum of them. Solution run time is O (1) per test case.
Problem C. The inverse problem of the largest increasing subsequence .
Idea: Andrei Stankevich, Nikolai Vedernikov.
Realization: Nikolay Vedernikov.
Analysis: Nikolay Vedernikov.
To solve the dynamic programming problem of the largest incremental subsequence, it was necessary to restore the original sequence from the array.
This problem can be solved constructively. For example, like this: d [i] = a [i] • n - i + 1, where n is the length of the sequence. Let us prove that this sequence is suitable.
∀ i <j, for which d [i] <d [j], will be satisfied: (d [j] - d [i]) • n ≥ n, and (j - i) <n ⇒ a [i] < a [j]. Similarly, in the other direction.
∀ i <j, for which d [i] = d [j], will be satisfied: a [i]> a [j].
In addition, there is a solution using the topological sorting algorithm.
Problem D. Tricolor chess .
Idea: Vitaly Demyanyuk.
Realization: Vitaly Demyanyuk.
Analysis: Vitaly Demyanyuk.
The task required counting the number of ways to paint each unpainted n × m board cell in three colors so that no two adjacent cells were painted in the same color.
This is a dynamic programming task for a broken profile.
Enumerate all colors. Each state corresponds to a quadruple of numbers (x, y, c, mask), where (x, y) are the coordinates of the cell where the profile breaks begin. Consider all the cells of the profile in the order from top to bottom. Then c is the color of the first cell of the profile. Consider the ith profile cell and the many colors in which it is not painted. This set consists of two colors. Then the i-th bit of mask is 0, if the color of i + 1 profile cells is equal to the minimum of this set, 1 - if the maximum.
In each state we will store the number of ways to paint the corresponding part of the board. Recalculation of values is the same. as in any other dynamic problem
broken profile programming. To get the answer, let's go over all c and mask and sum up the value in the states (n, m, c, mask).
Operating time - O (nm 2 n).
Task E. How to build a network .
Idea: Boris Minaev.
Realization: Boris Minayev.
Analysis: Boris Minayev.
The task required connecting all computers to switches that are arranged in a circle, while spending the least amount of cable. This problem can be solved using the algorithm for finding the maximum flow of the minimum cost. However, we describe a solution that uses the dynamic programming method and also has the best runtime.
To begin, consider the easier task. Let computers and switches be located on a straight line. Let us call the balance the difference between the number of computers we reviewed and the number of connections to the switches that were used. For each balance from -n to n we will keep the lowest cost to achieve it. The cost of achieving balance must be determined in such a way that, with a balance of 0, its cost coincides with the cost of laying the entire network. For example, this can be done as follows: if after adding the next device the balance module has increased, then the distance to the device is subtracted from its cost, otherwise it is added. Now let's use the dynamic programming method.
We will consider the device from left to right. If the current device is a computer, then the balance must be increased by 1 and its cost accordingly changed. If we consider a switch, then it is necessary to sort out how many computers will be connected to it, and carefully calculate the cost of the balance (perhaps the first few connections will increase it, and the next will decrease it). This solution works for O (n 2 • (n + m)).
Consider a method that allows you to reduce the time of the algorithm to O (n • (n + m)). The most time-consuming place of the algorithm is the update of dynamic programming values when processing a switch. We will find the cost of obtaining balances from smaller to larger. In this case, we will maintain a queue in which the costs of obtaining the desired balance from various previous states of balances are stored. When switching to a new balance value, you may need to remove the first element from the queue (if the required number of computers cannot be connected to the current switch), add the ability to get the current balance without using the switch at all, and also change all the current values that are in the queue — for it needs to be added (or subtracted) the distance to the switch. An increasing sequence of values should always be kept in the queue. Then the answer for the current balance will always be in the first place of the queue.
Now consider the network option in the form of a circle. Cut the circle and fix the number of wires that pass through the cut. It can easily be shown that if there is an optimal answer in which exactly as many wires go through the cut, then there is an optimal answer in which these wires are connected to the first devices of the corresponding type. Thus, we obtained a solution on a circle in O (n 2 • (n + m)).
Download and read the test results on the results page of the round .
The start of the championship surprised everyone with unexpectedly high performance: at the time of the start of round 1, more than 5,000 participants registered to participate in the championship. For comparison, in 2013, more than 3,500 programmers participated in the championship. And the number of applications is constantly growing, because you can register until the beginning of the last qualifying round.
')
A record number of participants for all the years - 1255 took part in the round itself! This have not happened before! Last year there were 754 participants in the first round. The reverse side of such popularity and increased load became technical problems with the server, observed throughout the entire round. Pages with tasks and results were unavailable or accessible with a long delay. And if the server had not fallen, at least 3,000 participants would have taken in the first round, judging by the logs data on the number of requests.
But the round still went to the end. Due to technical problems, the results of the round are not completely reliable. It would be logical to make it “unrated” and hold a new qualifying round instead. On the other hand, many participants spent time and energy trying to still take part in the round and solve problems, and we would like them to encourage their efforts and perseverance. Therefore, we made the following decision:
1) 200 best participants , who nevertheless took part in the round despite the difficulties, pass to the qualifying round.
2) On Sunday, June 1, 2014 at 1-00 pm, another, fourth qualifying round will be held. According to the results, another 200 best participants will also qualify for the qualifying round. Thus, 800 programmers will take part in it, and not 600. RCC 2014 T-shirts will be sent to all those who passed to the qualifying round.
We understand that this is a rather controversial decision and it has its drawbacks, but we hope for an understanding of the community. For our part, we will make all possible efforts to ensure that the remaining rounds are completed without overlays and the 50 strongest programmers reach the final and fight for the title of champion of the Russian Code Cup 2014.
Statistics
Participants sent 5945 decisions, of which 1982 were accepted by the system as correct. The programming languages used are as follows:
- GNU C ++ Solutions: 2369
- Visual C ++ Solutions: 1707
- Java solutions: 927
- C # Solutions: 461
- Python Solutions: 309
All five problems were solved by only three people (to qualify for the qualifying round, it was necessary to solve three problems with a penalty of no more than 233 minutes).
Tasks of the first qualifying round
Task A. Game .
Idea: Andrei Komarov.
Realization: Anna Malova.
Analysis: Anna Malova.
In this problem, it was necessary to check whether the playing field is good. A good field was a field containing a free cell or two adjacent cells with the same numbers.
The solution of the problem is to check all the cells of the playing field and the pairs of neighboring cells, whether they meet the above conditions. Total complexity: O (n2).
Problem B. Timer .
Idea: Vitalik Aksyonov.
Realization: Artem Vasilyev.
Analysis: Artem Vasilyev.
In the task, you need to find the maximum possible number that can occur on the timer after t seconds, if it is allowed to replace the number on the timer no more than k times with the smallest number not less than x and divisible by y.
In the given constraints, it is always possible to get a number that is divisible by y. Consider the first time that such a number appeared on the timer. It can be shown that this number will be the smallest among the numbers not smaller than x and divisible by y. Denote it by z.
There are no more than two different optimal ways to get z on the timer. The first way is to exploit the vulnerability up to the first timer tick. In this case, we spend one use of vulnerability and zero seconds. The second way is not to waste use of the vulnerability and wait for the required number of seconds. This method is possible only when z is x ≤ t and spends z - x seconds and zero exploit vulnerabilities.
Denote the time after receiving z as to, and the remaining number of uses as ko.
After z appeared on the timer, Petya's actions become unambiguous. It is beneficial for us to use as many vulnerabilities as possible, because they add an additional y -1 seconds.
Hence the answer is z + min (to, ko) • (y -1) + to.
It remains to check both ways to get the number z, calculate the answer for the resulting to and ko and choose the maximum of them. Solution run time is O (1) per test case.
Problem C. The inverse problem of the largest increasing subsequence .
Idea: Andrei Stankevich, Nikolai Vedernikov.
Realization: Nikolay Vedernikov.
Analysis: Nikolay Vedernikov.
To solve the dynamic programming problem of the largest incremental subsequence, it was necessary to restore the original sequence from the array.
This problem can be solved constructively. For example, like this: d [i] = a [i] • n - i + 1, where n is the length of the sequence. Let us prove that this sequence is suitable.
∀ i <j, for which d [i] <d [j], will be satisfied: (d [j] - d [i]) • n ≥ n, and (j - i) <n ⇒ a [i] < a [j]. Similarly, in the other direction.
∀ i <j, for which d [i] = d [j], will be satisfied: a [i]> a [j].
In addition, there is a solution using the topological sorting algorithm.
Problem D. Tricolor chess .
Idea: Vitaly Demyanyuk.
Realization: Vitaly Demyanyuk.
Analysis: Vitaly Demyanyuk.
The task required counting the number of ways to paint each unpainted n × m board cell in three colors so that no two adjacent cells were painted in the same color.
This is a dynamic programming task for a broken profile.
Enumerate all colors. Each state corresponds to a quadruple of numbers (x, y, c, mask), where (x, y) are the coordinates of the cell where the profile breaks begin. Consider all the cells of the profile in the order from top to bottom. Then c is the color of the first cell of the profile. Consider the ith profile cell and the many colors in which it is not painted. This set consists of two colors. Then the i-th bit of mask is 0, if the color of i + 1 profile cells is equal to the minimum of this set, 1 - if the maximum.
In each state we will store the number of ways to paint the corresponding part of the board. Recalculation of values is the same. as in any other dynamic problem
broken profile programming. To get the answer, let's go over all c and mask and sum up the value in the states (n, m, c, mask).
Operating time - O (nm 2 n).
Task E. How to build a network .
Idea: Boris Minaev.
Realization: Boris Minayev.
Analysis: Boris Minayev.
The task required connecting all computers to switches that are arranged in a circle, while spending the least amount of cable. This problem can be solved using the algorithm for finding the maximum flow of the minimum cost. However, we describe a solution that uses the dynamic programming method and also has the best runtime.
To begin, consider the easier task. Let computers and switches be located on a straight line. Let us call the balance the difference between the number of computers we reviewed and the number of connections to the switches that were used. For each balance from -n to n we will keep the lowest cost to achieve it. The cost of achieving balance must be determined in such a way that, with a balance of 0, its cost coincides with the cost of laying the entire network. For example, this can be done as follows: if after adding the next device the balance module has increased, then the distance to the device is subtracted from its cost, otherwise it is added. Now let's use the dynamic programming method.
We will consider the device from left to right. If the current device is a computer, then the balance must be increased by 1 and its cost accordingly changed. If we consider a switch, then it is necessary to sort out how many computers will be connected to it, and carefully calculate the cost of the balance (perhaps the first few connections will increase it, and the next will decrease it). This solution works for O (n 2 • (n + m)).
Consider a method that allows you to reduce the time of the algorithm to O (n • (n + m)). The most time-consuming place of the algorithm is the update of dynamic programming values when processing a switch. We will find the cost of obtaining balances from smaller to larger. In this case, we will maintain a queue in which the costs of obtaining the desired balance from various previous states of balances are stored. When switching to a new balance value, you may need to remove the first element from the queue (if the required number of computers cannot be connected to the current switch), add the ability to get the current balance without using the switch at all, and also change all the current values that are in the queue — for it needs to be added (or subtracted) the distance to the switch. An increasing sequence of values should always be kept in the queue. Then the answer for the current balance will always be in the first place of the queue.
Now consider the network option in the form of a circle. Cut the circle and fix the number of wires that pass through the cut. It can easily be shown that if there is an optimal answer in which exactly as many wires go through the cut, then there is an optimal answer in which these wires are connected to the first devices of the corresponding type. Thus, we obtained a solution on a circle in O (n 2 • (n + m)).
Download and read the test results on the results page of the round .
Source: https://habr.com/ru/post/220333/
All Articles