Russian Code Cup 2013: parse the tasks of the final

On September 23, 2013, the final of the Russian Code Cup 2013 Programming Championship was held.

First place went to Peter Mitrichev (by the way, the champion of the RCC 2011). Gennady Korotkevich took the second prize, Dmitry Dzhulgakov - the third.
')
Today we publish a detailed analysis of the six tasks that were proposed to the finalists of the RCC (spoiler: one of them remained unresolved). The program - sorting unprecedented speed, the fight against capybarny flu, travel robots and much more.

Problem A. Patience

Bullies Petya and Vasya sit in an unbearably boring lesson. In order to somehow have fun, they decided to play with the patience of the teacher. The level of teacher dissatisfaction with the guys is expressed as an integer x. Petya and Vasya in turn make various small and large pranks, Petya makes a prank first. After petty pranks, the level of teacher dissatisfaction increases by 1, after a major prank, it increases by 2 times. That student, after the pranks of which the teacher’s discontent becomes greater than n, receives a reprimand from the teacher and comes after lessons with his parents to the principal. Naturally, neither Vasya nor Petya are happy with this outcome, and therefore each of them acts optimally to avoid it.

Guys play this game every day. Every day the teacher’s initial discontent grows: on the first day it was 1, on the second day it was 2, and so on. On the i-th day, the initial discontent of the teacher with the students is i. There are exactly n study days in a year, that is, on the last day of study, teacher’s dissatisfaction is equal to n and any prank of students instantly pulls him off.

An excellent student, Kolya, is also very bored in class, because he already knows everything that the teacher tells. Kohl noticed a strange game of Petit and Vasya and easily found out who would go after their parents on every school day. Once Kohl noticed that Vasya went for his parents exactly for the k-th time. Determine which account of the school day this happened?

For example, let n = 4. On the first day, the teacher’s initial dissatisfaction is 1. Whatever prank Petya did, the teacher’s dissatisfaction will be 2. After that, Vasya commits a major prank, and the teacher’s dissatisfaction becomes equal to 4. Now, whatever prank Petr, he will be reprimanded and will go after his parents. On the second school day, the teacher’s initial discontent is 2. Now Petya commits a major mischief and forces Vasya to be reprimanded. On the third school day, Petya achieves the same effect by making a shallow prank. On the last - the fourth - school day, Petya will be reprimanded, since he has to commit a prank first. Thus, if Kohl sees that Vasya went for his parents for the first time, it can be concluded that now is the second school day, and if Vasya went for his parents the second time, now it is the third school day.

Input Format
The first line contains an integer T (1 ≤ T ≤ 10 ⁵ ) - the number of tests. Each of the following T lines contains the description of the next test: 2 integers n and k (1 ≤ n, k ≤ 10 ¹⁸ ).

Output format
For each test, output a single number: a - the day on which Vasya went after the parents for the k-th time, or −1, if such a situation cannot occur. Print each of the numbers on a separate line.

Parsing:
The condition described a game for two participants. The state of the game was described by one number x, and the players in turn could make one of two moves: replace x with x + 1 or 2x. The player who first wrote a number greater than n lost. It was necessary to find k by increasing the number x, such that the first player has a winning strategy if the initial number is x.

Since the restrictions on n were rather large, it was necessary to understand the structure of numbers, which are winning positions for a player who starts from such a state. We will show that this set is represented as a union O (log n) of segments of consecutive numbers, in each of which either each number or each second number is the winning position for the first player.

We will build this set recursively. Let the procedure F (n) return the set of all such segments, and at the same time the invariant is fulfilled: the player who made the move to a number greater than n loses.

Consider two cases. Let n be odd. Then any even number from 2 to n-1 is a winning position, and any odd number is a losing one. We show that the first player can always make him go from an even position, and his opponent from an odd position. Indeed, if the first player converts x to the number x + 1, then the second player can translate x + 1 only to an even number. It remains only to note that the number n is odd, and therefore the first player always has a move that does not lead to his defeat. Continuing by induction, we find that if the first player starts with an even number, then he has a winning strategy. In the case when the first player starts with an odd number, the second player uses the same strategy and wins.

Now let n be even. All odd positions that are greater than n / 2 are advantageous, since doubling such a number immediately leads to defeat; in this case, the winning position is determined by the parity of the number of remaining moves. Note also that the position n / 2 is advantageous, because from n / 2 you can get n, and the other player necessarily exceeds n with his next move.

Consider a number l that is greater than n / 2; while the position l is losing. Depending on the parity of the number n / 2, l is equal to either n / 2 + 1 or n / 2 + 2. Now consider all numbers from l / 2 to n / 2 inclusive. All these positions will be winning, because if you double any of these numbers, you get a number greater than n / 2 and even, and this position is a loss. We got two segments, on the first of which every position is advantageous, and on the second - every second.

Note that the remaining segments can be obtained by calling F (l / 2 - 1). By analyzing the cases, it can be shown that l / 2 - 1 is always equal to n / 4, rounded down. Make sure that the required property holds. Let x ≤ l / 2 - 1. Then 2x ≤ l - 2 ≤ n / 2, that is, all positions that are larger than l / 2 - 1 and to which movement from a position not exceeding l / 2 - 1 is possible winning, and therefore such a move will lead to loss.

With each recursive call, n is reduced by at least 4 times, so the program runs in O (log n). After that, to solve the original problem becomes easy. Since all these segments do not intersect, you can walk through them in ascending order and determine whether the answer falls into the current segment. If the current k is more than the number of numbers on this segment, then subtract this number from k and move on to the next segment. Otherwise, we can get the k number we need on this segment and output it. If no such segment was found, output -1.

Problem B. Snow White and n Dwarfs

Snow White is friendly with n gnomes, whom she numbered from 1 to n. It is known that the growth of the i-th gnome is hi centimeters, the growth of each gnome is positive and does not exceed n. A princess considers a non-empty subset of gnomes to be pretty if the sum of their numbers matches their total height. It is required to find out if there is a cute set of dwarfs, and if there is one, output an example of such a set.

Input Format
The first line contains an integer t - the number of tests. The following 2t lines contain t different test queries. The first line of the query contains n - the number of gnomes (1 ≤ n ≤ 10 ⁶ ), the second one contains n positive numbers not exceeding n - the growth of gnomes.

The sum n for all requests does not exceed 10 ⁶ .

Output format
If there is an answer in the first line, you need to display the number of gnomes in a nice subset that satisfies the condition, and in the second line you need to output the numbers of the selected residents separated by a space. In case a nonempty nice subset does not exist, output −1.

Parsing:
Construct a directed graph of n vertices. From the vertex i there will be one edge at the vertex a _i . If there is a cycle in this graph, then the vertices that are included in it will be included in the set that is required by the problem condition, since the sum of the numbers of vertices of the beginning edges on the cycle will be equal to the sum of the numbers of the ends.

Let the cycle in this column does not exist. Then choose any vertex. Since there is no cycle in the graph, this edge does not lead to it. We move along the edge and find ourselves at another vertex, from which the edge does not lead either to the first or to itself, otherwise the cycle would exist. Acting similarly, we will find ourselves at the last unvisited vertex. Wherever we lead edge from it, we get a cycle. We see a contradiction, therefore, the cycle is always there; this implies that there is always the set we need.

To find a cycle, you can act according to the algorithm described above: go along the edges until you reach the top that you have already visited. This means that this vertex is on a loop. From it is easy to find the cycle we need.

Problem C. Fast-quick sort

You must have a quick sort algorithm. Consider some of its variations, sorting an array without repeating elements.

function qqsort(A: array of int): array of int if isSorted(A): return A middle = pick(A) aLess = elements of A less then middle aGreater = elements of A greater then middle return qqsort(aLess) + [middle] + qqsort(aGreater) 

To sort an array, the following is done: first it is checked whether it is already sorted. If so, no further action is required. Otherwise, some element of the array is selected, the rest are divided into those that are smaller than it and those that are larger, after which sorting is started for these new arrays. In the new arrays, the elements are in the same order in which they went in the original array.

The isSorted (a) function checks whether the array already passed to it is sorted by argument. The pick function returns some element from the array, which is passed to it as an argument. It can return any of the elements of the array.

It is known that the sorting speed significantly depends on how correctly the separating element is selected. Accordingly, depending on the values ​​returned by the pick function, the number of actions that are performed while the algorithm is running may vary. As the minimization criterion, we will use the number of calls to the pick function.

An array of n distinct integers from 1 to n is given. Determine what minimum number of calls to the pick function can be achieved when sorting it, if each time you call pick is allowed to select a return value.

For example, if you want to sort the array A = [1, 2, 6, 7, 5, 3, 4, 8, 9], then if the first call to the pick function returns 5, the aLess array will be [1, 2, 3, 4], and the aGreater array is [6, 7, 8, 9]. Accordingly, the qqsort recursive calls will immediately go out, because in them the isSorted calls will return true and the array will be sorted. This is optimal; in this case, the pick function was called only once.

Input Format
The first line contains the number of tests t. Further in the 2t lines the tests themselves are given. The first line of the test description contains a positive number n - the size of the array. The second line contains the array itself ai (1 ≤ ai ≤ n, if i ≠ j, then ai aj). The total size of the arrays in all tests does not exceed 106.

Output format
For each test, output a single number — the minimum number of calls to the pick function, which can be done by sorting it using the qqsort function.

Parsing:
In the task, some modification of the fast sorting algorithm was given and it was required for the given permutation to find the smallest number of calls of the pick function to sort it.

Denote by left (a, x) what was called smaller in the code from the condition — the elements of array a are strictly smaller than x. Similarly, we introduce right (a, x) - elements greater than x. Let us prove several statements about left and right.

If x ∈ a and a is a set of consecutive natural numbers, then left (a, x) and right (a, x) are also sets of consecutive numbers. This is true, since if a is the set of integers from L to R, then left (a, x) is the set of integers from L to x-1, and right (a, x) is the set of integers from x + 1 to R.

Let's look at the given array a. Denote by w [i] the position of the element i in a: w [a [i]] = i. We divide the array into chains of increasing numbers by 1 so that the elements within one chain in the array go in a row: add 1 to the first chain, then, if w [1] <w [2], then add 2 to it, etc.

For example, chains ([1, 2, 6, 7, 5, 3, 4, 8, 9]) = [[1, 2, 3, 4], [5], [6, 7, 8, 9]] . Let's see what happens with these chains after splitting into x. We divide into chains the left (a, x) and right (a, x). We study the left. right is treated similarly. Consider the relative position of the chain [c..d] ∈ chains (a) and x.

• x> d. In this case, [c..d] ∈ chains (left (a, x))
• c <x. In this case [c..d] ∉ chains (left (a, x)). And also no element of [c..d] is represented in any chain of chains (left (a, x))
• x = d, x ≠ c. Here [c..d-1] ∈ chains (left (a, x))
• x = c, x ≠ d. Similar to the second case, [c..d] ∉ chains (left (a, x))
• Finally, the last case: x = c = d. In this case, nothing from the chain [c..d] (which, in fact, [c]) falls into neither the chains (left (a, x)) nor the chains (right (a, x))

Looking at these cases, you can notice the following: if the two elements were once in the same chain, then they will never be in different chains of the same array to be sorted. However, they may be in different chains, but within the framework of sorting different arrays. For example, a = [5, 2, 3, 4, 1], chains (a) = [[1], [2, 3, 4], [5]], x = 3, left (a, 3) = [2, 1], chains (left (a, 3)) = [[1], [2]], right (a, 3) = [5, 4], chains (right (a, 3)) = [ [4], [5]]. It can be seen that the numbers 2 and 4, which were first in the same chain [2, 3, 4], differed in different ways, but at the same time the arrays being sorted were also different ([2, 1] and [5, 4]).

From this we can make the first important observation: it does not make sense to take as a separating element that is not the last item in the chain. If we take instead of one of the extreme elements taken from the middle, the answer will be no worse (since elements of one chain cannot become elements of different).

We describe informally what I want to achieve. We have an array of a. We build chains (a) on it. In the resulting set, it is advantageous to select only the ends of the chains as a separator. In order to get a sorted array, it is necessary to eliminate all gaps between the chains. If there were originally chains [c..d] and [d + 1..e], and d was chosen as the separator, the gap (d..d + 1) stops worrying us, since all the elements to the left of it in one array, and all that to the right - in another. Thus one gap was eliminated, and all of them must be eliminated #chains (a) - 1, where # denotes the size.

Let there be neither the first nor the last chain of length 1: [c..d-1], [d], [d + 1..e]. Take d as the dividing element. Then, since it is the leftmost one for the chain [d], the gap (d-1..d) will be eliminated. Since it is also the rightmost one for the same chain, the gap (d..d + 1) will also be eliminated. Thus, the choice of a single element of a non-limit chain as a separator will eliminate two gaps at once.

Let there be some kind of optimal answer, and in it were dividing elements d ₁ , d ₂ , ..., d _k . Each of them eliminated some gaps. We do the following: choose min {d ₁ , ..., d _k } as the first separating element. The array is broken into sorted left and not yet sorted right pieces. We select the second minimum among d _i and make it a separating element for the right-hand piece. We will repeat until d _i run out. It is easy to make sure that with such a strategy for the selection of separating elements, each will eliminate the same number of gaps as in the previously chosen optimal choice. Thus, it is possible to solve a problem using dynamic programming, considering the minimum required number of actions in order to combine the first few chains into one. The answer will be the minimum number of actions required to combine all the chains into one.

Task D. Robot

Boris is participating in the robot programming competition. At the initial time, the robot is located in the upper left cell of a rectangular field of n × m size. The goal of the robot is to get into the right lower cell as quickly as possible. In one move, the robot first moves from the current field to the adjacent cell along its side.

Each cell is painted in one of two colors: black or white. It is known that the left upper and right lower cells of the field are painted black. After each move of the robot, if it stands on a white cage, the following happens: one of the white squares of the field is randomly selected and the robot is rearranged to it. In particular, the cell on which the robot is already standing can be selected - in this case, it remains on it.

Boris wants to win the competition, for this he needs to develop an optimal strategy for the robot. He knows the scheme of the field, where for each cell it is marked whether it is black or white. Now he is trying to figure out the expected number of moves that the robot will need to reach the finish when using the optimal strategy. Boris wants to know the answer exactly, so he tries to get it in the form of an irreducible fraction. Help him figure out the expected value.

Input Format
The first line contains an integer t - the number of fields. Each field is described as follows. The first line contains two integers n and m - the height and width of the field in the cells (1 ≤ n, m ≤ 10 ³ ). The following n lines contain m characters each. If the symbol is B, then the corresponding cell is black, and if W, then white.
The total number of cells in all fields does not exceed 10 ⁶ .

Output format
For each field in a separate line, print the expected number of moves required to get from the upper left cell to the lower right cell for the optimal strategy. The answer must be derived in the form of an irreducible fraction.

Parsing:
In this problem, it was necessary to find the expectation of the length of the shortest path from one corner of the field to another. At the same time, some cells of the field were painted white, and when the robot hit this cell, it was rearranged into a random white cell of the field.

Let us examine in more detail how the optimal strategy for choosing a path is arranged. For each cell of the field, you can calculate the expectation of the number of moves required to get into the right lower cell. In this case, the answer will correspond to the distance, which is recorded in the upper left cell. How to calculate these values? Consider a particular cell and all its neighbors. If the adjacent cell is colored black, then the answer for the cell will be at least (1 + value that is written in the adjacent cell). If the cell has a white neighbor, then the answer for it is at least (1 + arithmetic mean of responses for all white cells).

It is clear that if a robot gets in 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 the case, then on some of the moves the robot did wrong and went into the cage with a great 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 immediately to the lower right corner of the black cells (if such a path exists), and he can go to some white cell. Obviously, among all the white cells in which you can go, you should choose the closest one.

For each cell, we calculate the distance to the lower right one by the black cells and the distance to the nearest white one. Note that for any white cell the distance to the nearest white one is not more than two. Now we divide all the white cells into two sets - those from which the robot must immediately go to the right lower cell, and those from which the robot must go to the next white one. When such a partition is made, the answer is easy to calculate. Writing the recurrence relation for the average response for all white cells, we find it. This will be some fraction with a denominator of no more than the number of white cells. Now the answer is min (the distance in black cells to the bottom right, the distance to the nearest white + the average answer for all whites).

It remains to learn how to find the correct division of white cells into sets. We sort all the white cells by the criterion (the distance to the right lower one by black - the distance to the nearest white one). It is argued that the optimal splitting is the following: from all cells of a certain prefix of a sorted array, it is necessary to go immediately to the right lower cell, and from the rest to the nearest white cell. This fact is easily proved by the opposite method (let the optimal partition have a different appearance; consider the average answer for white cells, we see that some cells can be moved from one set to another without worsening the answer, but reducing the partition to the desired form).

As a result, the decision boils down to the following. Calculate the distances discussed earlier for all cells. We sort the white cells. Let's sort the partition into sets, each time recalculating the average answer for white cells as O (1). The answer to the problem is the minimum from the distance in black cells and the distance to the nearest white cell + average answer 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).

Task E. Vaccination

The Ministry of Health, Bytelandia, conducted a large-scale study of the incidence of capybarnum influenza among the inhabitants of the country. Scientists have found that a person’s immunity against influenza is characterized by a whole non-negative number. Every year on January 4, as a result of an outbreak on the Sun, each person’s immunity is reduced by k. However, he can not become negative. If the original immunity was less than k, then the immunity becomes 0.

In some years on January 2, all residents were vaccinated against influenza in Bytelandia. As a result of vaccination, the immunity of each person increased by a certain amount. As a result of each vaccination, the increase in immunity is the same for all residents, although perhaps this value is different for different vaccinations.

To better study the disease, scientists decided to collect more statistics. Help them figure out the immunity of some people in some years of their life.

About each person is known the year in which he was born, the year in which you need to know his immunity, as well as his immunity at birth. We will assume that all residents of Bytelandia were born on January 1 of the relevant year, and to recognize immunity is required on January 3.

Input Format
The first line contains an integer t - the number of tests.

Each test is defined as follows. The first line contains three integers n, m and k - the number of vaccinations, the number of requests and the amount by which immunity decreases on January 4 of each year as a result of a solar flare (1 ≤ n, m ≤ 10 ⁵ , 1 ≤ k ≤ 10 ⁹ ) . The following is a description of vaccinations: the next n lines contain two numbers each - the year in which the vaccination was carried out, as well as the amount by which the immunity of each person increased. It is guaranteed that the years are given in strictly increasing order.

The following m lines contain queries: three integers each, indicating the year of birth of the person, the year in which his immunity must be known, as well as the initial immunity of the person.

All numbers in tests are non-negative and do not exceed 10 ⁹ . It is guaranteed that the year in which it is necessary to recognize a person’s immunity is not less than the year of birth. The total number of vaccinations in all tests does not exceed 200,000. Similarly, the total number of people does not exceed 200,000.

Output format
For each request in a separate line output the person's immunity in the corresponding year.

Parsing:
In this task, the rules were set according to which a certain quantity changes. It was necessary to find the value of the value under different initial conditions. The changes themselves took place as follows. Each unit of time value decreased by some number. If the value became negative, then it was equated to zero. At some points in time, some values ​​were added to this value.

Each request was characterized by a triple of numbers - the beginning and end of the observation interval, as well as the initial value of the value. Consider the function of answering a query, depending on the third parameter. It is stated that it always has the following form: to some value, the answer is constant, and if the value is greater than this value by x, then the answer will be this constant + x. It is easy to prove by induction on the number of "additions" that are in the segment. Base of induction - on a segment, the values ​​only decrease each time unit by a constant. The validity of the statement is obvious. Suppose we have considered the first k additions, and now we add another one that occurs later than the existing ones. It is necessary to analyze two cases - when the minimum value with which we can arrive at the last “addition” is zero, and when it is greater than zero. In both cases, the final function has the same form.

Knowing the fact that is described above, it is not difficult to come up with the right solution. Build a tree of segments on all the "additions". At the vertices of the tree, we will store in some form the answer function for the gap. In order to connect the two gaps, it is necessary to carefully consider the two cases discussed above. To process the next request, we take the corresponding interval from the segment tree, we take into account that the ends of the gap may not exactly coincide with the ends of the query, we calculate the value of the function. The total complexity of the solution is O (n + m • log (n)), where n is the number of “additions” and m is the number of queries.

Problem F. Flight Schedule

The new flight schedule of the company BytelandAvia gave a surprise to all travelers exploring the sights of Byteland. According to representatives of this company, with a new flight schedule, any tourist will be able to quickly and easily determine the minimum number of hours that he will spend on a flight from one city to another.

There are n cities in Bytelandia, and the airline serves m regular flights, allowing you to get - possibly with a few transfers - from any byteland city to any other. Flight number i connects cities with numbers ai and bi and runs exactly once a day, consisting of p hours in Byteland. The flight time of the i-th flight is li hours, and it flies at the moment when si hours have passed since the beginning of the next day. Moreover, all flights are bilateral, that is, the aircraft from city ai to city bi and aircraft from city bi to city ai fly out and arrive simultaneously. It is also known that airplanes fly strictly according to a schedule, which allows a traveler who has flown into the city at some point in time to catch a plane departing from the same city at that very moment.

In this case, the Bytlandia flight schedule satisfies the following condition. Consider an undirected graph, where the vertices are cities; they are connected by an edge if there is a direct flight between cities. Then, in this graph, each vertex belongs to no more than one simple cycle, such graphs are called vertex cacti.

You need to determine the minimum number of hours that the traveler, who arrived at the beginning of the next day at the airport x, on the flight to city y, will take. This task needs to be solved for several different travelers.

Input Format
The first line contains the number of tests t. The following are descriptions of tests.

The first line of each test description contains integers n, m and p (1 ≤ n ≤ 10 ⁴ , 1 ≤ m, 1 ≤ p ≤ 10 ⁹ ) - the number of cities in the country, the number of flights and the duration of the day.

The following m lines contain descriptions of flights. The description of each flight consists of four integers a, b, l and s (1 ≤ a, b ≤ n, a ≤ b, 1 ≤ l ≤ 10 ⁹ , 0 ≤ s <p) - the cities connected by this flight, its duration and time of departure. It is guaranteed that no pair of cities is connected by two or more flights.

The next line contains a single integer c (1 ≤ c ≤ 10 ⁵ ) - the number of travelers for whom you need to find the minimum duration of their journey. c x y (1 ≤ x, y ≤ n) — , , . (x + ans — 1) mod n + 1 ( y + ans — 1) mod n + 1, ans — , , 0 .

, 10 ⁴ , — 10 ⁵ .


— , .

:
. , , , , .

, , , . , , .

. , , . :

• , 0 ( )
• , 0

, 2 ^k 2 ^{k + 1} O(1) , 2 ^{k + 1} 2 ^k , , , , .

, , , , O(logn) , . , , .

, , . -, , - , , . : , , , . , , .

, , , , : , , , , , . , , :

• , 0 ( ) , ,
• , 0 , ,
• , 0 , ,
• , 0 , ,

, , , .
, . , (, ) , , , , .
, — , , .

RCC 2013 . F , , , — 50 .

, ( , ) .