Russian Code Cup 2012: a detailed analysis of the tasks from the first qualification
On May 27, the first stage of the Mail.Ru Group programming contest Russian Code Cup 2012 was completed . In total, over a thousand people took part in RCC'12, of which 200 of the best reached the semi-final of the competition, in the qualifying round. The winner of the first qualifying round was a student at the UNN Vladislav Epifanov from Nizhny Novgorod. Participants sent 3391 decisions, of which 1066 were accepted by the system as correct. 634 people or 63% of the total number of participants solved at least one problem.
The Russian Code Cup is an individual sports programming competition held annually by the Mail.Ru Group. It traditionally consists of three stages: at the beginning of the summer three qualifying rounds take place, then the best take part in the qualifying round, the first fifty winners of the qualifying round compete in the final. Personal presence will require only the last of them, the rest are held online. All finalists will be awarded with valuable gifts, and the prize for the participant who won first place will be $ 10,000. For the second and third place rely 5,000 and 3,000 dollars.
In the article I will talk about the tasks that were offered to the participants and how to solve them. A brief analysis of the tasks published on the site immediately after the completion of the RCC, I will immediately try to explain the details so that the solution is clear even to novice programmers.
In total, five tasks were proposed for the tour: “Parallelepiped”, “Perestroika”, “War”, “Label”, “Javai Weapon”.
')
It should be remembered here that the parallelepiped is a figure, the base of which is a parallelogram - a quadrangle, whose sides are parallel in pairs. The parallelepiped has three dimensions in 12 edges - length, width and height. Therefore, it is necessary to answer the question whether there are exactly three groups of four identical numbers among the input data.
To understand this, you need to sort all the numbers and make sure that you get three groups of four identical numbers (the same at least within each group). If so, output yes; otherwise, no.
There were 1479 attempts to pass the “Parallelepiped” task, of which 639 were successful (43%). This task turned out to be the most accessible - the number of attempts more than twice as many as on other tasks, a high success rate.
RussianCodeCup.Ru: problem statement
RussianCodeCup.Ru: analysis of tasks
This task assumes some knowledge from the field of graph theory. The vertices of our graph are cities, the edges are roads. In graph theory there is the concept of a graph connectedness - the presence of a path from any vertex to any. In this case, initially we have a graph of unknown connectivity, and as a result, we must obtain a graph that is necessarily connected. There is the concept of a graph connected component - this is the maximum set of interconnected vertices with respect to inclusion. Accordingly, the number of connected components is the number of vertex groups not connected to each other. For example, if there are no edges of the graph (= roads) at all, the number of connected components is equal to the number of vertices (= cities). We also introduce the concept of a “bridge” - an edge, the removal of which makes the graph incoherent, that is, divides it into unrelated parts.
So, let us remember the essence of the reform from the formulation of the problem: one existing edge (= road) is removed, and another is added to the place where there was no edge before. It is necessary to count the number of options for such a reform.
Also, under the terms of the problem, we remember that our reform should lead to a connected graph, i.e. with one connected component. Initially, the number of groups of disconnected vertex cities can be any.
Obviously, if the number of connected components is more than two, we cannot make a connected graph as a result of adding one edge, because in this way we will connect only two groups to each other, and there are more of them. Here is an illustration of this option:
Therefore, in this simplest case, the answer is zero options.
If we are dealing with two groups, that is, two connected components, then the number of variants is calculated as follows.
First you need to find out which edges are the “bridges” - after all, when we remove these edges, we bring everything to the first, considered above option. We cannot add them back, since according to the conditions of the problem we can add only where there were no edges. Since in the end we have to get a connected graph, the added edge must connect the vertices from different components of the connectivity — make a disconnected graph connected. Two groups of N and M vertices can be connected to each other by NxM methods. Therefore, the number of reforms we get is NxMxC, where C = the number of edges, excluding those that are bridges.
The third case when we have an initially connected graph is the most complicated one. In this case, the connected component is one, but some edges may be bridges. As a result, the number of reform options is the sum of two components: the first is the number of options for removing non-bridge edges, the second is the number of options for removing edge-bridges.
The total number of edges can be calculated by the number of vertices: n * (n-1)) / 2 (where n = the number of vertices). The number of edges that can be added is calculated by subtracting the total number of existing edges. So we get the first term - the number of edges that are not bridges, multiplied by the number of edges that can be added.
When removing the “bridge”, we must connect two resulting connected components, untied vertex groups, with an edge. The number of ways to do this is equal to the product of the vertices to the right of the bridge by the number of vertices to the left of the bridge, reduced by one, since we cannot put the bridge back according to the condition of the problem.
As a result, to solve this problem, it is necessary to know the following algorithms from graph theory:
Finding the number of connected components
For the solution, you can use the depth traversal algorithm. The principle is simple - we go around recursively all the vertices, marking them as visited. As soon as we got around, we proceed to the first one, which we have not yet visited, if one exists, at the same time increasing by one the number of connected components. And so on until all the vertices run out.
Algorithm description and example: e-maxx.ru/algo/connected_components
Finding bridges
The algorithm for finding bridges is based on the search for "cycles" - alternative paths between the vertices. If no such path is found, then the edge is a bridge.
Algorithm description and example: e-maxx.ru/algo/bridge_searching
This algorithm can be modified to find the number of vertices from different sides of the bridge.
There were 621 attempts to surrender the Perestroika task, of which 137 were successful (22%).
RussianCodeCup.Ru: problem statement
RussianCodeCup.Ru: analysis of tasks
C ++ solution (pastebin)
In fact, the task is reduced to dividing the array of numbers into monotone segments so that the product of their lengths is maximal. It is clear that if a large segment can be divided into several sub-segments, then the product of lengths will be longer than the length of a large segment. This can be done when the length of the segment is more than three: if n ≥ 4, then 2 (n - 2) = 2n - 2 ≥ n.
Now you can solve the problem using dynamic programming - for each prefix, you need to calculate the optimal answer and the length of the last segment on this prefix.
To do this, go through the length of the segment you need to take (1, 2 or 3), check that the sequence does not increase or decrease on it, and choose a maximum from the appropriate options.
To restore the answer, you need to use the standard idea: restore from the end, using the information on the optimal length of the last segment for a given prefix.
In the C decision below, there is another trick. The fact is that for large “ranks” the product is obtained long enough to store it in standard data structures. Therefore, the storage and comparison of such numbers there is realized through the powers of two and three. The Java version uses BigInteger and there are no such problems.
There were 879 attempts to surrender the War task, of which 184 were successful (21%).
RussianCodeCup.Ru: problem statement
RussianCodeCup.Ru: analysis of tasks
C ++ solution (pastebin)
Java solution (bigint) (pastebin)
We show that from the conditions imposed on the length of the weapon, it follows thatd1 = d2 . Let no three numbers be equal, then d1 <d2 <d3 . By the condition (d1 + d2) 2 - 1 = (d1 + d2 + 1) (d1 + d2 - 1) is divisible by d3, since d3 is simple, one of the multipliers is divisible by d3.
Suppose, for example,(d1 + d2 + 1) is divisible by d3. From the condition d1 <d2 <d3 it follows that d1 + d2 + 1 = d3 . But then (d2 + d3) 2 -1 = (2d2 + d1 + 1) 2 -1 = 4d2 2 + 4d2 + 4d1d2 + d1 2 + 2d1. By condition, this number is divisible by d1, which means 4d2 2 + 4d2 is divisible by d1. This means either d1 = 2, or d1 = d2, or d1 = d2 + 1.
Applying similar reasoning to the third condition, we obtain that eitherd2 = 2, or d1 = d2, or d2 = d1 + 1. Of all the pairs of these conditions, only d1 = d2 and d1 = 2, d2 = 3 are compatible . But in the latter case, it is not possible to find a suitable d3. So d1 = d2.
The case is considered similarly(d1 + d2 - 1) divided by d3.
Denote d1 = d2 as p. Therefore(p + p) 2 -1 = (2p - 1) (2p + 1) is divided by d3, and since it is simple and the greatest, it can only be (2p-1) or (2p + 1). Consequently, all triples must have the form (p, p, 2p-1) or (p, p, 2p + 1). Since, under the terms of the problem, the first prime number is among the first 60000 thousand, it does not exceed 10 7 . Therefore, with such restrictions, you can apply the sieve of Eratosthenes - an algorithm for finding primes.
Sieve of Eratosthenes
The principle of the algorithm for finding primes "by Eratosthenes" is as follows. For example, you need to find prime numbers in the range from 1 to some N <= 10 7 . Create an array of N elements and fill it with the value “true”. Then we pass through it to the root from N, and everywhere, where we meet true, we cross out all multiples of it to N. At the first step, all even numbers are crossed out (because the first simple is 2), on the second step, all multiples of a triple, etc. d.
Algorithm description and example: http://habrahabr.ru/post/91112/
There were 303 attempts to surrender the Javai Weapon task, of which 126 were successful (42%).
RussianCodeCup.Ru: problem statement
RussianCodeCup.Ru: analysis of tasks
C ++ solution (pastebin)
In order to solve this problem, it is necessary to move from the concept of strings and symbols to arrays of values ​​and numbers — this will greatly simplify the solution and allow you to meet the time and memory limits.
The key idea in solving this problem is the choice of polynomial hashing for encoding words. This will allow you to move from working with strings to working with arrays and numbers, which is much faster.
The polynomial hash of the string is calculated as the sum of the products of the code of thei-th character by n to the power of i. Such hashes are often used to speed up the search for substrings in a line: if two lines are the third, their hashes are in simple arithmetic H3 = H1 + k * H2, where k = the base of the hash raised to the power of the first line.
In this case, we use the hash calculation method, where the position number will be counted from the end of the line. This is needed to recalculate the hash with a cyclic shift to the left.
For the initial position, you can easily calculate the hashes of all words, taking into account the hyphenation of words from line to line.
Now you need to make a cyclic shift one position to the left. To do this, it is necessary to recalculate the hashes of boundary words: from the left word hash, subtract the code of the outgoing character multiplied by the base of the hash to the power of the string length, add the right hash with the code of this character multiplied by the base of the hash.
It is important that checking all the hashes from all the lists for availability in the dictionary will not be easy, due to restrictions on the running time. Therefore, checks should be "cached" here - check only those words that can change - all boundary words.
Polynomial hashes
Algorithm description: http://habrahabr.ru/post/142589/
There were 109 attempts to pass the Label task, of which only 6 were successful (5%). This task was the most difficult for the participants.
RussianCodeCup.Ru: problem statement
RussianCodeCup.Ru: analysis of tasks
JAVA solution (pastebin)
The Russian Code Cup is an individual sports programming competition held annually by the Mail.Ru Group. It traditionally consists of three stages: at the beginning of the summer three qualifying rounds take place, then the best take part in the qualifying round, the first fifty winners of the qualifying round compete in the final. Personal presence will require only the last of them, the rest are held online. All finalists will be awarded with valuable gifts, and the prize for the participant who won first place will be $ 10,000. For the second and third place rely 5,000 and 3,000 dollars.In the article I will talk about the tasks that were offered to the participants and how to solve them. A brief analysis of the tasks published on the site immediately after the completion of the RCC, I will immediately try to explain the details so that the solution is clear even to novice programmers.
In total, five tasks were proposed for the tour: “Parallelepiped”, “Perestroika”, “War”, “Label”, “Javai Weapon”.
')
"Parallelepiped"
The task of the “Parallelepiped” was to check by the known lengths of twelve matches whether it is possible to glue together the frame of the parallelepiped. This task was the simplest and all the participants began to solve it.It should be remembered here that the parallelepiped is a figure, the base of which is a parallelogram - a quadrangle, whose sides are parallel in pairs. The parallelepiped has three dimensions in 12 edges - length, width and height. Therefore, it is necessary to answer the question whether there are exactly three groups of four identical numbers among the input data.
To understand this, you need to sort all the numbers and make sure that you get three groups of four identical numbers (the same at least within each group). If so, output yes; otherwise, no.
#include <iostream> #include <cstdio> using namespace std; int main() { int a[12]; while (true) { bool ex = true; for (int i = 0; i < 12; i++) cin >> a[i]; for (int i = 0; i < 12; i++) if (a[i] != 0) ex = false; if (ex) break; bool ans = true; for (int i = 0; i < 12; i++) { int k = 0; for (int j = 0; j < 12; j++) k += (a[i] == a[j]); if (k % 4 != 0) ans = false; } cout << ((ans) ? "yes" : "no") << endl; } } There were 1479 attempts to pass the “Parallelepiped” task, of which 639 were successful (43%). This task turned out to be the most accessible - the number of attempts more than twice as many as on other tasks, a high success rate.
RussianCodeCup.Ru: problem statement
RussianCodeCup.Ru: analysis of tasks
"Perestroika"
The second task was more difficult.Under the terms of the problem, there were many roads between cities. Between any two cities laid no more than one road. As a result of a certain road reform, one of the existing roads had to be destroyed, and the other, from those not previously laid, had to be built, and in such a way that in the end it could be reached from any city to any city (this could not be the case initially) . There is also a clarification that the road cannot lead from the city to it. It was necessary to count the number of options for implementing this reform.
This task assumes some knowledge from the field of graph theory. The vertices of our graph are cities, the edges are roads. In graph theory there is the concept of a graph connectedness - the presence of a path from any vertex to any. In this case, initially we have a graph of unknown connectivity, and as a result, we must obtain a graph that is necessarily connected. There is the concept of a graph connected component - this is the maximum set of interconnected vertices with respect to inclusion. Accordingly, the number of connected components is the number of vertex groups not connected to each other. For example, if there are no edges of the graph (= roads) at all, the number of connected components is equal to the number of vertices (= cities). We also introduce the concept of a “bridge” - an edge, the removal of which makes the graph incoherent, that is, divides it into unrelated parts.
So, let us remember the essence of the reform from the formulation of the problem: one existing edge (= road) is removed, and another is added to the place where there was no edge before. It is necessary to count the number of options for such a reform.
Also, under the terms of the problem, we remember that our reform should lead to a connected graph, i.e. with one connected component. Initially, the number of groups of disconnected vertex cities can be any.
Obviously, if the number of connected components is more than two, we cannot make a connected graph as a result of adding one edge, because in this way we will connect only two groups to each other, and there are more of them. Here is an illustration of this option:
Therefore, in this simplest case, the answer is zero options.
If we are dealing with two groups, that is, two connected components, then the number of variants is calculated as follows.
First you need to find out which edges are the “bridges” - after all, when we remove these edges, we bring everything to the first, considered above option. We cannot add them back, since according to the conditions of the problem we can add only where there were no edges. Since in the end we have to get a connected graph, the added edge must connect the vertices from different components of the connectivity — make a disconnected graph connected. Two groups of N and M vertices can be connected to each other by NxM methods. Therefore, the number of reforms we get is NxMxC, where C = the number of edges, excluding those that are bridges.
The third case when we have an initially connected graph is the most complicated one. In this case, the connected component is one, but some edges may be bridges. As a result, the number of reform options is the sum of two components: the first is the number of options for removing non-bridge edges, the second is the number of options for removing edge-bridges.
The total number of edges can be calculated by the number of vertices: n * (n-1)) / 2 (where n = the number of vertices). The number of edges that can be added is calculated by subtracting the total number of existing edges. So we get the first term - the number of edges that are not bridges, multiplied by the number of edges that can be added.
When removing the “bridge”, we must connect two resulting connected components, untied vertex groups, with an edge. The number of ways to do this is equal to the product of the vertices to the right of the bridge by the number of vertices to the left of the bridge, reduced by one, since we cannot put the bridge back according to the condition of the problem.
As a result, to solve this problem, it is necessary to know the following algorithms from graph theory:
- counting the number of connected components;
- finding bridges;
- count the number of vertices on each side of the bridge.
Finding the number of connected components
For the solution, you can use the depth traversal algorithm. The principle is simple - we go around recursively all the vertices, marking them as visited. As soon as we got around, we proceed to the first one, which we have not yet visited, if one exists, at the same time increasing by one the number of connected components. And so on until all the vertices run out.
Algorithm description and example: e-maxx.ru/algo/connected_components
Finding bridges
The algorithm for finding bridges is based on the search for "cycles" - alternative paths between the vertices. If no such path is found, then the edge is a bridge.
Algorithm description and example: e-maxx.ru/algo/bridge_searching
This algorithm can be modified to find the number of vertices from different sides of the bridge.
There were 621 attempts to surrender the Perestroika task, of which 137 were successful (22%).
RussianCodeCup.Ru: problem statement
RussianCodeCup.Ru: analysis of tasks
C ++ solution (pastebin)
"War"
“One small oil-bearing country was attacked by a high-tech army of another hostile country. For the defense, an army consisting of n soldiers was mobilized. Before the beginning of the decisive battle, all n soldiers lined up in front of the general. He always believed that all the soldiers in his army were of the same height, but this was not the case. The general realized that such an army was ineffective, and decided to divide it into subunits. By subdivisions, the general meant non-empty groups of soldiers standing next to each other in a line. Also, the general decided to introduce the concept of “unit capacity”, which was defined as:
- the number of soldiers in the unit, if in the ranks they stand in the order of non-increasing or non-decreasing their growth;
- 0 otherwise.
Also, the general decided that the power of the army is equal to the product of the capacities of all units.
The general wants to find such a division of the army into units so that the power of the whole army is at its maximum. Help him solve this problem. ”
In fact, the task is reduced to dividing the array of numbers into monotone segments so that the product of their lengths is maximal. It is clear that if a large segment can be divided into several sub-segments, then the product of lengths will be longer than the length of a large segment. This can be done when the length of the segment is more than three: if n ≥ 4, then 2 (n - 2) = 2n - 2 ≥ n.
Now you can solve the problem using dynamic programming - for each prefix, you need to calculate the optimal answer and the length of the last segment on this prefix.
To do this, go through the length of the segment you need to take (1, 2 or 3), check that the sequence does not increase or decrease on it, and choose a maximum from the appropriate options.
To restore the answer, you need to use the standard idea: restore from the end, using the information on the optimal length of the last segment for a given prefix.
In the C decision below, there is another trick. The fact is that for large “ranks” the product is obtained long enough to store it in standard data structures. Therefore, the storage and comparison of such numbers there is realized through the powers of two and three. The Java version uses BigInteger and there are no such problems.
There were 879 attempts to surrender the War task, of which 184 were successful (21%).
RussianCodeCup.Ru: problem statement
RussianCodeCup.Ru: analysis of tasks
C ++ solution (pastebin)
Java solution (bigint) (pastebin)
Javai Weapon
“From antiquity, each Jawai had a set of three types of weapons: a laser sword, a laser saber and a laser knife for spreading butter on bread (suddenly Javai gets hungry).
But since this weapon is Javai, and not simple, the following restrictions were imposed on the lengths of the items in the set:
The length of the knife is d1, the length of the saber is d2, the length of the sword is d3 must be prime numbers;
- d1 ≤ d2 ≤ d3;
- (d1 + d2) 2 - 1 divided by d3;
- (d2 + d3) 2 - 1 divided by d1;
- (d3 + d1) 2 - 1 divided by d2.
Dart Generics Industries sells any set of Javai weapons by its number in lexicographical order. Namely, we order all Javai sets in non-decreasing d1, with equal d1 in non-decreasing d2, and with equal d1 and d2 in increasing d3, and we number them in this order from 1 to infinity. Then for a given k you can buy the k-th set in this order.
Javai Anykey wants to buy the k-th set. Tell him the size of his weapon. ”
We show that from the conditions imposed on the length of the weapon, it follows that
Suppose, for example,
Applying similar reasoning to the third condition, we obtain that either
The case is considered similarly
Denote d1 = d2 as p. Therefore
Sieve of Eratosthenes
The principle of the algorithm for finding primes "by Eratosthenes" is as follows. For example, you need to find prime numbers in the range from 1 to some N <= 10 7 . Create an array of N elements and fill it with the value “true”. Then we pass through it to the root from N, and everywhere, where we meet true, we cross out all multiples of it to N. At the first step, all even numbers are crossed out (because the first simple is 2), on the second step, all multiples of a triple, etc. d.
Algorithm description and example: http://habrahabr.ru/post/91112/
There were 303 attempts to surrender the Javai Weapon task, of which 126 were successful (42%).
RussianCodeCup.Ru: problem statement
RussianCodeCup.Ru: analysis of tasks
C ++ solution (pastebin)
"Label"
Perhaps this task was the most difficult of all, although her explanation was probably one of the simplest.“When archaeological research is sometimes extremely interesting things. For example, during the excavations of a settlement of an ancient civilization, it was found out that its representatives, like modern people, drank drinks from bottles, on which labels with information about the drink contained in the bottle were pasted. One of these labels even survived to this day. However, before the scientists involved in decoding, quite unexpectedly, a very interesting problem appeared.
The problem was that this civilization did not use the sign of the transference. As soon as the line ended, the reading simply continued from the next line. When deciphering books, this did not cause any inconvenience, however, the label has a significant difference from the book - the label was stuck on the bottle so that a solid cylinder was obtained, on which the text was written in a circle. When reading the text, one should start reading the first line from the gluing point, after reaching the gluing point, go to the second line, then to the third line, and so on. But scientists still can not determine the place where the label was glued! So instead of text, there is only a set of lines of the same length k, consisting of letters and symbols ".", Which were used by this civilization instead of spaces.
Fortunately, besides the label itself there is a dictionary that lists all the possible words that were used by this civilization. Now, using these data, you need to determine how many gluing locations exist. More formally, you need to determine how many non-negative t <k values ​​exist such that the concatenation of all strings given to you cyclically left-shifted to t characters is a set of words from the dictionary, separated by one or several “.” Characters. In addition, you also need to output all these t values.
In order to solve this problem, it is necessary to move from the concept of strings and symbols to arrays of values ​​and numbers — this will greatly simplify the solution and allow you to meet the time and memory limits.
The key idea in solving this problem is the choice of polynomial hashing for encoding words. This will allow you to move from working with strings to working with arrays and numbers, which is much faster.
The polynomial hash of the string is calculated as the sum of the products of the code of the
In this case, we use the hash calculation method, where the position number will be counted from the end of the line. This is needed to recalculate the hash with a cyclic shift to the left.
For the initial position, you can easily calculate the hashes of all words, taking into account the hyphenation of words from line to line.
Now you need to make a cyclic shift one position to the left. To do this, it is necessary to recalculate the hashes of boundary words: from the left word hash, subtract the code of the outgoing character multiplied by the base of the hash to the power of the string length, add the right hash with the code of this character multiplied by the base of the hash.
It is important that checking all the hashes from all the lists for availability in the dictionary will not be easy, due to restrictions on the running time. Therefore, checks should be "cached" here - check only those words that can change - all boundary words.
Polynomial hashes
Algorithm description: http://habrahabr.ru/post/142589/
There were 109 attempts to pass the Label task, of which only 6 were successful (5%). This task was the most difficult for the participants.
RussianCodeCup.Ru: problem statement
RussianCodeCup.Ru: analysis of tasks
JAVA solution (pastebin)
- Analysis of tasks from the second qualification
Analysis of tasks from the third qualification
Aliyev Rauf
Director of Research and Education
Project Manager Russian Code Cup
Mail.Ru Group
Source: https://habr.com/ru/post/144793/
All Articles