Results of the second round of the Russian Code Cup 2017
On April 16, the second qualifying round of the Russian Code Cup 2017 was held , at which attendance records for the last three years were broken. By tradition, we brag a little bit of the results and lay out the analysis of tasks.
A. Very important guests
B. The least common multiple
C. Portim order
D. Red-black tree
E. Exploring the array
This time 5262 programmers were registered (647 of them are new participants). In the qualifying round, we took on the results of another 201 participants. All five tasks successfully solved 10 people. The first three places were taken by the guys with a very large margin from the rest:
- In the first place is Andrei Popa from Romania.
- Second place went to Lam Nguyen, only two minutes behind the penalty time.
- In the third place with a small margin of five minutes was Vladislav Epifanov from Nizhny Novgorod, Russia.
In addition, the top 10 hit:
- Adam Bardashevich, Mozyr, Belarus
- Mahmoudian Arash, Reina, Iran
- Oleg Davydov, St. Petersburg, Russia
- George Wu, China
- Yuri Pisarchik, Minsk, Belarus
- Roman Udovichenko, Stolbtsy, Belarus
- Nguyen Trung, Vietnam
We congratulate all those who passed in the qualifying round. The rest can be prepared for the third qualifying round, it will be held on Saturday, April 29, from 14:00 to 16:00 Moscow time. And now - analysis.
A. Very important guests
Time limit - 1 second
Memory limit - 256 megabytes
At the opening of the new campus of the University of the city of N plan to arrive nm very important guests. The ceremony will be held in the hall, which has a rectangular shape, the seats in the hall are organized in n rows of m seats, the rows are numbered from 1 to n , the seats in each row from 1 to m , j -th place in the i -th row is designated as (( i, j ).
The opening ceremony organizers numbered guests from 1 to nm in accordance with their importance, the more - the more important. The most important guest - the mayor of the city - has the number nm . It is known that the mayor plans to sit down at the place (1, 1). Now you need to seat the rest of the guests. At the same time, guests must be arranged in such a way that a guest with a larger number is located no further from the mayor than a guest with a smaller number. The distance between two places ( r 1 , s 1 ) and ( r 2 , s 2 ) is the value | r 1 - r 2 | + | s 1 - s 2 |.
Help the organizers of the ceremony seating the guests.
Input Format
The input contains several test cases. The first line contains the number of tests t (1 ≤ t ≤ 400).
Each of the tests is described by two integers: n and m (1 ≤ n , m ≤ 20).
Output format
For each test, output what the hall will look like after accommodating guests there.
Print n lines, each with m numbers, j -th number of the i- th line should be equal to the importance of the guest who will sit on the seat ( i, j ).
If there are several suitable ways to seat the guests, output any of them.
Examples
Input data
2
2 3
3 2
Output
6 4 2
5 3 1
6 4
5 2
3 1
There are two ways to solve this problem. The first is to seat guests diagonally, starting from position (1, 1). Some accuracy in implementation is required to correctly take into account the cases n <m and m <n . The second method allows not to think about which way the rectangle is drawn. Just run the bypass in width from the place (1, 1) and we will seat the guests, starting from the maximum number, in order to extract seats from the queue.
B. The least common multiple
Time limit - 2 seconds
Memory limit - 256 megabytes
The concept of the smallest common multiple, the minimum number that is divided into each of the given, is well known. This concept can be generalized to other mathematical concepts. For example, on ordinary fractions.
Given two fractions. It is required to find their smallest common multiple — such a smallest positive irreducible fraction p / q , that when it is divided into each of these fractions in a particular, an integer is obtained.
Input Format
The input contains several test cases. The first line of the input data contains the number t - the number of tests (1 ≤ t ≤ 50 000).
Each test is described by one line, which contains four numbers a, b, c, d, which define fractions a / b and c / d (1 ≤ a, b, c, d ≤ 10 9 ). It is guaranteed that a / b and c / d are reduced fractions.
Output format
For each test, output on a separate line the smallest common multiple of the fractions a / b and c / d - the numerator and denominator of the desired irreducible fraction through a space.
Examples
Input data
2
9 5 12 5
1 10 3 100
Output
36 5
3 10
Let p / q be wholly divisible by a / b and c / d , and all fractions are irreducible. Then the integers are ( p / q ): ( a / b ) = ( p • b ) / ( q • a ) and ( p / q ): ( c / d ) = ( p • d ) / q ( c ).
p • b is divided by q • a . Since b and a are coprime, p is divisible by a . p and q are coprime too, so b is divisible by q . Similarly, p is divided by c , d is divided by q .
Thus p divides lcm ( a, c ), q divides gcd ( b, d ). The lcm ( a, c ) / gcd ( b, d ) fraction is the smallest fraction and is divided by a / b and c / d . Thus, the answer is lcm ( a, c ) / gcd ( b, d ).
C. Portim order
Time limit - 2 seconds
Memory limit - 256 megabytes
Dima has n dots painted in a row on the carpet in the room. By a surprising coincidence, he also has n cubes, weighing 1, 2, ..., n grams, respectively. Dima played enough with the cubes and put them in a row, one per point. Now he was going to shift them so that they went from left to right in ascending weight, but a little distracted. At that moment, the bad boy Vadim entered the room and decided to foul up on Dima.
Vadim knows that Dima is still small, and he will arrange the cubes in order of increasing weight as follows. Each time he will look for the easiest cube, which is not yet in place, and change it with the one that stands there in his place.
Vadim is a bad boy, so he wants to spoil a little more. He has already pulled several cubes out of the row and now wants to arrange them back in such a way that Dima makes the maximum number of exchanges. After the cubes return, those cubes that Vadim did not remove should remain in their places, exactly one die should appear at each point.
How exactly should he arrange the cubes?
Input Format
The input contains several test cases. The first line contains the number of tests t .
Each test is described as follows.
The first line of the test description contains the number n - the total number of cubes (1 ≤ n ≤ 10 5 ). The next line contains n numbers a i (0 ≤ a i ≤ n )
If a i is equal to 0, then at the i- th place is not worth anything yet, this cube Vadim took out. Otherwise, a i is equal to the mass of the cube, which stands on the i- th place.
It is guaranteed that the masses of the cubes present are different. Vadim must return exactly those cubes in a row to empty spaces that are not there yet.
The sum n in all tests of one input data does not exceed 10 5 .
Output format
For each test, output two lines.
In the first line print the number of exchanges that Dima will have to make to sort the cubes.
In the second line print n numbers - the masses of the cubes in the order from left to right, which are obtained with the optimal arrangement of the cubes by Vadim. Please note that the cubes that Vadim did not take out immediately should remain in place.
If there are several possible solutions that lead to the maximum number of exchanges, output any of them.
Examples
Input data
3
2
0 0
four
4 0 0 3
five
0 4 0 2 5
Output
one
2 1
3
4 1 2 3
2
3 4 1 2 5
In the task, it is necessary to supplement the original array before rearranging the numbers from 1 to n so that the sorting will make the greatest number of exchanges.
To begin with, let us assume that we have already generated some sort of permutation and want to find out how many exchanges the sorting will make by choice. For this, we will consider the permutation as a set of cycles. Consider a cycle that contains the minimum number that does not stand in its place. The length of this cycle is more than 1. It is easy to notice that with one exchange the length of the corresponding cycle decreases by one and a new cycle of length 1 appears. Now note that the cycle of length L will decrease its length exactly L - 1 times during the sorting process, which means that the total cycle lengths will decrease exactly by n - c , where c is the number of cycles.
Thus, we need to supplement the array before permutation so that the number of cycles is minimal. To do this, consider the permutation as a directed graph, where if a [ i ] = j , then the graph has an edge from vertex i to vertex j . The graph broke into loops and chains. All the cycles that are in this graph will be preserved even after adding the missing elements, and all existing chains (a vertex that has neither incoming nor outgoing edges, we will consider as a chain of length 0) can be combined into one big cycle. Go through all the available chains and add an edge from the end of one chain to the top of another. When all the chains are connected into one, we add an edge from its end to the beginning, and it will become a cycle.
D. Red-black tree
Time limit - 3 seconds
Memory limit - 256 megabytes
Did you know that in most standard libraries the data structure “set” is implemented using red-black tree? In this task, you need to find the number of ways to paint a given binary tree so that it becomes red and black. The answer must be displayed modulo 10 9 + 7.
Consider a binary tree. If a vertex has less than two children, add fictitious vertices to the place of missing children. A tree is called red-black if the following properties are true:
- Each vertex is painted in one of two colors: red or black.
- The root of the tree and all the added dummy vertices are colored black.
- The parent of the top, painted red, is painted black.
- All paths from the root to the added fictitious leaves contain the same number of black vertices.
Note that the parent of a vertex colored black can be colored black.
Two colors of a tree are called different if there is a vertex that is painted in different colors in these colorings.
The figure shows two ways of painting wood from the second test.
Input Format
The first line contains a single integer n - the number of vertices in the tree (1 ≤ n ≤ 500 000).
The following n lines describe the tree. The i- th line contains two integers l i and r i - the indices of the vertices that are the left and right children of the i -th, or 0, if the corresponding child is missing ( l i = 0 or i < l i ≤ n ; r i = 0 or i < r i ≤ n ). The root of the tree is number 1. It is guaranteed that the correct tree is described in the input.
Output format
Output one integer - the number of ways to paint the given tree so that it becomes red and black. The answer must be displayed modulo 10 9 + 7.
Examples
Input data
3
2 3
0 0
0 0
Output
2
Input data
6
2 4
thirty
0 0
5 6
0 0
0 0
Output
2
Having noticed a subtle hint in the first sentence of the conditions, it is easy to prove (or check in any book on data structures) that in any red-black tree with n vertices on the way from the root to the leaves O ( logn ) black vertices. We take advantage of this fact in the decision.
We call an almost red-black tree in which all the properties of a red-black tree are fulfilled, but the root of the tree is painted red.
Using dynamic programming, we calculate for each subtree the number of ways to color vertices in it so that the subtree is red and black and the number of black vertices on the path from root to leaf is h - or the tree is almost red and black and the number of black vertices on the path from root to leaf was h .
Save this number of methods in the array d [ v ] [ h ] [ t ], where v is the number of the vertex that is the root of the subtree, h is the number of black vertices on the path from root to leaf, and t denotes the type of painting: if t = 0 - the number of dyes is stored there so that the subtree becomes red-black, and if t = 1, the subtree becomes almost red-black.
Then d [ v ] [ h ] [0] equals the product for all u , which are children of v , of the values ( d [ u ] [ h - 1] [0] + d [ u ] [ h - 1] [1]). And d [ v ] [ h ] [1] equals the product over all u , which are children of v , of values d [ u ] [ h ] [0].
The answer to the problem will be equal to the sum over all d [1] [ h ] [0].
Now we note that h for all admissible colorings of subtrees is limited to a certain value C = O ( log ( n )), and for all h > C the number of colorings is guaranteed to be zero.
This means that all O ( nlog ( n )) states are needed, from each of which there are O (1) transitions. Therefore, the solution will work for O ( nlog ( n )).
E. Exploring the array
Time limit - 2 seconds
Memory limit - 256 megabytes
Vasya loves arrays. Therefore, for his birthday, his parents gave him an array a , consisting of the numbers 1 and - 1. Vasya immediately began to study it.
Since Vasya also loves zeros very much, he decided to take different subsegments a [ l i , ..., r i ] of array a and look for the length of the maximum subsegment with the sum 0. If there is no such subsection, he considers the answer to be 0. Vasya wrote on a piece of paper q segments [ l i , r i ] and now wants to find the sum of the answers to them.
Here are the answers to the subsegments selected by Vasya in the test example:
- Sub-segment [1, 5]: maximum sub-segment with the sum of 0 - [2, 5];
- Sub-segment [1, 3]: maximum sub-segment with the sum of 0 - [2, 3];
- Sub-segment [2, 4]: maximum sub-segment with the sum of 0 - [2, 3];
- Sub-segment [3, 4]: There is no sub-segment with sum 0;
- Sub-segment [3, 5]: the maximum sub-segment with the sum of 0 - [4, 5].
Total, the total length of all the desired subsegments in this test is 4 + 2 + 2 + 0 + 2 = 10.
Input Format
The input contains several test cases. The first line contains the number of tests t (1 ≤ t ≤ 1000).
Each of the following t tests is described as follows: the first line of the test description contains the number n - the number of array elements (1 ≤ n ≤ 10 5 ).
The next line contains n integers a i - the elements of the array ( a i = - 1 or a i = 1).
The next line contains the number q - the number of sub-spars written out by Vasya (1 ≤ q ≤ 10 5 ).
Each of the following q lines contains two numbers l i , r i - the left and right borders of the i -th sub-segment, respectively (1 ≤ l i ≤ r i ≤ n )
It is guaranteed that the sum n in all tests of one input data does not exceed 10 5 , and the sum q in all tests of one input data does not exceed 10 5 .
Output format
For each test, output the answer to it - the sum of the answers for all q sub-spans.
Examples
Input data
one
five
1 -1 1 1 -1
five
15
13
2 4
3 4
3 5
Output
ten
Since the restrictions on n and q are the same, we will use n instead of max ( n, q ). Let's make some observations.
The first observation: the answer to the request is the maximum length of the segment [ L, R ] such that pref L - 1 = pref R , where pref i = a 1 + a 2 + ... + a i is the prefix sum of the array a ( pref 0 = 0). Further, we will assume that we work with the array pref 0 , pref 1 , ..., pref n and on request [ l, r ] it is required to find the maximum in length of the [ L, R ] sub-segment [ l - 1, r ], such such that pref L = pref R.
The second observation: pref i - rather small (- n ≤ pref i ≤ n ).
We will solve the problem offline. We use the method, in many respects similar to the Mo algorithm. We divide all queries into groups, where the i -th group contains queries [ l i , r i ], such that i • K ≤ l i <( i + 1) • K ( K is a constant approximately equal to sqrt ( n ) ). In each group, sort the requests by the right border. Now we will solve the problem separately for each group of requests.
Consider the ith group [ L i , R i ]. We will go in a row on requests from left to right (i.e., not decreasing the right border). We will also support two arrays, mostLeft [ p ] and mostRight [ p ]: the current leftmost occurrence of the prefix sum p , which is also to the left of R i , and the current rightmost occurrence of the prefix sum p . Supporting these two arrays, it is also easy to maintain the answer on the segment [ R i + 1, r ], where r is the right border of the current query. To answer the query [ l, r ], we calculate in O ( K ) the answer to [ l , min ( r, R )], using the information from the mostRight array, and compare this value with the current answer on the [ R + 1, r ] segment .
Total for requests of each group in total we spend O ( K • c i + n ) time, where c i is the number of requests in the group. Since the groups are O ( n / K ), we get the total operation time O ( sum i = 1 ... n / K ( K • c i + n )) = O ( K • sum (c i ) + n2 / K ). With K = sqrt ( n ), we obtain the running time O ( n • sqrt ( n )).
All for the third round!
Once again we remind: the third round will begin on April 29 at 14:00 Moscow time. More than five thousand participants have already been registered. Will compete with anyone!
Join now !
')
Source: https://habr.com/ru/post/327066/
All Articles