RCC 2017. Analysis of the tasks of the hottest warm-up round
Original Mighty Morphin Power Rangers by Yurtigo
March 19, the warm-up round of our championship on sports programming Russian Code Cup 2017 was held. This round does not affect the final results, but allows you to get acquainted with the championship system and its objectives. Today we want to talk about the outcome of the round and parse its tasks:
A. Spaceship
B. Rangers on the bus
C. Magic weapons
D. Knights and liars
E. Parallelepiped
2789 people registered for the round, which is two times more than last year. Only one of them was able to solve all five proposed problems! Congratulations to Mikhail Ipatov. Four more people coped with four of them. GNU C ++ 14 turned out to be the most popular language. 565 task solutions were sent to it. The second and third place was taken by Python 3.5 (525 solutions) and GNU C ++ 11 (409 solutions).
A. Spaceship
Time limit per test - 2 seconds
Memory limit per test - 256 megabytes
Space Ranger was on an alien spacecraft surrounded by enemies. To free himself, he needs to destroy all enemies in a certain order.
Around the ranger n enemies, the i- th of them has the power f i . To get out, a ranger must destroy all enemies, and in such a manner that the strength of the last destroyed enemy is equal to the sum of the forces of all other enemies.
The ranger has little time left, so he does not have time to figure out how to do it. He needs your help. Restore the order in which you need to destroy enemies to get out.
Input data
The first line of input contains a positive integer n - the number of enemies (2 ≤ n ≤ 105) .
The second line contains n integers f i that specify the strength of each enemy (–109 ≤ f i ≤ 109) .
Output
Print the numbers f i in the order in which you want to destroy the enemies corresponding to them. If there are several suitable variants, output any. It is guaranteed that at least one suitable order of destruction exists.
Note that if the boss power is x , then the sum of the forces of all enemies is 2x . Therefore, in order to find the strength of the boss, it is necessary to calculate the total strength of all enemies and divide it by 2. After that, you need to find some enemy with such power and change this value in the array f with the value of the last enemy.
B. Rangers on the bus
Time limit per test - 2 seconds
Memory limit per test - 256 megabytes
Space Rangers go to a secret meeting on the bus.
The main villain is closely watching the bus, in which, in his opinion, one of the Rangers is riding. In the cabin there are n rows of seats, each of which has two seats - on the left and right of the aisle. Rows are numbered from 1 to n , starting at the front of the bus. At the final stop, k people took turns in the bus, and the villain knows who sat down at what place and in what order. Initially, all the seats were free.
The villain knows how each of the rangers chooses his place when he gets on the bus:
- The red ranger loves to sit in front. Therefore, among the empty seats, he always chooses a place in the row with the lowest number. If there are two free places in this row, he sits to the left of the passage.
- The blue ranger also likes to sit in front. But, unlike red, when in the row with the smallest number there are two free places, blue sits on the right.
- The black ranger loves to sit back. Among the empty seats, he always chooses a place in the row with the highest number, and if there are two free places, he sits to the left of the aisle.
- The yellow ranger also likes to sit back. But, unlike black, when in the row with the largest number there are two free places, yellow sits on the right.
- The pink ranger has no preferences and can sit on any available space.
The main villain wants to know which of the k passengers could be each of the Rangers. From the known places where the passengers sat down, output this information. Please note that it is not necessary that all the Rangers rode this bus.
Input data
The first line contains the numbers n and k - the number of rows in the bus and the number of passengers (1 ≤ n ≤ 109, 1 ≤ k ≤ min (2 • 105, 2n)) .
The following k lines describe the passengers in the order in which they entered the bus.
The i- th of these lines contains the numbers x i and y i - the place where the i- th passenger sat (1 ≤ x i ≤ n, 1 ≤ y i ≤ 2) , x i is the row number, y i = 1 , if this is the place to the left of the passage, and y i = 2 , if to the right.
All the seats on which passengers sat down are different.
Output
In the first line print the number s 1 - the number of passengers that could be a red ranger, and then, after the space, s 1 numbers - the numbers of these passengers in ascending order (passengers are numbered from 1 to k in the order in which they are given in input file).
In the next four lines, print in the same format information about the other rangers: blue, black, yellow and pink.
We will handle passengers in turn and for each to determine who he could be. Immediately, we note that the pink ranger can sit anywhere, so any passenger can be him.
For each place you need to remember whether it is free. Let's get unordered_set , in which we will keep the occupied places. Check if the next passenger could be a red ranger. To do this, find a place that would have sat red. Cycle through series from 1 to n . If there is a row in which there is a free space, we select the left one, if it is free, or the right one, if not - this will be the place where the red would sit. Since he chooses a seat unequivocally, we can determine if this passenger could be red - you need to check that he took exactly that place. In the same way, we find out where the blue, yellow and black would have sat down: the difference is in the order of enumeration of rows (from 1 to n or vice versa) and in the order of choosing a place in the row (first left or right). After processing the passenger, we mark his place as occupied.
The solution works in O (nk) and uses O (k) memory.
To improve the solution, we note that each of the cycles stops when it finds a row in which there is free space. This means that you need to quickly find the first and last unoccupied series. We will support these values - first and last . Initially first = 1 , last = n . After each iteration of the loop, we update these values. We will increase first by 1 while the first row is busy, then decrease last by 1, while the last row is busy. There are no more than k / 2 rows occupied, so first and last will do O (k) steps. Thus, the improved solution works in O (k) and passes all tests.
C. Magic weapons
Time limit per test - 2 seconds
Memory limit per test - 256 megabytes
To build a magic weapon, you need to connect three fragments: green, red and blue.
The green, red and blue rangers wondered how many different ways they had to assemble a magical weapon. A known set of fragments of each ranger. The green ranger has green fragments, the red ranger has red, and the blue has blue.
When assembling weapons, you must follow three rules:
- The first digit of the model number of the red fragment should be equal to the last digit of the green model.
- The last digit of the red fragment model number should be equal to the first digit of the blue model.
- All three fragments used must have different model numbers.
Two ways to collect weapons are considered different if at least one of the Rangers uses another piece in the assembly, possibly the same model. You know the model numbers of the fragments of each ranger. One ranger can have several fragments of the same model. Help the Rangers understand how many different ways they have to collect weapons.
Input data
The first line of input contains the numbers g , r and b - the number of fragments of the green, red and blue rangers, respectively (1 ≤ g, r, b ≤ 105) .
The next line contains g numbers x i - the model numbers that the green ranger has (0 ≤ x i ≤ 109) .
The next line contains r numbers y i - the model numbers that the red ranger has (0 ≤ y i ≤ 109) .
The next line contains b numbers z i - model numbers that the blue ranger has (0 ≤ z i ≤ 109) .
Output
Print one number - the number of ways to collect weapons.
Prefer arrays: R [a] [b] - the number of fragments in the red ranger, in which the first digit is a , and the last is b ; G [a] - the number of fragments of the green ranger, in which the last digit is a ; and B [b] is the number of fragments of the blue ranger whose first digit is b .
If different rangers did not have identical fragment models, the answer would be equal to the sum over all a and b values of G [a] • R [a] [b] • B [b] .
To take into account the situation when some pair of models coincide, we calculate the number of pairs of fragments with the same model number for the red and blue, red and green and blue and green rangers, respectively (for example, using std :: map). Note that only the numbers that match the first and the last digit are suitable. We use the inclusion-exception formula, subtract the number of such pairs from the answer, and add twice the number of triples of fragments when all three Rangers have the same models.
D. Knights and liars
Time limit per test - 2 seconds
Memory limit per test - 256 megabytes
Space Ranger built his army in two rows of k soldiers. He considers the soldiers on the left and right in the same line as a neighbor, as well as a soldier who is in the same position, but in a different line. The ranger knows that there are knights in the army who always tell the truth, and liars who lie, answering at least one question that they have been asked.
The ranger selected one or two questions from the set:
- "Is it true that exactly x of your neighbors are knights?"
- "Is it true that exactly y of your neighbors are liars?"
And I asked each soldier. All soldiers were asked questions with the same x and / or y values.
Suddenly, all the soldiers answered "yes" to all the questions he asked. Now the space ranger is interested in what the minimum and maximum number of knights can be in his army. Help him figure it out. Let us examine the second example from the condition: there are five soldiers in each line, the questions were asked: "Is it true that exactly one of your neighbors is a knight?" And "Is it true that exactly two of your neighbors are liars?"
The army may consist entirely of liars (they precisely lied when answering the first question, although the extreme ranks answered the truth to the second question). In this case, the minimum number of knights is reached - 0. Another option: in each rank there are knights in the second and fourth places, and liars in the rest. In this case, all the knights tell the truth, as they should, and every liar tells a lie, answering the second question (each liar has exactly one neighbor - a liar). In this case, the maximum number of knights is reached - 4.
Input data
The only input line contains three integers k , x , y - the number of soldiers in one rank and the number of questions (1 ≤ k ≤ 105, –1 ≤ x, y ≤ 3) .
If x = –1 , this means that the ranger did not ask the first question.
If y = –1 , this means that the ranger did not ask the second question.
It is guaranteed that the ranger asked at least one question.
Output
If for the given k , x and y there is no single construction method, output –1.
Otherwise, the first line should contain one number - the smallest possible number of knights in the army, and the second - the largest possible number of knights in the army.
We will solve the problem by dynamic profile programming. Find for example the maximum number of knights. Let dp [i] [mask_prev] [mask_cur] be the maximum number of knights that can be in the layout of the first i columns, mask_cur the mask of the i -th column, and mask_prev the (i - 1) -th.
Then we look through the mask for the (i + 1) -th column and check whether the restrictions on neighbors for the soldiers from the i -th column are fulfilled, since all their neighbors are now known. For the first and last columns, constraints need to be checked separately, because they do not have one of the neighbors.
Base: dp [2] [mask_prev] [mask_cur] is equal to the number of units in mask_prev and mask_cur , if mask_prev can stand to the left of mask_cur .
Transition: dp [i + 1] [mask_cur] [mask_next] = dp [i] [mask_prev] [mask_cur] + ones (mask_next) , where ones (x) is the number of units in the mask x .
The answer will be the maximum among all dp [k] [mask_prev] [mask_cur] such that mask_cur may be to the right of mask_prev . Finally, we note that the case k = 1 should be disassembled separately, since in this case there is no previous column.
E. Parallelepiped
Time limit per test - 2 seconds
Memory limit per test - 256 megabytes
The black ranger wants to make a rectangular parallelepiped. For this, he plans to use 6 of n rectangular sheets of metal, the i- th sheet has size a i per b i meters.
Each facet of the parallelepiped should be a single sheet of metal. Sheets cannot be bent or cut, sheets from which the parallelepiped will be folded should not protrude beyond its edges. Sheets can be rotated arbitrarily.
The black ranger wants to build a parallelepiped of maximum volume. Help him.
Input data
The first line contains one number n - the number of metal sheets of the black ranger (6 ≤ n ≤ 200 000) .
The next n lines contain pairs of numbers a i , b i - the sizes of the i- th sheet of metal (1 ≤ a i , b i ≤ 106) .
Output
Print one integer - the maximum volume of a rectangular parallelepiped, which can be assembled from these sheets of metal.
If it is impossible to assemble a rectangular parallelepiped from these sheets, output –1.
Let's tell about the main idea of the decision. First, we consider separately all parallelepipeds, in which two or three sides coincide, this can be done in O (n) .
Now suppose that all three sides are different. We construct the following undirected graph: the vertices are the possible lengths of the sides, connect the edges of the numbers a and b , if there are at least two sheets of size a × b . The task was reduced to the consideration of triangles in the resulting graph, this can be done as O (n2 / w) or O (nsqrt (n)) (here w stands for the size of a machine word, 32 or 64, this factor appears during bit compression in the search for triangles).
What's next?
We invite you to qualifying rounds! They will take place on April 2, 16 and 29. The top 200 programmers of each round will qualify for the qualifying round. They will receive special certificates and will compete for a memorable prize - a cool T-shirt with the championship logo. And the top 50 programmers of the qualifying round will get to the final, where they will compete for a prize pool of 750 thousand rubles. Join now !
')
Source: https://habr.com/ru/post/324500/
All Articles