At the end of September, we told us that we decided to try to hold a contest, where anyone can practice in solving problems as close as possible to “combat”. So the participants can understand what format the tasks are received by the developers at the interviews in Yandex (many people are interested in this), and most importantly - what they encounter while working on the Search. A typical task at the interview is to create an algorithm, prove its correctness, suggest ways of optimization. If a person understands the algorithms, then he will quickly be able to implement them in any available language.

In Blitz, you can use Java, C ++, C # or Python. In addition, participation in the contest gives you the opportunity to test your knowledge. If in the end you understand that they should be tightened - this is also the result. By the way, then specialization on the Algorithms and Data Structures cursor, in the creation of which Yandex participated, may be useful to you.

Let's now analyze the tasks that were proposed in the qualifying round. We had several variants of the same complexity, each of which contained six tasks. We will analyze one set of tasks completely, as well as the most interesting tasks from other sets. By the way, out of 1,762 participants in the qualifying round, only 263 passed to the final. So the tasks were not the easiest.

"A game"

Condition

Petya and Vasya play a game: they take turns taking cards from the deck, on which are written non-recurring positive numbers (Petya always takes the first card). Players take cards one by one from the top of the deck. After that, they compare the values ​​recorded on the cards: the player who has less pulls another card and leaves it. When all the cards end, Petya and Vasya count the sum of the values ​​written on these cards. Loses one who has the amount obtained is less than that of another player.

They are tired of manually drawing cards and comparing values. They asked you to write a program that, according to the initial set of cards, will determine the winner.

It is guaranteed that for any test the winner can be determined unequivocally.

  3
 1 2 3 

  Petya 

  3
 1 4 2 

  Vasya 

Decision

Perhaps the easiest way to solve this problem is to simulate a game on a given sequence of numbers. As long as we still have input data, we’ll get three numbers from the input stream, add the first number to Peti’s total points, and the second one to Vasya’s total points. After that, compare two numbers taken from the input stream. If the first is less than the second, then we will add the third number to Petit's points, and if the second is less than the first, we will add the third to Vasya's points. When the input data is finished, let's compare the total number of points scored and find the winner. The solution of the problem is simplified by the fact that all the input data is correct and so-called border situations cannot arise when, for example, the number of points on the cards stretched by the players is the same or when both participants score the same number of points at the end of the game.

“Complicated Numbers”

Condition

Denote by $$$S (n)$ sum of digits of a natural number $$$n$ .

Let's say that a natural number $$$n$ complex if there is no such natural number $$$k,$ what

Find the smallest complex number.

Decision

Here you can come up with a mathematical solution, but all we have to do is find the smallest number that satisfies the condition of the problem. At the same time, neither the proof nor the code need to be written, and we do not have much time for the remaining tasks. Therefore, instead of searching for an informed solution, you can use brute force. Here is one of the choices: search the value of the function for all $$$k$ from 1 to a certain limit (for example, to a million) and, if it is an integer, remember what a number is $$$n$ definitely will not be difficult. Then, we derive the smallest positive integer that we did not remember in the process of calculating our function. In our example, this will be the number 61.

"Standings"

Condition

Many programmers love to play football. Some even like to hold their tournaments. But they do not want to keep track of who scored points and how many places they took, they just want to add the results of the matches to the database, and then get the standings with the number of points scored and the final position.

One of these groups of programmers asked you to help them and, while they are assembling teams and conducting their own tournament, write a program that will build the final standings.

  Linux - Gentoo - 1: 0
 Gentoo - Windows - 2: 1
 Linux - Windows - 0: 2 

  + - + -------- + - + - + - + - + - +
 | 1 | Gentoo | X | L | W | 3 | 1 |
 + - + -------- + - + - + - + - + - +
 | 2 | Linux | W | X | L | 3 | 1 |
 + - + -------- + - + - + - + - + - +
 | 3 | Windows | L | W | X | 3 | 1 |
 + - + -------- + - + - + - + - + - + 

  Cplusplus - C - 1: 0
 Cplusplus - Php - 2: 0
 Java - Php - 1: 0
 Java - C - 2: 2
 Java - Perl - 1: 1
 Java - Haskell - 1: 1 

  + - + ---------- + - + - + - + - + - + - + - + - +
 | 1 | C | X | L |  | D |  |  | 1 | 3 |
 + - + ---------- + - + - + - + - + - + - + - + - +
 | 2 | Cplusplus | W | X |  |  |  | W | 6 | 1 |
 + - + ---------- + - + - + - + - + - + - + - + - +
 | 3 | Haskell |  |  | X | D |  |  | 1 | 3 |
 + - + ---------- + - + - + - + - + - + - + - + - +
 | 4 | Java | D |  | D | X | D | W | 6 | 2 |
 + - + ---------- + - + - + - + - + - + - + - + - +
 | 5 | Perl |  |  |  | D | X |  | 1 | 3 |
 + - + ---------- + - + - + - + - + - + - + - + - +
 | 6 | Php |  | L |  | L |  | X | 0 |  |
 + - + ---------- + - + - + - + - + - + - + - + - + 

Decision

In the programmer's work, such tasks are often encountered when it is necessary to obtain data that has some pre-negotiated format, and to give the result in the form in which the next element of the conveyor waits for it to enter. This task is about correct data processing and their output in the right format. The main difficulty here is to write the input parser and storage. The parser accepts a string as input and saves the results of the game between two teams, and the repository contains the names of the teams and the results.

Due to the rather small amount of input data, it is possible to use not complex structures, but standard mechanisms of any of the available languages. For example, when using C ++, the std::map container is suitable. The key in the container will be the name of the team, and the value will be information about it: the number of points scored, the number of victories and the results of games with other teams. The results can also be stored in std::map , where the key is the name of the opponent, and the value is the result of the match.

Divide each of the rows of the input stream and update the information about each of the participants. std::map , chosen as the repository, allows us to store all the names in lexicographical order, so for the formation of the final table we just need to iterate over the repository elements. When the entire input stream is processed, we calculate the final position of each of the participants: select all pairs of the type “number of points - the number of wins” and arrange them in descending order, arranging the corresponding places for the first three results. In addition, during post-processing, we can calculate the required number of characters for each of the columns of the resulting table, and then carefully implement the output of the table to the output stream.

"Wallets and coins"

Condition

Programmer Peter loves to put all his money in wallets and record how much money is in each wallet. To do this, he saves in the file a set of positive integers - the amount of money that lies in each of his wallets (Peter doesn’t like it when at least one of his wallets is empty). Peter keeps all the money in coins, the denomination of each coin is 1 conventional unit.

Once, Peter had a block of magnetic heads broken and he had to recover data from a hard disk. He wants to check whether the data has been correctly restored, and asks you to make sure that the amount of money he had can be decomposed into all of his wallets so that the same numbers as in the recovered file are obtained.

  2
 2 3
 five 

  Yes 

  2
 2 3
 four 

  No 

  2
 2 3
 3 

  Yes 

Decision

It was necessary to understand that several other wallets may lie in the wallet, where, in turn, there are coins. One of the test examples clearly showed the possibility of such a situation. With this in mind, the task is quite easily reduced to the well-known problem of a backpack , which is solved by the method of dynamic programming. Take the most roomy wallet and fill it with coins. If this cannot be done (that is, the number of coins is less than it is necessary to put in the largest wallet) - there is no way to put the coins into wallets. If we managed to fill the biggest wallet - take all the remaining coins and try to find a way to expand them on the remaining wallets. Here we are - just like in the task about the backpack - we make a choice. Only there we would choose whether to put another item in a backpack.

Restrictions allow us to allocate memory for an array whose size is equal to the remaining number of coins. Then check each remaining wallet to see if we can fill it with the remaining number of coins. If there is a way to distribute coins over a certain subset of wallets, then we will put all unused wallets into the largest one, after having transferred the necessary amount of coins from them to it. If the remaining coins cannot be distributed among a subset of the remaining wallets, there is no successful configuration.

"Good Sequence"

Condition

A sequence of points on a plane is called trivial if it is strictly ordered in ascending or descending order of distance to one of the points of this sequence.

A sequence of points in three-dimensional space is called good if none of the sequences obtained by taking the original projection on one of the base planes $$$(Oxy,$$$$Oyz$ and $$$Oxz),$ not trivial.

Given a sequence of $$$n$ points with integer coordinates in three-dimensional space. It is necessary to find such an odd permutation of its indices, that after its application the sequence becomes good.

It is guaranteed that a solution exists.

  four
 1 1 1
 2 4 16
 3 9 81
 4 16 256 

  1 2 4 3 

Decision

For the correct solution of the problem, it is quite enough for us to estimate how many trivial permutations exist. In each of the planes their number is proportional to $$$O (n)$ where $$$n$ - the total number of points. So, everything in their space will be $$$O (n ^ 3)$ . In this case, the total number of permutations, which can serve as a correct answer, is equal to $$$n! / 2$ (the division is due to the fact that we only need odd permutations). It turns out that unsuitable answers are much less than those that suit us. Therefore, we can simply iterate through the odd permutations. The answer will be the first permutation, which is not trivial when constructing its projection on any of the three planes.

"An interesting journey"

Condition

It is no secret that some programmers love to travel. Well-known programmer Petya also enjoys traveling, visiting museums and seeing the sights of other cities.

To move from city to city, he prefers to use the car. At the same time, it refuels only at stations in cities, but not at stations along the way. Therefore, he very carefully selects the routes so that the car does not stall on the road. And Petya is a very important team member, so he cannot afford to travel for too long. He decided to write a program that will help him with the choice of the next trip. But since he now has too many other tasks, he asked you to help him.

The distance between two cities is calculated as the sum of the difference modules for each of the coordinates. Roads are between all pairs of cities.

  7
 0 0
 0 2
 2 2
 0 -2
 2 -2
 2 -1
 2 1
 2
 13 

  2 

  four
 0 0
 ten
 0 1
 eleven
 2
 14 

  one 

  four
 0 0
 20
 0 2
 2 2
 one
 14 

  -one 

Decision

First, from the existing points you need to build a graph. To do this, let's iterate through all pairs of points and, if the distance between them is less than the specified limit, add an edge between the vertices to the graph. After constructing the graph, we will launch a search wide from the city, from where Peter begins his journey. As soon as it reaches the destination point, we complete our algorithm and derive the number of edges we have passed. If the algorithm is completed, and we have not reached the destination, then it is not reachable from the source city, so you should output -1. The total complexity of the described algorithm is $$$O (n ^ 2)$ where $$$n$ - the number of cities.

"Splitting number"

Condition

Given the number $$$n$ . Break decimal notation $$$n$ to the maximum possible number of different numbers.

Using numbers with insignificant zeros is not allowed.

  0 

  0 

  101 

  10-1 

  102 

  1-0-2 

  eleven 

  eleven 

Decision

Despite the fact that the initial number can be very large, the number of ways to break it apart depends not on the value, but on the number of characters in the number. In the worst case, the number consists of 18 decimal places (we don’t consider option 10 ¹⁹ - there’s only one partitioning option). Hence, the “-” sign can only be put in 17 different positions. In each of these positions, we can both put a sign and lower it. In other words, there are only 2 ¹⁷ ways to choose a partition for the largest numbers. These are about 10 ⁵ options. We will sort them all, cut off those that do not suit us (that is, which give the same numbers), and choose the variant containing the largest number of parts.

“Maximum damage”

Condition

Programmer Igor loves to play computer games. Most of all, Igor likes strategies, especially those moments when he sends groups of his units to attack enemy bases. Igor has been playing strategy for a long time, so he has a well-developed plan of action for the attack: he breaks up all his units into groups and sends them to the attack in turn. At the same time, Igor believes that the total damage that will be inflicted in the attack is equal to the product of the size of the groups. He tries to split his units into groups so as to maximize total damage.

Recently, Igor began to often lose. He is sure that the problem is that in one of the groups, after splitting, an unlucky number of units is obtained. He is trying to remake his partitioning algorithm and asked you to calculate what maximum total damage his group can inflict if there is not one among them containing an unlucky number of units.

  8 2 

  sixteen 

  9 3 

  20 

Decision

If it were not for an additional ban on the use of groups of a certain size, which in the condition is called unlucky, then the product would be maximal when splitting the original number into groups of 3 units. If the total number of units is divided into 3, we simply divide them into groups of 3 units. If the remainder of dividing by 3 is 1, then we separate a group of four units (unless, of course, initially we have more than one unit), and in the other groups we define 3 units each. And finally, if the remainder of dividing by 3 is 2, we separate a group of two units, and in the rest we define 3 units each.

We prove that such a partition is correct. Let's try to prove it by the opposite. Suppose first that there are numbers in our partition $$$x$ ≥ 5. But then we can replace $$$x$ two numbers: $$$x$ -3 and 3. The total amount of the replacement will not affect, and the product of the numbers 3 and $$$x$ -3 is always more than $$$x$ at $$$x$ ≥ 5. So numbers that are greater than or equal to 5 in our sequence cannot exist. Suppose it has the number 4, but we can replace it with two deuces without affecting the values ​​of the sum and the product, so let's do it. Further, in our sequence there can be no more than two twos, otherwise we could replace any three of them with two triples. The value of the sum of this would not change, and the value of the product would increase (8 = 2⋅2⋅2 <3⋅3 = 9). Consequently, three or more twos cannot be either. Well, and besides, we can not have units (only if the initial amount itself is not equal to one). Thus, our resulting sequence can consist only of triples and no more than two twos, as we showed above.

Let us return to the restriction on the unlucky size of the group. If it exceeds the value of 3 - our solution will remain exactly the same. If it is 3, then, going through the small sizes of groups manually, we will divide the sequence into groups of size 2. If the number of units is initially odd, then we additionally take a group consisting of 5 units (since one group of size 5 will provide a greater final value than 2 groups 2 units each and one group of one unit). If group sizes equal to 2 are excluded, then we use the algorithm of division into groups of 3 units. Finally, if their initial number is not divisible by 3, we take as the size of additional groups not 2, but 4 units.

"Red-black trees"

Condition

A red-ebony tree is a tree, in which all the vertices are painted red or black and there are additional properties:

• The root is black.
• Each vertex either has two descendants or is a leaf (no descendants).
• All the leaves of the tree are black.
• At the red peaks, both descendants are black.
• The number of black peaks on the path from the root to any leaf of the tree is the same.

Find the number of non-isomorphic red-black trees with a given number of vertices. Two red-black trees $$$T_1$ and $$$T_2$ are isomorphic if there is a bijection between the vertices of the trees $$$f: V (T_1) \ rightarrow V (T_2)$ satisfying the conditions:

• $$$f (root (T_1) = root (T_2))$ i.e. the root goes to the root.
• If a $$$f (v) = u$ and at the top $$$v$ have kids ( $$$v_l$ and $$$v_r$ ), then at the top $$$u$ have kids ( $$$u_l$ and $$$u_r$ ), at the same time or $$$f (v_l) = u_l$ and $$$f (v_r) = u_r$ , or $$$f (v_l) = u_r$ and $$$f (v_r) = u_l$ .
• $$$f$ preserves the color of the vertices, that is $$$color (v) = color (f (v))$ .

  five 

  one 

  7 

  2 

  6 

  0 

Decision

The problem can be solved by dynamic programming, but it is a bit more complicated than the tasks that we solved by the same method above.

Denote as $$$Countblack [n] [h]$ the number of different black-root red-black trees up to isomorphism, which consist of $$$N$ vertices and in which the number of black vertices from root to leaf is $$$H$ . Behind $$$Countred [n] [h]$ we denote the same trees with a red root. This will violate the black root property of red-black trees, but we need this assumption to calculate the result.

How to calculate the value $$$Countblack [n] [h]$ ? The root of it can be any number. $$$i$ from 1 to $$$N$ . Then the left subtree will contain $$$i-1$ top, and in the right - $$$j = N-i$ vertices. How many subtrees can be in the left subtree? If its root is black, then the number of subtrees is $$$CountBlack [i-1] [H-1]$ , and if red, then $$$CountRed[i-1][H-1]$ . : $$$CountBlack[j][H-1]$ , , $$$CountRed[j][H-1]$ , . , : $$$CountLeft = CountBlack[i-1][H-1] + CountRed[i-1][H-1]$ and $$$CountRight = CountBlack[j][H-1] + CountRed[j][H-1].$ , $$$i$ . , $$$i-1 \leq j$ . If a $$$i-1 < j$ , $$$CountBlack[N][H]$ : $$$CountLeft⋅CountRight$ . ( $$$i-1 = j$ ), $$$CountLeft⋅(CountLeft+1)/2$ .

$$$CountRed[N][H]$ , . -, , . -, , . , $$$i$ , $$$CountBlack[i-1][H]$ , — $$$CountBlack[j][H]$ . .

, $$$CountBlack[N][H]$ $$$H$ . . , , $$$H = 2⋅log(N) ≈ 20$ . $$$H$ 1 20 $$$CountBlack[N][H]$ . .

« »

Condition

$$$k$ $$$n$ , $$$m$ .

, $$$k$ , .

  3 2
1 3 2
2 3 1
 3
1 2 1 

  3
 one
 2 

  2 2
 12
 2 1
 3
1 2 1 

  2
 one
 2 

  eleven
 one
 one
 one 

  one 

Decision

$$$prefix[i]$ , $$$i$ - , $$$k$ permutations. Behind $$$suffix[i]$ , , , $$$i$ - $$$k$ -. , , $$$prefix[i-1]$ , $$$prefix[i]$ , $$$prefix[i-1]$$$$i$ - . — $$$O(n)$ where $$$n$ — . , $$$prefix[i]$ for $$$i$ 1 $$$k$ $$$O(n⋅k)$ . $$$suffix[i]$ , , $$$suffix[i]$ $$$suffix[i+1]$ to $$$i$ - . , , $$$j$ - , $$$prefix[j-1]$ $$$suffix[j+1]$ . $$$prefix[0]$ and $$$suffix[k+1]$ $$$j$ 1 $$$k$ , . $$$j$ $$$O(n)$ , — $$$O(n⋅k)$ .

« »

Condition

$$$n$ .

. , , , , .

, .

  one
 -eleven 

  one 

  3
 -eleven
 0 0
 eleven 

  2 

  five
 0 1
1 0
 eleven
 2 1
 3 2 

  2 

Decision

. , , . 4 , — . , . , . .

« »

Condition

$$$n$ $$$a_1, a_2, …, a_n$ . , : .

?

  2
 eleven 

  0 

  3
9 6 3 

  3 

  6
1000000000 1000000000 1000000000 1000000000 1000000000 1 

 4999999995 

Decision

Let be $$$a$ — . , , $$$2\cdot a$ , . , , , $$$2\cdot a$ . a, , $$$2\cdot a$ , , , $$$2\cdot a$ . , $$$2\cdot a$ , , . , . . $$$S$ . Then $$$S \leq 2na$ , $$$a \geq S/(2n)$ . , $$$1-1/(2n)$ time. $$$O(n\cdot log(Mn))$ , $$$M$ — .