Results and analysis of tasks for the final of the Yandex. Algorithm 2016

On July 29, Minsk hosted the final round of the Yandex Programming Championship. Algorithm . The winner was Egor EgorK Kulikov - a graduate of the Moscow State University and a former employee of Yandex. The second place was taken by Nikola Jokic from the Swiss Higher Technical School of Zurich. As part of the school team, he was a finalist for the ACM ICPC. Third place went to Makoto Soejima , a graduate of the University of Tokyo. Gennady Korotkevich , the winner of the two previous Algorithms, took the sixth place.

As in previous years, we publish a detailed analysis of the final tasks. July 31, we first held a mirror of the algorithm. Therefore, in order not to spoil its participants' pleasure, they did not publish the answers immediately after the final, as we usually do.

This year we received a quarter more applications to participate in the Algorithm than a year ago - 4578. There are still a few girls among the participants - 372. There are representatives of 70 countries in the list of registered participants; most competing - from Russia, India, Ukraine, Belarus, Kazakhstan, USA and China. The final was attended by 25 people.

Tasks for Yandex.Algorithm are Yandex employees and invited experts, among which are the finalists and prize-winners of the ACM ICPC. Under the terms of the competition, participants can use different programming languages. Statistics Yandex. Algorithm shows that the most popular language - C ++; He was chosen by more than two thousand people. The second place was shared by Python and Java.

Objective A. Venue finals

Problem authors : Alexey Tolstikov, Roman Udovichenko

This year, the final Yandex.Algorithm is held at the National Library of Belarus. It should be noted that the building of the library has a very unusual form - a rhombocuboctahedron.

A rhombicobooctahedron is a semiregular polyhedron whose faces are 18 squares and 8 triangles. In total, the rhombicuboctahedron has 24 vertices and 48 edges. An image of a rhombicuboctahedron is shown below:

In this task, you need to determine the number of ways to paint the faces of a rhombocuboctahedron so that no two faces that have a common edge are painted in the same color. In total, there are k colors at your disposal.

Since the answer can be quite large, calculate it modulo 10 ⁹ + 7.

Input Format

The single line of input data contains a single integer k (1 ⩽ k ⩽ 50), the number of colors at your disposal.

Output format

In the only line print the answer to the problem.

Examples

Comment

One of the options for the correct coloring for k = 3 is to paint all triangular faces in the first color (8 faces), all square faces adjacent along the edge with one of the triangular faces, in the second color (12 faces), and all remaining square faces in the third color (6 faces).

Parsing task A

Consider a new graph whose vertices are the faces of a rhombicubooctahedron, and the vertices are connected to the vertices that correspond to the faces adjacent to the side (the so-called dual graph of the polyhedron). Our task takes the following form: we need to calculate the number of correct colorings of the resulting graph in k colors, where the correct coloring is such a coloring that the neighboring vertices are painted in different colors.

Note that our graph is bipartite: its vertices can be divided into two groups consisting of 12 vertices and 14 vertices, so that the edges connect only the vertices of different groups. In fact, the condition even states exactly how this partition is arranged: the first segment of the partition is formed by the vertices, which, in the explanation, are proposed to be painted in the second color, and the second segment - all the others.

We will first paint the first part, and only then the second. Note that with a fixed coloring of the first beat, it’s easy to calculate the number of ways to finish the second beat: we paint each vertex of the second beat separately, which means that the total number of ways is the product of all vertices of the second beat v of k - adj ( v), where adj (v) is the number of different colors among the vertices adjacent v.

Now we must somehow sort out the coloring of the first lobe. If we explicitly touch the color for each vertex, it will require about 50 ¹² ≈ 2.4 · 10 ²⁰ operations, which will not fit into any reasonable timeframe. We will go through not the colors of the vertices themselves, but only their division into identical / different color groups. Namely - for each next vertex during the search, we will decide whether to assign it to one of the existing vertex colors, or whether to create a new one for it. There are not so many such “compressed” colorings, a total of 4,213,597 pieces. Obviously, the information contained in the compressed coloring of the first beat is enough to understand how many ways the second beat can be colored, just remember to multiply this number by the number of ways to turn this compressed coloring into a full coloring (it equals A (k, c ) = k (k - 1) (k - 2) ... (k - c + 1), where c is the number of colors used in the compressed coloring).

If the written solution does not fit into the time limit, but it does not work very long on one test, then you can cheat and use the fact that the limit on k is not very large by calculating all 50 answers to the tests on the local computer and simply driving into the program.

An alternative solution can enumerate the coloring on the belt of 8 medium squares, and then count the number of ways to paint one of the halves and square it, since the upper and lower half of the rhomb cubobooctahedron are colored independently of each other.

Task B. Transform Sequence

Problem authors : Maxim Akhmedov, Gleb Evstropov

You are given a sequence a ₁ , a ₂ , ..., a _n , originally consisting of n zeros. In one move, you can choose any of its sub-slices a _l , a _{l + 1} , ..., a _r , as well as an arbitrary integer x and convert the sequence of this sub-slices, replacing a _{l + k} with a _{l + k} + (−1 ) ^k · x for all integers 0 ⩽ k ⩽ r - l.

It is required to convert the initial zero sequence to the given sequence b ₁ , b ₂ , ..., b _n in the minimum number of moves. There is an important restriction on the sequence b _i : it is guaranteed that all its elements belong to the set {−1, 0, 1}.

Input Format

The first line of input contains a single integer n (1 ⩽ n ⩽ 10 ⁵ ). The second line contains n integers b ₁ , b ₂ , ..., b _n (−1 ⩽ b _i ⩽ 1).

Output format

Print the minimum number of moves needed to convert the original sequence to the required one.

Examples

Comment

In the first test, from the condition one can get the required sequence in one move, in which x = −1, l = 1 and r = 2.

In the second test from the condition, you can act as follows:
0 0 0 0 0 → 2 -2 2 0 0 → 1 -1 1 1 0

Parsing task B

We will gradually understand the design. First, we invert the signs of all the numbers in even positions. Now the operation specified in the condition will be simpler: we are allowed to choose any sub-segment and add the same number t to all the numbers on it.

Since we are dealing with operations of the form “add the same number on the subsegment”, it is useful to proceed to a sequence consisting of the differences of neighboring elements: we move from a ₁ , a ₂ , ..., a _n to the sequence b ₀ = a ₁ , b ₁ = a ₂ - a ₁ , ..., b _i = a _{i + 1} - a _i , ..., b _n = −a _n . In this sequence of elements, one is greater, and it satisfies the special condition that b ₀ + b ₁ + ... + b _n = 0.

Then adding the constant x on the interval [l, r] of the original sequence is equivalent to replacing b _{l − 1} → b _{l − 1} + x and b _r → b _r - x.

In the sequence a _{i there} were integers from −1 to 1, therefore in the sequence b _{i there} will be integers from −2 to 2. In one move, as we have already found out, we can add x to one of the numbers, and subtract from the other x, and we want to ensure that the sequence contains only zeros.

The term “x” is called the “weight” of adding x and −x to two elements of the sequence.

Let us prove an auxiliary fact: if the number b _{i is} greater than (less than) zero, then it is not beneficial to apply operations in which the number b _i increases. Formally speaking, if there is an optimal (i.e., shortest) sequence of operations in which some b _i increases at some time, then a sequence of operations can be presented in which no b _i never increases and which has same length.

Indeed, let two operations be applied to b _i , say 1) b _i → b _i + x, b _j → b _j - x and 2) b _i + x → b _i + x - y, b _k → b _k + y, and, for definiteness, where x, y> 0 and, for definiteness, x ⩽ y.

Let's replace these two operations with two others: 1) b _i → b _i - (y - x) = b _i + x - y, b _k → b _k + y - x and b _j → b _j - x, b _k + y - x → b _k + y - x + x = b _k + y. These are two equivalent operations, they lead to the same results, but you can see that the total weight of the two new operations has decreased: | y - x | + | x | = y - x + x = y <x + y = | x | + | y ​​|.

Repeating such replacements, while it is possible, we will sooner or later stop (because the total weight of operations cannot decrease indefinitely, since it is always whole and non-negative), which means you can find a sequence of operations of the same length, in which any positive element is always only decreases. Similarly, it is possible to ensure that any positive element will only increase.

This allows us to describe all the operations available to us. We can either get rid of −2 and 2 in one move, or get rid of −1 and 1 in one move, or get rid of −2, 1, 1 in two moves, or get rid of 2, −1, −1 in two moves .

It is clear that the total weight of all operations that we perform is the sum of all positive numbers among b _i (which is opposite in sign to the sum of all negative numbers). We now have operations of weight 1 and weight 2, and it is clear that in order to minimize the total number of operations, we need to do as many operations of weight 2 as possible. This leads us to the greedy algorithm, namely, to reduce the two to the minus two, while we can, but when no longer can, reduce edinichki and minus edinichki with what happens.

Thus, the answer is the sum of all positive b _i minus the minimum of the number of twos and the number of minus twos.

Problem C. Hat game

Problem Author : Gleb Evstropov

The hat is a popular game in Russian-speaking countries, designed for a great friendly company. Participants are divided into teams of two and sit in a circle in such a way that everyone sits strictly opposite his partner. The players write a lot of words on small pieces of paper, put them in a hat, after which each of the players in turn tries to explain the word to his partner without naming him explicitly.

Consider the following problem. At the round table sit 2n people. They want to play with a hat, and in some way they have already broken into teams of two. Now they want to move in such a way that each person sits opposite his partner. To do this, they can perform the following operation several times: they select two people from those sitting at the table and ask them to switch places.

You are given the initial arrangement of people at the table. Determine what the minimum number of operations of the type described should be made so that each person sits opposite his partner.

Input Format

The first line of input contains an integer n (1 ⩽ n ⩽ 10 ⁵ ), which means that 2n people are sitting at the table.

The second line contains a sequence of 2n integers. Each integer from 1 to n occurs in this sequence exactly two times. This sequence describes the division of people sitting around the table, into teams, if we write them out in a clockwise order.

Output format

Print the minimum number of operations that need to be performed so that each person is facing his partner.

Examples

Comment

In the first test of the condition, the initial seating is already suitable for playing with a hat.

In the second test from the condition one of the best ways will first swap people sitting in the first and seventh positions, and then swap people sitting in the seventh and eighth positions, which will lead us to the correct seating: 3 1 4 2 3 1 4 2 .

Parsing task C

Consider the following graph: its vertices will be 2n positions at the table, and the edges will be connected, firstly, the vertices corresponding to diametrically opposite positions, and secondly - the vertices corresponding to the positions on which people from the same team are sitting. In particular, if people from the same team are already sitting opposite each other, then between the peaks corresponding to their positions, two ribs will be drawn.

The resulting graph has the property that in it from each vertex there are exactly two edges (one is the diameter and the second is the top in which a person from the same team sits). Such a graph is always a union of some number of cycles.

We strive to achieve a situation where each cycle consists of exactly two diametrically opposite vertices, that is, when there are exactly n cycles of length 2.

Let us understand how our graph changes under the influence of the operation available to us. Let them swap two people from more than one team (otherwise it is a meaningless operation), say, a person from the top of a with a person from the top of b. Let the person's partner a sit at the vertex a ′, and let the person's partner b sit at the top of b ′. Then two edges aa ′ and bb ′ disappear from the graph and two new edges ba ′ and ab ′ are formed (that is, new edges will cross over between the ends of the old ones). It is easy to see that such an operation can either divide one cycle into two, or not change the number of cycles, or glue two cycles together. This means that the answer is no less than n - c, where c is the initial number of cycles. On the other hand, one can always achieve the required exactly in so many moves: it’s enough at each step to take a couple of teammates who do not sit opposite each other, and simply replant one of them so that he sits in front of his partner. This operation strictly increases the number of cycles by one.

Thus, the answer is n - c, where c is the number of cycles, or, equivalently, the connected components in the specified graph. This problem can be solved simply by clearly modeling the process of seating people in pairs, and this is correct for the same reasons as described above.

Problem D. Cumulate me completely

Problem Author : Maxim Akhmedov

You are a simple guy who wants only one thing: to be presented with a binary maximum pile for his birthday, because all of your friends already have one! Finally, you went to the store with your parents, but unfortunately, all the binary heaps ended there, and all that was left was the old full binary tree. It consists of n = 2 ^h - 1 vertices, in which some values ​​are written, which do not necessarily satisfy the main property of the maximum heap. Fortunately, Old Joe agreed to help you turn this tree into a binary heap for a fee.

A complete binary tree of height h is a rooted tree consisting of n = 2 ^h - 1 vertices numbered from 1 to n, such that for any 1 ⩽ v ⩽ 2 ^h-1 - 1 the vertex v is an ancestor of the vertices 2v and 2v + one.

The binary maximum heap of height h is a full binary tree of height h, whose values ​​are h ₁ , h ₂ , ..., h _n at the vertices, and the value at any vertex is not less than the value of its children (if it has children).

You are given a complete binary tree of height h, at the vertices of which are the values ​​a ₁ , a ₂ , ..., a _n . Also, a value c _v is associated with each vertex, meaning that Old Joe can either increase or decrease the value at vertex v by an arbitrary value x> 0 for the cost in c _v x. You can change the values ​​in any number of vertices.

Determine the minimum cost of converting a given full binary tree to a maximum pile.

Input Format

The first line of input contains a single integer n (1 ⩽ n ⩽ 2 ¹⁸ −1), the number of vertices in the complete binary tree that you got. It is guaranteed that n = 2 ^h - 1 for some integer h.

The second input line contains n integers a ₁ , a ₂ , ..., a _n (0 ⩽ a _i ⩽ 10 ⁶ ), the current values ​​of the tree vertices.

The third line contains n integers c ₁ , c ₂ , ..., c _n (0 ⩽ c _i ⩽ 10 ⁶ ), the cost of changing the values ​​at the vertices of the tree.

Output format

Output the minimum cost of converting the given full binary tree to the maximum heap.

Example

Comment

In the test from the condition, the optimal way is to increase the value at vertex 1 by 2 by 4 · 2 = 8 and decrease the values ​​at vertices 6 and 7 by 3 by 2 · 3 = 6 and 3 · 3 = 9, respectively. Thus, the total cost will be equal to 8 + 6 + 9 = 23.

Analysis of task D

We introduce the notation. Let L _v (x) be the minimum price that must be paid for the subtree of the top of v to become a valid heap, and at the very top of v there is a number that does not exceed x. Let S _v (x) be a quantity that is determined absolutely analogously, only at the very vertex v there must be a strictly x number. Then the answer to the problem is equal to the minimum value of the function S _v (x).

For leaf vertices of v, by the condition, we have that S _v (x) = c _v | x - a _v |. Similarly, we can understand that L _v (x) = max {0, c _v (a _v - x)}.

Let us express S _v (x) through L _2v (x) and L _{2v + 1} (x) (that is, the function S of the vertex v through the functions L of its children). The following relation is true:

S _v (x) = c _v | x - a _v | + L _2v (x) + L _{2v + 1} (x).

Indeed, if we put the value of x at the vertex v, then we pay, first, for changing the vertex v itself, and second, we must change the subtrees v in some way so that the value in v turns out to be no less than its value children, and we can get this value from the L function for children.

L _v (x) we now learn to count by S _v (x). But let's stop at this point and suggest what kind of functions L _v and S _{v have} . One can guess that they will be piecewise linear functions of the variable x, but in fact even a stronger condition is true: they will be convex piecewise linear functions (in other words, the slope of each next link increases). Let us prove this strictly: let it be true for vertices 2v and 2v + 1. Then S _v (x), as follows from the formula above, is also a convex piecewise-linear function (since it is the sum of three convex piecewise-linear functions).

Now L _v (x) is easy to obtain from S _v (x): consider the global minimum point S _v (x). Up to this point, S _v (x) decreases, and after it increases. In order to get L _v (x), you just need to replace the ascending section of S _v (x) with a constant horizontal section with a value equal to the global minimum of the function S _v (x).

Note that in order to set the functions L _v and S _v , you need O (size (v)) information about the break points of these functions, where size (v) is the size of the subtree of v. Indeed, the break points in the graph of the function S _v (x) are no more than the total break points in the graphs of the functions S _2v and S _{2v + 1} plus one more break point due to the term c _v | x - a _v |. It turns out the recurrence T (v) = T (2v) + T (2v + 1) + 1 for the amount of information stored in the worst case, the solution of which is T (v) = size (v).

Directly implement the basic formula used in the problem, it is possible for the linear complexity of the size of the merged functions. Thus, the solution for size (v) = nk = n · log ₂ n.

Problem E. Separate and Conquer

Problem Author: Mikhail Tikhomirov

A sequence of numbers is called good if it can be built according to the following rules:

• empty sequence is good;
• if X and Y are good sequences, then XY (concatenation of X and Y) is also
  good;
• if X is a good sequence, and n is any number, then nXn (number n, then all elements of X, and finally, number n) is also a good sequence.

For example, the sequence (1, 2, 2, 1, 3, 3) is good, and the sequence (1, 2, 1, 2) is not.

A sequence is called separable if there is a way to split it into two good subsequences (any of them can be empty). For example, the sequence (1, 2, 1, 2) is separable (since it can be divided into good subsequences (1, 1) and (2, 2)), and the sequence (1, 2, 3, 1, 2, 3) - not.

Consider all sequences of 2n numbers, such that each number from 1 to n occurs exactly twice. How many of them are separable? Find the answer modulo 10 ⁹ + 7.

Input Format

The only input line contains one integer n (1 ⩽ n ⩽ 500).

Output format

Print a single integer - the answer to the problem modulo 10 ⁹ + 7.

Examples

Parsing task E

How to check if a sequence is separable? For this sequence, we construct a graph on n vertices. Connect vertices i and j by an edge if the pairs of corresponding numbers cannot be included in one memory band (i.e., for example, when the numbers are arranged as (i, j, i, j) or (j, i, j, i), but not (i, i, j, j) or (i, j, j, i)). A sequence is separable if and only if the resulting graph is duplex.

Denote by f (n) the number of separable sequences of n pairs of numbers, while the sequences differing in renumbering numbers will be considered identical. We introduce an auxiliary function g (n) —the number of primitive sequences, i.e., separable sequences of n pairs of numbers for which there is exactly one way of dividing into two memory bands (these are exactly the same sequences for which the graph described above is connected) .

Suppose we know the values ​​of g (n), we now calculate f (n). For an arbitrary separable sequence, consider the connected component containing the first number. Let it contain k pairs of numbers, then there are 2k spaces between its elements, in each of which you can put any separable sequence independently of each other. Denote by F (n, k) the number of ways to choose k separable sequences of total length 2n. Then from the reasoning above we get f (n) = g (k) F (n - k, 2k). The values ​​of F (n, k) are trivially recalculated through each other and the next values ​​of f (n).

How to find g (n)? Let us call the configuration of the ways to split 2n elements into two sets and construct the SRP on each of them independently. The number of configurations on 2n elements t (n) is calculated trivially. Subtract from this number all configurations that are not related to primitive sequences, the remaining number will be 2g (n). Consider again the connected component containing the first number, even if there are k pairs of numbers in it. The number of such configurations is 2g (k) T (n - k, 2k), where T (n, k) is the number of ways to select k configurations with a total number of elements 2n. Thus, g (n) = (T (n) - g (k) T (n - k, 2k). The values ​​of T (n, k) are calculated trivially through t (n), which are explicitly. The total complexity of this solution is O (n ³ ).

Problem F. Shot

Problem Author : Oleg Khristenko

Given a sequence a ₁ , a ₂ , ..., a _n , the elements a _{i of} which are fractions written as p / q, where p is an integer and q is a positive integer (while their mutual simplicity is not guaranteed).
Check that for each pair i, j (1 ≤ i <j ≤ n) there exists at least one 1 ≤ k ≤ n such that a _i · a _j = a _k .

Input Format

The first line of the input data contains a single integer n (1 ⩽ n ⩽ 3 · 10 ⁵ ) - the length of the sequence. The next line contains n fractions in p / q format (p and q are integers, | p | ⩽ 10 ⁹ , 1 ⩽ q ⩽ 10 ⁹ ).

Output format

Output "Yes" if for each pair of different i and j there is the required k, and "No" otherwise.

Examples

Parsing task F

Reduce all fractions. We make several observations.

First, if a certain number occurs more than twice, you can delete all its copies.
except for two: it does not affect many of the various pairwise works.

Secondly, we note that in each of the sets 0 <| x | <1 and 1 <| x | there is no more than one number. Indeed, if, for example, on 0 <| x | <1 is more than one number, then from all the numbers presented there we choose two minimum absolute values ​​(say, a and b), take their product ab, and it will have an even smaller non-zero absolute value: 0 <| ab | = | a || b | <min {| a |, | b |}, which means that it does not coincide with any of the numbers in our set. Similarly, with a range of 1 <| x |.

Thus, after reducing and removing duplicates, provided that the answer is Yes, in our set there can be no more than eight numbers: two zeros, two ones, two minus ones, and one number from the specified ranges. So, you can adhere to the following logic: reduce all the numbers, leave no more than two copies of each number. If you get more than eight numbers, the answer is definitely No, otherwise you can consider all the pairs of numbers, the benefit of them quite a bit, and honestly check the required condition.