April 16, 2014 at 16:19Seven most interesting tasks of RCC for all years according to Andrey Stankevich
In anticipation of the first qualifying round of the Russian Code Cup, which will take place on April 19, we decided to tell you about the seven most interesting RCC tasks in the history of the championship, according to Andrei Stankevich, associate professor of the ITMO department of computer technology, winner of the Presidential Award in the field of education, winner of the award ACM-ICPC Founder's Award, winner of the IBM Special Coaching Award.
We remind you that in order to take part in the Russian Code Cup, you need to register on the website http://russiancodecup.ru/ (registration will be open before the third qualification round begins).
2011, Final Round, “B” Inverse Turtle Challenge
2011, Final Round, “D” Archiver
2012, 2nd qualifying round, “C” Tetrahedron
2012, Qualifying round, “F” Prince
2012, Final round, “E” Shuffle the deck
2013, Qualifying round, “E” Lasers
2013 year, Final round, “D” Robot
1) 2011, Final Round, “B” Inverse Turtle Problem
Analysis:
In this problem, it was required to construct a labyrinth for a given number k, in which the number of paths from the upper left to the lower right cell would be equal to k, provided which is allowed to move only to the right and down.
Note the following. Suppose we have two labyrinths in which the number of ways to get from the upper left to the lower right cells is a and b, respectively.
Then, placing them in parallel, as shown in the figure, we can get a maze for which there are a + b ways to get from the upper left to the lower right cell. And placing them sequentially - get a maze in which ab paths.
Note that there are two paths in an empty 2 × 2 maze, and one path in a 1 × 1 maze. Therefore, by expanding the number k into a binary number system and using the described method, we can get a maze with k paths from the upper left to the lower right cell.
An example of such a maze for k = 19 is shown in the figure.
Note that for each discharge of k, 5 cells are required horizontally, and 2 60 > 10 18, therefore, the above scheme allows you to create a labyrinth with a size of no more than 300 × 300, which is what is required in the problem statement.
2) 2011, Final Round, “D” Archiver
Analysis:
There are at least two different approaches to this task: dynamic programming or a greedy algorithm.
Imagine the process of archiving a sequence in the form of a tree: each symbol of each of the intermediate sequences will be the top of the tree, the children of the vertex will be two characters that are “glued” during the archiving into the given one. Initial numbers are written in the leaves, and the task is to write numbers to all intermediate vertices, while the penalty for archiving is equal to the number of vertices for which different numbers are written in children.
The solution using dynamic programming is as follows: at each vertex u we will store the minimum total penalty p [u] [x] for the subtree if we write the number x at this vertex. Note that at the vertex it is meaningful to write down only the number that occurs in one of the leaves in the subtree, so the total number of options that should be considered is O (n log n).
Recalculation is carried out as follows: consider the vertex u with children v and w. Suppose we plan to write the value of x. If both p [v] [x] and p [w] [x] are defined, then one of the options to put x in u is to put x in both children, the price of this option is p [v] [x] + p [w ] [x]. There is also the option to put x in only one child. Suppose we plan to put x in v, then the cost of this option is p [v] [x] + minp [w] + 1, where minp [w] is the minimum value of p [w] [y] for all y.
An alternative to solving using DP is a greedy solution: for each vertex we will keep a list of all possible values, putting one of them at the top, we will get the minimum penalty in the subtree. It turns out that in order to find the optimal set for a vertex, it is enough to try to put only optimal values in its children. Moreover, if the lists of optimal values for children intersect, then you must take one of these numbers. If they do not intersect, then any of the meanings of each of the children will do.
We will leave the proof of the correctness of the presented algorithm as an exercise.
3) 2012, 2nd qualification round, “C” Tetrahedron
Analysis:
Let me remind you that a tetrahedron is a polyhedron whose faces are four triangles (in other words, a triangular pyramid).
It all starts with the fact that we sort out the possible matches of the edges of the tetrahedron. We denote the desired tetrahedron as ABCD. He has six ribs: AB, AC, AD, BC, BD and CD. Let's go over all 6! = 720 options, which match corresponds to which edge. Now it remains to verify that the corresponding tetrahedron exists.
How to check the existence of a tetrahedron? There are at least three solutions here.
The first solution is based on calculating the volume of the tetrahedron. The simplest solution is to find a formula for calculating the volume of a tetrahedron by its faces. This task in itself is not easy, I will give the formula here:
Accordingly, if the right-hand side of the equality turns out to be negative or it is impossible to construct triangles in the faces (triangle inequality), then the tetrahedron will not converge.
For those interested , this formula is displayed here .
The second approach to solving the problem is geometric. First, make sure that ABC and BCD exist. Now try to make a tetrahedron. It is clear that when constructing a three-dimensional figure, a problem can arise only with the last edge - it can turn out to be either too long or too short. Therefore, in this solution, it is proposed to find the length range of the last rib.
There are two limiting options for placing faces, in which the tetrahedron turns into a flat figure. The first - when the faces are rotated 180 degrees relative to each other (CAB and CBD), and the second - when they are “folded” and form a “zero angle” (CA'D and CDB). All permissible positions of faces relative to each other are in the range between these boundary ones. The last edge (AD) reaches its greatest length in the first limiting variant (AD), and the shortest one in the last (A'D). Consequently, a tetrahedron will exist if this length of the last edge fits into the range we found (from A'D to AD).
In order to find the distance between points A and D and A 'and D, we first find their coordinates, taking for zero one of the vertices common to the triangles, and draw the abscissa axis through one of the edges emanating from this vertex. Finding the coordinates of all the other vertices in this coordinate system is quite simple: through the aspect ratios and cosines of the angles, we determine the positions of the vertices in polar coordinates (angle, distance), and then translate them into a Cartesian coordinate system. Knowing the coordinates of the vertices, it is very simple to calculate the maximum and minimum distances between unconnected vertices.
The program should check whether the length of the remaining face fits into the specified ranges. If so, then a tetrahedron of such lengths can be "assembled".
The third method is also geometric.First you need to check the existence of all triangles with the indicated sides. If at least one triangle cannot be constructed according to the indicated values of the sides, then the tetrahedron cannot be built either. To check, it is necessary to check the inequality of a non-degenerate triangle: any of its sides must be strictly less than the sum of the other two.
In many cases, the solution was limited to this; meanwhile, there are situations when triangles with the indicated sides can be constructed, and it is impossible to assemble a tetrahedron from them.
For example, if we have faces (100,100,2,101,100,2), then the triangles (100,100,2) and (101,100,2) formally satisfy the triangle inequality, but it is impossible to add a tetrahedron from such triangles. From the figure, we see that the edge AC is almost parallel to AB, which means that the distance from D to C will hardly change for any inclination of the face ABD relative to AB, from which we can conclude that DB is almost perpendicular to BC. In this case, the DC can be approximately estimated as the root of the sum of the squares of the legs, that is, the DC should be approximately 10, and not 2 at all, as we assumed in the condition.
Therefore, in addition to checking for triangles in the faces, it is necessary to perform an additional test for trihedral angles. There are two necessary and sufficient conditions for the existence of a trihedral angle:
The flat angle is found through the cosine theorem for the triangle.
In total, 1088 decisions were aimed at checking, of which only 74 (7%) were correct. 8% of Russian Code Cup QR2 participants completed this task. The first decision came from a participant with the nickname AVictor 30 minutes after the start of the round.
4) 2012 Qualifying round, “F” Prince
Analysis:
In this task, it is necessary to find the minimum time for which the prince will fall to the princess along the one-dimensional corridor without falling into any trap. Known schedule, size and location of the appearance / disappearance of traps, as well as the speed of movement of the prince. Since the corridor is one-dimensional, the prince can move either towards the princess, or away from her, or not move anywhere at all. Obviously, there are situations when there is no way out, and the prince does not get to the princess - in this case, you need to withdraw Impossible.
The solution to this problem is to start by depicting traps on a plane where the x coordinate is the position in the corridor and the y coordinate is time. Now the problem can be reformulated in terms of this plane: it is required to get from the point (0, 0) to the point (x, y) with the minimum y, while it is allowed to move vertically up (to stand still), diagonally right up and left up (move along the corridor) and it is forbidden to enter certain rectangles (traps). It is allowed to be on the border of the rectangle.
The optimal path in such a task will consist of many similar parts, each of which will consist of movement along one of the diagonals to the coordinate corresponding to the border of one of the rectangles, followed by vertical upward movement to the upper corner of this rectangle. Thus, the key points are the upper left and upper right corners of each rectangle and it is necessary to find out about them whether it is possible to get there.
When moving diagonally, we will support many rectangles located above the current position. Since it is possible to be located at the border of rectangles, then rectangles starting or ending at the current “corridor” coordinate will not be taken into account. Rectangles will be stored in a set arranged on the bottom edge. Such a set will be called a slice. To store the set, you can use data structures like red-black or Cartesian trees or priority queues. The lower edge of the lower rectangle will be called the edge of the slice. If the slice does not contain rectangles, then we will consider its edge to be infinity.
Since the time coordinate increases with any movement, we will consider the angles of the rectangles in non-decreasing order of this coordinate. Considering the next angle, we will try to move from it diagonally in both directions. The movement is carried out at the coordinates corresponding to the boundaries of the rectangles. Reaching the next coordinate, we check whether it is possible, moving vertically upwards, to get into the corresponding upper corner of a rectangle. An angle can be reached if this angle is not higher than the edge of the current slice. It is also necessary to check that the movement does not rest against the edge of one of the rectangles starting in this coordinate. If you managed to reach the door x coordinate, then you need to update the current answer. If, when moving from one coordinate to another, the edge of the cut was exceeded,
Having examined all the corners one by one and stepping to both sides of each of them, we will find the minimum possible answer or information that the door is not reachable. The described algorithm performs O (n2 log n) operations, since it is necessary to go from each of the O (n) angles along the diagonal O (n) of different coordinates and check the O (n) rectangles. Also, for each angle it is necessary to perform O (n log n) operations to maintain the slice, since it is necessary to add and remove O (n) rectangles from the slice.
The following are possible options for passing rectangles that you must remember to process.
And
at the same time, on the next test it is impossible to catch the door.
This task is also not an easy one - only 23 people solved it, the first was Yegor Kulikov at 100: 18. Here it is worth noting Epifanova Vladislav, who sent a solution to this problem, the last for him, 2 minutes before the end of the tour. Vladislav took first place both in qualification and in the qualifying round.
5) 2012, Final round, “E” Shuffle the deck
Analysis: Sergey MELNIKOV , student of NRU ITMO, talks
about the task of shuffling the deck .
In this problem, you need to think over the deck mixing mechanism, which allows you to mix it perfectly (for the minimum number of moves of the card blocks from the middle to the end of the deck (that is, make sure that no two identical cards go one after the other), or report that it is impossible to mix the deck perfectly . Initially, the deck is sorted by non-decreasing dignity. Given the number of different advantages of the cards, the order of the cards in the deck, the number of decks.
Detailed statement of the problem
Let us call a conflict a situation in which two identical cards stand in a row:
We call the body the initial sequence of cards, which we will gradually reduce by transferring the cards to the tail. Tailwill be formed in such a way that the cards in it do not form conflicts.
We transform the original sequence into a sequence of conflicts and will work with the new sequence. We will call the color of the conflict the number written on the cards that form it. Each time transferring a segment of cards to the end of the deck, we will choose its ends inside conflicts.
We denote the number of conflicts by K. Since one move operation removes no more than two conflicts, it is impossible to solve the problem faster than in ⌈K / 2⌉ operations (here and below in the description there are constructions ⌋ ... ⌋ and ⌈ ... ⌉ - this is rounding down and up, respectively )
We denote by M the maximum number of conflicts of one color and we will call these conflicts themselves “maximum”. We learn to solve the problem in the case when M = /K / 2⌉.
I also remind you that according to the conditions of the task, the deck is sorted by non-decreasing dignity.
For example, in deck 1122333344, the number M will be 3 (three conflicts 33), the total number of conflicts - 6. In this case, M = ⌈K / 2⌉.
In this case (not an example), there are two options:
The solutions for these cases are optimal, since the lower limit of the number of operations ⌈K / 2⌉ is reached. In total, we are able to optimally solve the problem when the number of “maximum” conflicts is half of all conflicts (with rounding up). We will call such a case basic.
Now we classify the initial situations by the maximum number of cards of the same value in a row. We will call these cards maximum and denote their number as Q.
Now, each time, we will delete the last pair of conflicts that can be deleted (the last two conflicts are of different colors) (C 1 , C 2 ). If in the process we get into the base case, then we will solve as we solve it. If there are no more conflicts left, then the problem is solved.
We prove that no new conflicts will arise. Consider the color of the last conflict Z, we will transfer pairs of conflicts (X, Z) until Z runs out, while Z remains at the end, and we get the tail Z (X 1 , Z) (X 2 , Z) .... If the Z-conflicts run out, then there will be a transition to (X, Y) conflicts, that is, the pair (X k , Z) (X k + 1 , Y), for X k + 1 ≠ Z.
In the transition to the base case, there will be no conflict, because after the transfer of the pair (X, Z), neither X nor Z can become maximal (M). Since M ≠ Z, either Z ended and the conflict (X, Z) (Z, ...) does not arise, or Z is after M, that is, we get the continuation (X, Z) (M, Z).
Since we remove a couple of conflicts at every step, or use the base case, the solution constructed is optimal and works for ⌈K / 2⌉ operations.
You may notice that there is no need to store information about which numbers and in what order are written in the tail, since there are no conflicts. The sequence of values can be maintained using the Cartesian tree with an implicit key, and the total operating time will be O (N log N). Also, if at some point we determine that there are no conflicts at the end of the body, then we can reduce the length of the body and, accordingly, increase the tail. You can consider all the cases when a segment moves, and make sure that the body will always look like: the prefix of the original array with no more than two cut sub-segments. Based on this fact, it is possible to implement a solution in O (n), but to solve this problem in these restrictions this is not required.
The task "Shuffling cards" was solved only by Eugene KAPUN
6) 2013, Qualifying round, “E” Lasers
Analysis:
The main idea of the solution is binary search by answer. We fix the maximum deflection angle α and check the existence of a solution with such an answer. To do this, we reduce the problem to finding a path in the graph.
Denote the points defined in the condition as P 1 , P 2 , ..., P n . We construct a graph of n (n - 1) vertices, where each vertex is an ordered pair of different points. Draw the edges from the pair (i, j) to the pair (j, k) if the angle between the vectors P i P j and P j P k does not exceed α. In the constructed graph, no more than n 3ribs. Now, if in such a graph there exists a path from a vertex of the form (1, i) to a vertex of the form (j, 1), then with such α the experiment can be carried out. You can verify the existence of a path using any algorithm for finding a path in a graph.
Thus, one iteration of the binary search works for O (n 3 ), which means that the whole algorithm can be implemented in O (n 3 log (1 / ε)) or, if you notice that the search space is actually discrete (we are only interested no more than n 3 angles), then this algorithm can be implemented in O (n 3 log (n 3 )).
7) 2013, Final round, “D” Robot
Analysis:
In this problem, it was necessary to find the expectation of the shortest path length from one corner of the field to another. At the same time, some cells of the field were painted white, and when a robot hit such a cell, it was rearranged into a random white field cell.
We will examine in more detail how the optimal strategy for choosing a path is arranged. For each cell in the field, one can calculate the expectation of the number of moves necessary to get into the lower right cell. In this case, the answer will correspond to the distance that is recorded in the upper left cell. How to calculate these values? Consider a specific cell and all neighboring cells. If the neighboring cell is painted black, then the answer for the cell will be at least (1 + the value that is recorded in the neighboring cell). If the cell has a white neighbor, then the answer for it is at least (1 + arithmetic average of the responses for all white cells).
It is clear that if the robot gets into the same cell twice, then there is an optimal strategy in which the next move is the same in both cases. If this is not so, then on some of the moves the robot did the wrong thing and went into the cage with a large expectation of the number of moves to the end, which means that the strategy can be improved. There are two fundamentally different actions that a robot can do while in a certain cell. He can go directly to the lower right corner along the black cells (if such a path exists), or he can go to some white cell. Obviously, among all the white cells that you can go to, you should choose the closest one.
We calculate for each cell the distance to the lower right on the black cells and the distance to the nearest white. Note that for any white cell, the distance to the nearest white cell is no more than two. Now we divide all the white cells into two sets - those from which the robot must immediately go to the lower right cell, and those from which the robot must go to the next white one. When such a partition is made, it is not difficult to calculate the answer. Having written the recurrence relation for the average response for all white cells, we find it. This will be a fraction with a denominator of no more than the number of white cells. Now the answer is min (the distance along the black squares to the lower right, the distance to the nearest white one + the average answer for all white ones).
It remains to learn how to find the correct division of white cells into sets. Sort all the white cells according to the criterion (the distance to the lower right on black - the distance to the nearest white). It is argued that the optimal partition is the following - from all the cells of a certain prefix of the sorted array, you must go immediately to the lower right cell, and from the rest to the nearest white one. This fact is easily proved by the opposite method (let the optimal partition have a different look; consider the average answer for white cells, see that some cells can be moved from one set to another without worsening the answer, but bringing the partition to the desired form).
As a result, the solution boils down to the following. We calculate the distances that were discussed earlier for all cells. Sort the white cells. We sort through the partition into sets, each time recounting the average answer for white cells for O (1). The answer to the problem is the minimum of the distance in black cells and the distance to the nearest white cell + the average response for white cells. If you sort the white cells by counting, then the total complexity of the solution will be O (total number of cells).
Which of the tasks did you find most interesting?
Announcement of the first qualifying round on April 19.
We remind you that in order to take part in the Russian Code Cup, you need to register on the website http://russiancodecup.ru/ (registration will be open before the third qualification round begins).
2011, Final Round, “B” Inverse Turtle Challenge
2011, Final Round, “D” Archiver
2012, 2nd qualifying round, “C” Tetrahedron
2012, Qualifying round, “F” Prince
2012, Final round, “E” Shuffle the deck
2013, Qualifying round, “E” Lasers
2013 year, Final round, “D” Robot
1) 2011, Final Round, “B” Inverse Turtle Problem
Analysis:
In this problem, it was required to construct a labyrinth for a given number k, in which the number of paths from the upper left to the lower right cell would be equal to k, provided which is allowed to move only to the right and down.
Note the following. Suppose we have two labyrinths in which the number of ways to get from the upper left to the lower right cells is a and b, respectively.
Then, placing them in parallel, as shown in the figure, we can get a maze for which there are a + b ways to get from the upper left to the lower right cell. And placing them sequentially - get a maze in which ab paths.
Note that there are two paths in an empty 2 × 2 maze, and one path in a 1 × 1 maze. Therefore, by expanding the number k into a binary number system and using the described method, we can get a maze with k paths from the upper left to the lower right cell.
An example of such a maze for k = 19 is shown in the figure.
Note that for each discharge of k, 5 cells are required horizontally, and 2 60 > 10 18, therefore, the above scheme allows you to create a labyrinth with a size of no more than 300 × 300, which is what is required in the problem statement.
2) 2011, Final Round, “D” Archiver
Analysis:
There are at least two different approaches to this task: dynamic programming or a greedy algorithm.
Imagine the process of archiving a sequence in the form of a tree: each symbol of each of the intermediate sequences will be the top of the tree, the children of the vertex will be two characters that are “glued” during the archiving into the given one. Initial numbers are written in the leaves, and the task is to write numbers to all intermediate vertices, while the penalty for archiving is equal to the number of vertices for which different numbers are written in children.
The solution using dynamic programming is as follows: at each vertex u we will store the minimum total penalty p [u] [x] for the subtree if we write the number x at this vertex. Note that at the vertex it is meaningful to write down only the number that occurs in one of the leaves in the subtree, so the total number of options that should be considered is O (n log n).
Recalculation is carried out as follows: consider the vertex u with children v and w. Suppose we plan to write the value of x. If both p [v] [x] and p [w] [x] are defined, then one of the options to put x in u is to put x in both children, the price of this option is p [v] [x] + p [w ] [x]. There is also the option to put x in only one child. Suppose we plan to put x in v, then the cost of this option is p [v] [x] + minp [w] + 1, where minp [w] is the minimum value of p [w] [y] for all y.
An alternative to solving using DP is a greedy solution: for each vertex we will keep a list of all possible values, putting one of them at the top, we will get the minimum penalty in the subtree. It turns out that in order to find the optimal set for a vertex, it is enough to try to put only optimal values in its children. Moreover, if the lists of optimal values for children intersect, then you must take one of these numbers. If they do not intersect, then any of the meanings of each of the children will do.
We will leave the proof of the correctness of the presented algorithm as an exercise.
3) 2012, 2nd qualification round, “C” Tetrahedron
Analysis:
Let me remind you that a tetrahedron is a polyhedron whose faces are four triangles (in other words, a triangular pyramid).
It all starts with the fact that we sort out the possible matches of the edges of the tetrahedron. We denote the desired tetrahedron as ABCD. He has six ribs: AB, AC, AD, BC, BD and CD. Let's go over all 6! = 720 options, which match corresponds to which edge. Now it remains to verify that the corresponding tetrahedron exists.
How to check the existence of a tetrahedron? There are at least three solutions here.
The first solution is based on calculating the volume of the tetrahedron. The simplest solution is to find a formula for calculating the volume of a tetrahedron by its faces. This task in itself is not easy, I will give the formula here:
Accordingly, if the right-hand side of the equality turns out to be negative or it is impossible to construct triangles in the faces (triangle inequality), then the tetrahedron will not converge.
For those interested , this formula is displayed here .
The second approach to solving the problem is geometric. First, make sure that ABC and BCD exist. Now try to make a tetrahedron. It is clear that when constructing a three-dimensional figure, a problem can arise only with the last edge - it can turn out to be either too long or too short. Therefore, in this solution, it is proposed to find the length range of the last rib.
There are two limiting options for placing faces, in which the tetrahedron turns into a flat figure. The first - when the faces are rotated 180 degrees relative to each other (CAB and CBD), and the second - when they are “folded” and form a “zero angle” (CA'D and CDB). All permissible positions of faces relative to each other are in the range between these boundary ones. The last edge (AD) reaches its greatest length in the first limiting variant (AD), and the shortest one in the last (A'D). Consequently, a tetrahedron will exist if this length of the last edge fits into the range we found (from A'D to AD).
In order to find the distance between points A and D and A 'and D, we first find their coordinates, taking for zero one of the vertices common to the triangles, and draw the abscissa axis through one of the edges emanating from this vertex. Finding the coordinates of all the other vertices in this coordinate system is quite simple: through the aspect ratios and cosines of the angles, we determine the positions of the vertices in polar coordinates (angle, distance), and then translate them into a Cartesian coordinate system. Knowing the coordinates of the vertices, it is very simple to calculate the maximum and minimum distances between unconnected vertices.
The program should check whether the length of the remaining face fits into the specified ranges. If so, then a tetrahedron of such lengths can be "assembled".
The third method is also geometric.First you need to check the existence of all triangles with the indicated sides. If at least one triangle cannot be constructed according to the indicated values of the sides, then the tetrahedron cannot be built either. To check, it is necessary to check the inequality of a non-degenerate triangle: any of its sides must be strictly less than the sum of the other two.
In many cases, the solution was limited to this; meanwhile, there are situations when triangles with the indicated sides can be constructed, and it is impossible to assemble a tetrahedron from them.
For example, if we have faces (100,100,2,101,100,2), then the triangles (100,100,2) and (101,100,2) formally satisfy the triangle inequality, but it is impossible to add a tetrahedron from such triangles. From the figure, we see that the edge AC is almost parallel to AB, which means that the distance from D to C will hardly change for any inclination of the face ABD relative to AB, from which we can conclude that DB is almost perpendicular to BC. In this case, the DC can be approximately estimated as the root of the sum of the squares of the legs, that is, the DC should be approximately 10, and not 2 at all, as we assumed in the condition.
Therefore, in addition to checking for triangles in the faces, it is necessary to perform an additional test for trihedral angles. There are two necessary and sufficient conditions for the existence of a trihedral angle:
- the sum of the flat angles of the trihedral angle must be less than 360 degrees,
- each plane angle of the trihedral angle must be less than the sum of two other plane angles.
The flat angle is found through the cosine theorem for the triangle.
In total, 1088 decisions were aimed at checking, of which only 74 (7%) were correct. 8% of Russian Code Cup QR2 participants completed this task. The first decision came from a participant with the nickname AVictor 30 minutes after the start of the round.
4) 2012 Qualifying round, “F” Prince
Analysis:
In this task, it is necessary to find the minimum time for which the prince will fall to the princess along the one-dimensional corridor without falling into any trap. Known schedule, size and location of the appearance / disappearance of traps, as well as the speed of movement of the prince. Since the corridor is one-dimensional, the prince can move either towards the princess, or away from her, or not move anywhere at all. Obviously, there are situations when there is no way out, and the prince does not get to the princess - in this case, you need to withdraw Impossible.
The solution to this problem is to start by depicting traps on a plane where the x coordinate is the position in the corridor and the y coordinate is time. Now the problem can be reformulated in terms of this plane: it is required to get from the point (0, 0) to the point (x, y) with the minimum y, while it is allowed to move vertically up (to stand still), diagonally right up and left up (move along the corridor) and it is forbidden to enter certain rectangles (traps). It is allowed to be on the border of the rectangle.
The optimal path in such a task will consist of many similar parts, each of which will consist of movement along one of the diagonals to the coordinate corresponding to the border of one of the rectangles, followed by vertical upward movement to the upper corner of this rectangle. Thus, the key points are the upper left and upper right corners of each rectangle and it is necessary to find out about them whether it is possible to get there.
When moving diagonally, we will support many rectangles located above the current position. Since it is possible to be located at the border of rectangles, then rectangles starting or ending at the current “corridor” coordinate will not be taken into account. Rectangles will be stored in a set arranged on the bottom edge. Such a set will be called a slice. To store the set, you can use data structures like red-black or Cartesian trees or priority queues. The lower edge of the lower rectangle will be called the edge of the slice. If the slice does not contain rectangles, then we will consider its edge to be infinity.
Since the time coordinate increases with any movement, we will consider the angles of the rectangles in non-decreasing order of this coordinate. Considering the next angle, we will try to move from it diagonally in both directions. The movement is carried out at the coordinates corresponding to the boundaries of the rectangles. Reaching the next coordinate, we check whether it is possible, moving vertically upwards, to get into the corresponding upper corner of a rectangle. An angle can be reached if this angle is not higher than the edge of the current slice. It is also necessary to check that the movement does not rest against the edge of one of the rectangles starting in this coordinate. If you managed to reach the door x coordinate, then you need to update the current answer. If, when moving from one coordinate to another, the edge of the cut was exceeded,
Having examined all the corners one by one and stepping to both sides of each of them, we will find the minimum possible answer or information that the door is not reachable. The described algorithm performs O (n2 log n) operations, since it is necessary to go from each of the O (n) angles along the diagonal O (n) of different coordinates and check the O (n) rectangles. Also, for each angle it is necessary to perform O (n log n) operations to maintain the slice, since it is necessary to add and remove O (n) rectangles from the slice.
The following are possible options for passing rectangles that you must remember to process.
And
at the same time, on the next test it is impossible to catch the door.
This task is also not an easy one - only 23 people solved it, the first was Yegor Kulikov at 100: 18. Here it is worth noting Epifanova Vladislav, who sent a solution to this problem, the last for him, 2 minutes before the end of the tour. Vladislav took first place both in qualification and in the qualifying round.
5) 2012, Final round, “E” Shuffle the deck
Analysis: Sergey MELNIKOV , student of NRU ITMO, talks
about the task of shuffling the deck .
In this problem, you need to think over the deck mixing mechanism, which allows you to mix it perfectly (for the minimum number of moves of the card blocks from the middle to the end of the deck (that is, make sure that no two identical cards go one after the other), or report that it is impossible to mix the deck perfectly . Initially, the deck is sorted by non-decreasing dignity. Given the number of different advantages of the cards, the order of the cards in the deck, the number of decks.
Detailed statement of the problem
Let us call a conflict a situation in which two identical cards stand in a row:
We call the body the initial sequence of cards, which we will gradually reduce by transferring the cards to the tail. Tailwill be formed in such a way that the cards in it do not form conflicts.
We transform the original sequence into a sequence of conflicts and will work with the new sequence. We will call the color of the conflict the number written on the cards that form it. Each time transferring a segment of cards to the end of the deck, we will choose its ends inside conflicts.
We denote the number of conflicts by K. Since one move operation removes no more than two conflicts, it is impossible to solve the problem faster than in ⌈K / 2⌉ operations (here and below in the description there are constructions ⌋ ... ⌋ and ⌈ ... ⌉ - this is rounding down and up, respectively )
We denote by M the maximum number of conflicts of one color and we will call these conflicts themselves “maximum”. We learn to solve the problem in the case when M = /K / 2⌉.
I also remind you that according to the conditions of the task, the deck is sorted by non-decreasing dignity.
For example, in deck 1122333344, the number M will be 3 (three conflicts 33), the total number of conflicts - 6. In this case, M = ⌈K / 2⌉.
In this case (not an example), there are two options:
- K is even (as in the example). We color all conflicts preceding the “maximum” in color A, the “maximum” conflicts in color B, and the subsequent ones in color C. | A | + | B | + | C | = | K |, therefore | A | + | C | = | B | = M. In the above example, the color scheme for 1122333344 will be AABBBC. We will eliminate conflicts in pairs: first, pairs (B, C), then when there are no such pairs left, pairs (A, B). Note that the tail will have the form (B, C) * (A, B) *, where * is one or more repetitions. In our example, these are: 1122333344 (AABBC) -> 1122333-4.34 (AAB) -> 1-2333-4.3412 (BB) (hyphens indicate where the cards were taken from before being transferred to the tail. The dot is the body and tail separator).Obviously, two conflicts of the same color do not go in a row. When paired with the body, everything will be fine too: if | C | > 0, then the last card with the value C will remain in place, and the tail will begin with B. If, however, | C | = 0, then the tail has the form (A, B) *, while the last card with the value of B will remain in place.
- K is odd. Apply a similar coloring. If there is at least one card of color A, then we reduce the problem to the previous case by adding a virtual card and A-conflict to the beginning. If there is a color C card, then add a new virtual card and C-conflict to the end, again reducing to the previous case.
The solutions for these cases are optimal, since the lower limit of the number of operations ⌈K / 2⌉ is reached. In total, we are able to optimally solve the problem when the number of “maximum” conflicts is half of all conflicts (with rounding up). We will call such a case basic.
Now we classify the initial situations by the maximum number of cards of the same value in a row. We will call these cards maximum and denote their number as Q.
- Q = 0. There are no conflicts, nothing needs to be done.
- If Q> ⌈N / 2⌉, then the problem has no solution. In this case, we have less than Q − 1 not maximum cards, which is not enough to separate cards of maximum value.
- Q = ⌈N / 2⌉. In this case, not the maximum cards are enough, but every second card should be maximum. Having painted the cards in three colors we get:
- A A-cards reaching to the maximum,
- b = Q B-cards that are maximal
- c C-cards after the maximum.
- Moreover, we assume that all A- and C-cards form conflicts. Consider the following cases:
- a = 0. Consequently, c = N - Q = ⌊N / 2⌋, and then b differs from c by no more than one, that is, we reduced it to the base case.
- c = 0 . Similar to the previous case.
- a> 0, b> 0 Among A-cards a - 1 conflict, among B: b - 1, among C: c - 1. (a - 1) + (c - 1) = N - Q - 2, differs from Q - 1 is not more than one, which means that this is a basic case.
- M <⌊ (N + 1) / 2 ⌋. If you can add a certain number of virtual conflicts (conflicts between cards with different values), so that the problem reduces to the base case, then we add them and solve it as the base case.
Now, each time, we will delete the last pair of conflicts that can be deleted (the last two conflicts are of different colors) (C 1 , C 2 ). If in the process we get into the base case, then we will solve as we solve it. If there are no more conflicts left, then the problem is solved.
We prove that no new conflicts will arise. Consider the color of the last conflict Z, we will transfer pairs of conflicts (X, Z) until Z runs out, while Z remains at the end, and we get the tail Z (X 1 , Z) (X 2 , Z) .... If the Z-conflicts run out, then there will be a transition to (X, Y) conflicts, that is, the pair (X k , Z) (X k + 1 , Y), for X k + 1 ≠ Z.
In the transition to the base case, there will be no conflict, because after the transfer of the pair (X, Z), neither X nor Z can become maximal (M). Since M ≠ Z, either Z ended and the conflict (X, Z) (Z, ...) does not arise, or Z is after M, that is, we get the continuation (X, Z) (M, Z).
Since we remove a couple of conflicts at every step, or use the base case, the solution constructed is optimal and works for ⌈K / 2⌉ operations.
You may notice that there is no need to store information about which numbers and in what order are written in the tail, since there are no conflicts. The sequence of values can be maintained using the Cartesian tree with an implicit key, and the total operating time will be O (N log N). Also, if at some point we determine that there are no conflicts at the end of the body, then we can reduce the length of the body and, accordingly, increase the tail. You can consider all the cases when a segment moves, and make sure that the body will always look like: the prefix of the original array with no more than two cut sub-segments. Based on this fact, it is possible to implement a solution in O (n), but to solve this problem in these restrictions this is not required.
The task "Shuffling cards" was solved only by Eugene KAPUN
6) 2013, Qualifying round, “E” Lasers
Analysis:
The main idea of the solution is binary search by answer. We fix the maximum deflection angle α and check the existence of a solution with such an answer. To do this, we reduce the problem to finding a path in the graph.
Denote the points defined in the condition as P 1 , P 2 , ..., P n . We construct a graph of n (n - 1) vertices, where each vertex is an ordered pair of different points. Draw the edges from the pair (i, j) to the pair (j, k) if the angle between the vectors P i P j and P j P k does not exceed α. In the constructed graph, no more than n 3ribs. Now, if in such a graph there exists a path from a vertex of the form (1, i) to a vertex of the form (j, 1), then with such α the experiment can be carried out. You can verify the existence of a path using any algorithm for finding a path in a graph.
Thus, one iteration of the binary search works for O (n 3 ), which means that the whole algorithm can be implemented in O (n 3 log (1 / ε)) or, if you notice that the search space is actually discrete (we are only interested no more than n 3 angles), then this algorithm can be implemented in O (n 3 log (n 3 )).
7) 2013, Final round, “D” Robot
Analysis:
In this problem, it was necessary to find the expectation of the shortest path length from one corner of the field to another. At the same time, some cells of the field were painted white, and when a robot hit such a cell, it was rearranged into a random white field cell.
We will examine in more detail how the optimal strategy for choosing a path is arranged. For each cell in the field, one can calculate the expectation of the number of moves necessary to get into the lower right cell. In this case, the answer will correspond to the distance that is recorded in the upper left cell. How to calculate these values? Consider a specific cell and all neighboring cells. If the neighboring cell is painted black, then the answer for the cell will be at least (1 + the value that is recorded in the neighboring cell). If the cell has a white neighbor, then the answer for it is at least (1 + arithmetic average of the responses for all white cells).
It is clear that if the robot gets into the same cell twice, then there is an optimal strategy in which the next move is the same in both cases. If this is not so, then on some of the moves the robot did the wrong thing and went into the cage with a large expectation of the number of moves to the end, which means that the strategy can be improved. There are two fundamentally different actions that a robot can do while in a certain cell. He can go directly to the lower right corner along the black cells (if such a path exists), or he can go to some white cell. Obviously, among all the white cells that you can go to, you should choose the closest one.
We calculate for each cell the distance to the lower right on the black cells and the distance to the nearest white. Note that for any white cell, the distance to the nearest white cell is no more than two. Now we divide all the white cells into two sets - those from which the robot must immediately go to the lower right cell, and those from which the robot must go to the next white one. When such a partition is made, it is not difficult to calculate the answer. Having written the recurrence relation for the average response for all white cells, we find it. This will be a fraction with a denominator of no more than the number of white cells. Now the answer is min (the distance along the black squares to the lower right, the distance to the nearest white one + the average answer for all white ones).
It remains to learn how to find the correct division of white cells into sets. Sort all the white cells according to the criterion (the distance to the lower right on black - the distance to the nearest white). It is argued that the optimal partition is the following - from all the cells of a certain prefix of the sorted array, you must go immediately to the lower right cell, and from the rest to the nearest white one. This fact is easily proved by the opposite method (let the optimal partition have a different look; consider the average answer for white cells, see that some cells can be moved from one set to another without worsening the answer, but bringing the partition to the desired form).
As a result, the solution boils down to the following. We calculate the distances that were discussed earlier for all cells. Sort the white cells. We sort through the partition into sets, each time recounting the average answer for white cells for O (1). The answer to the problem is the minimum of the distance in black cells and the distance to the nearest white cell + the average response for white cells. If you sort the white cells by counting, then the total complexity of the solution will be O (total number of cells).
Which of the tasks did you find most interesting?
Announcement of the first qualifying round on April 19.