Analysis of the tasks of the final Yandex. Algorithm 2017

The other day ended with Yandex. Algorithm 2017 - our championship in sports programming. In the final round 25 finalists had to solve six problems in two and a half hours. Gennady Korotkevich from ITMO from St. Petersburg won the first place again - this is his fourth victory after the competitions of 2013, 2014 and 2015. Nikola Jokic of Zurich Swiss Technical University and a graduate of the University of Tokyo, Makoto Soejima, became the second and the third, repeating their last year results. This is how cash prizes were distributed: victory - 300 thousand rubles, second place - 150 thousand, third - 90 thousand.

Applications for participation in the Algorithm 2017 filed 4840 people. More than 60% of them are Russians. In second place in the number of applications - Belarus, followed by Ukraine, India and China. In total, residents of several dozens of countries, including Singapore, Cameroon, Venezuela and Peru, registered for the championship.

We traditionally publish the wording and parsed solutions to the tasks of the final.

Task A. Mountain task

Problem Author : Gleb Evstropov (Yandex, HSE).

Input File Name:	Output File Name:	Time limit:	Memory limit:
standard input	standard output	5 seconds (13 for java)	512 megabytes

Tired of programming contests and solving algorithmic problems, Arkady decided to take a short pause and radically change his occupation. Our hero has always been attracted to the mountains, therefore, using the prize money earned at various competitions, he bought himself a small ski resort and started preparing him for the winter season.

The only route available is $$$n$ control points numbered from $$$1$ before $$$n$ . Control point $$$i$ is on top $$$h_i$ and no two points are at the same height. Since there is only one lift on the track, the descent always starts at the control point number $$$s$ and ends in the checkpoint number $$$t$ . Some $$$m$ pairs of control points are connected by sections of the route that lead from a higher control point to a lower one.

The attractiveness of the section of the route directly connecting the control point $$$u$ with control point $$$v$ , is equal to the height difference of points, i.e. $$$h_u - h_v$ . In this case, the attractiveness of the route, consistently visiting checkpoints $$$v_1, v_2, \ ldots, v_k$ , is called the minimum of the attractiveness of its sites, that is, the minimum among the values $$$h_ {v_1} - h_ {v_2}, h_ {v_2} - h_ {v_3}, \ ldots, h_ {v_k} - h_ {v_ {k - 1}}$ .

Tourists visiting the resort of Arkady, on the one hand, are concerned about the attractiveness of the route, and on the other - its length, which is defined as the number of sections of the route in the route. Since Arkady is no longer strong in solving this kind of problems, then it is you who will have to calculate for each possible route length. $$$x$ from $$$1$ before $$$n - 1$ the greatest possible attraction of the route from $$$s$ at $$$t$ having a length of at least $$$x$ .

Input Format

The first line of the input contains four integers. $$$n$ , $$$m$ , $$$s$ and $$$t$ ( $$$2 \ leq n \ leq 100 \, 000$ , $$$1 \ leq m \ leq 200 \, 000$ , $$$1 \ leq s, t \ leq n$ , $$$s \ ne t$ ) - the number of control points on the track, the number of sections of the track, the number of the starting control point and the number of the final control point, respectively.

The second line contains $$$n$ different integers $$$h_1, h_2, \ ldots, h_n$ ( $$$0 \ leq h_i \ leq 100 \, 000$ ) - heights at which control points are located.

Followed by $$$m$ lines describing sections of the route. AT $$$i$ th of them recorded two numbers $$$u_i$ and $$$v_i$ ( $$$1 \ leq u_i, v_i \ leq n$ , $$$u_i \ ne v_i$ ) meaning $$$i$ section of the route goes from the control point $$$u_i$ to the checkpoint $$$v_i$ . It is guaranteed that no two sections of the route connect directly the same pair of control points that the height of the control point $$$u_i$ more than the height of the control point $$$v_i$ , and that there is at least one route from the control point $$$s$ to control point $$$t$ .

Output format

Output $$$n - 1$ numbers one per line $$$i$ -e of which should be equal to the maximum possible attractiveness of the route from $$$s$ at $$$t$ having a length of at least $$$i$ . If for some $$$i$ there is no route no less than $$$i$ then output in the appropriate line $$$-1$ .

Examples

standard input	standard output
4 4 2 4 3 4 2 1 2 4 2 1 13 3 4	3 one one
3 2 1 3 3 2 1 12 13	2 -one
5 10 1 5 8 6 4 3 1 12 13 14 15 2 3 2 4 2 5 3 4 3 5 4 5	7 3 2 one

Comment

In the first example, there is a direct part of the route from the starting control point to the final one. The appeal of this route is $$$3$ and length $$$1$ . There is also a length path $$$3$ passing through checkpoints $$$2$ , $$$1$ , $$$3$ and $$$4$ c attractiveness equal $$$1$ . For $$$x = 2$ the answer will be the given path of length $$$3$ because it is the most attractive way of at least $$$2$ .

Parsing task A

Note that since all control points are located at different heights and all sections of the route go from higher to lower points, the graph is acyclic. We find its topological sorting (for example, simply by sorting the vertices by height) and we will continue to work with it.

We describe two ways to solve the problem in quadratic time. Method one: enumerate all possible values $$$x$ the fascination of the route, after which leave only the edges in the column $$$(u, v)$ such that $$$h_u - h_v \ geq x$ and find the longest way out $$$s$ at $$$t$ using only such edges. The time of such a decision - $$$O (mC)$ where $$$C = h_s - h_t + 1$ . Second way: dynamic programming $$$d (v, len)$ - the maximum possible length of the route $$$len$ of $$$v$ at $$$t$ . To calculate the value $$$d (v, len)$ consider all the edges $$$(v, u)$ and use relaxation $$$d (v, len) = max (d (v, len), min (d (u, len - 1), h_v - h_u))$ . The time of such a decision - $$$O (nm)$ .

Note that the first of the quadratic solutions described will quickly find the answer for paths with a little excitement, and the second solution is better suited for short paths, and we will try to combine these two approaches. Indeed, for the path length $$$x$ true that his fascination does not exceed $$$C / x$ and vice versa the path of fascination $$$y$ may not be longer than $$$C / y$ . Enter the parameter $$$k = \ sqrt {C}$ . For any way from $$$s$ at $$$t$ it is true that either its length or its fascination does not exceed $$$k$ . We apply both solutions from the second paragraph, launching the first only for $$$c \ leq k$ , and in the second using only the values $$$len \ leq k$ . The total complexity of the solution obtained: $$$O (m \ sqrt {C})$ . Note that, if desired, this solution can be implemented using $$$O (m)$ extra memory.

---

Problem B. Unmanned vehicle

Problem author : Maxim Akhmedov (Yandex, MSU, HSE).

Input File Name:	Output File Name:	Time limit:	Memory limit:
standard input	standard output	4 seconds	512 megabytes

Disclaimer: the situation described in the problem has little to do with the real project of an unmanned vehicle and is solely a figment of the fantasy of the authors of the competition.

As you know, Yandex has recently been developing an unmanned vehicle, in which some of the contestants present in Moscow have a chance to see for themselves. Production of an unmanned vehicle is impossible without rigorous testing at a specially equipped landfill site. As part of this task, you will be asked to check the possibilities for moving an unmanned vehicle around a landfill that has a tree view.

Polygon consists of $$$n$ sites connected $$$n - 1$ by roads. Sites are numbered from $$$1$ before $$$n$ and the unmanned vehicle is initially on $$$1$ th site. The purpose of testing is to spend the car for the minimum time on a route that passes through each of the sites at least once, if it is known that the car passes one road in one minute, and the time for turns and turns can be neglected.

The task is complicated by the fact that in the framework of this experiment, navigation can be carried out only by special radio beacons. At each site there is a radio beacon, with the charge of the included radio beacon located on the site $$$i$ , grabs exactly on $$$a_i$ minutes Being turned off, the beacon does not spend the charge. Initially, all radio beacons are turned off.

The process of moving is as follows. Only one beacon can be switched on at a time. If at the beginning of the minute the car is on site $$$i$ and the beacon is located on the site $$$j$ and included for $$$t$ minutes then the car moves on $$$t$ roads in the direction of reducing the distance to the site $$$j$ . If the car is already on the same site with the beacon, then nothing happens. Each beacon can be switched on for an integer number of minutes, an arbitrary number of times.

Determine whether it is possible to draw up a plan for switching on and off beacons in such a way that the car visits all the sites at least once, and if so, find the minimum number of minutes required for this. Return to the original site is not required .

Input Format

The first line contains an integer $$$n$ ( $$$1 \ leq n \ leq 200 \, 000$ ) - the number of sites.

The second line contains integers. $$$a_1, a_2, \ ldots, a_n$ ( $$$0 \ leq a_i \ leq 10 ^ 6$ ) where $$$a_i$ - the number of minutes for which there is enough charge in the beacon at the site $$$i$ .

In subsequent $$$n - 1$ the lines contain descriptions of the roads, each of which consists of two integers $$$u_i$ and $$$v_i$ ( $$$1 \ leq u_i, v_i \ leq n$ , $$$u_i \ neq v_i$ ) - numbers of connected sites.

Output format

If possible, output a single integer - the minimum time required to visit all sites. Otherwise, print the number $$$-1$ .

Examples

standard input	standard output
7 0 3 0 2 4 3 3 12 13 3 4 15 5 6 6 7	9
four 0 1 1 2 12 2 3 14	-one

Comment

In the first test from the condition the following route is suitable, for example:

• For 2 minutes, we keep the radio beacon on site 4, as a result of which the car is on site 4, and the beacon is discharged.
• For 3 minutes, we keep the radio beacon on at site 2, as a result of which the car is at site 2, and the beacon is discharged.
• For 2 minutes, we keep the radio beacon on at site 5, as a result of which the car is at site 5, and the lighthouse has 2 minutes of charge.
• For 2 minutes, we keep the radio beacon on at site 7, as a result of which the car is at site 7, and the lighthouse has 1 minute of charge.

Thus, in 9 minutes you can visit all the sites.

Parsing task B

This task proposes to deal with how you can navigate the tree using unusual travel rules. Instead of the car task used in the legend, we assume that there is a chip on the tree, and buttons are located at the tree tops, and pressing one button is equivalent to turning on the beacon for 1 second.

Thus, we have a tree, at the top of which there is a chip, which also has a set of buttons: at the top $$$i$ located $$$a_i$ buttons, clicking on which, it is necessary to carry the car around the tree.

A useful technique for solving a problem is often the consideration of a simpler problem, differing in some minor detail. In this case, it is useful to consider a statement in which the chip at the end must necessarily return to the starting vertex. A distinctive detail of this formulation is that in such a formulation for each edge, the chip will be required to pass at least twice (one way or the other), which is wrong for the original problem. For several reasons, this task is simpler than the original one.

Note that after choosing a route for its correct passage, it is necessary to compare each button along its edge with its own button in the part of the tree located behind the end of the edge being passed. It is easy to see that the optimal desired route will pass along each edge not just at least twice, but, in fact, exactly two times, because otherwise we will need to match the buttons to a larger number of edges, which is obviously more difficult.

Conversely, if we were able to compare each button to each oriented edge, then we can consider an arbitrary so-called. Euler tree traversal, and then, using the existing mapping, successfully accomplish this traversal.

Hence, the answer to our problem (in a simplified formulation) is always $$$2n - 2$ (such is the length of any Eulerian tree traversal), and the only thing to check is that there is a juxtaposition of buttons to edges, satisfying the condition that the edge corresponds to a button in the subtree indicated by this edge. This task is, in fact, the task of matching in a bipartite graph (one of which is a set of oriented edges, and the other is a set of buttons) that saturates one of the shares. The classical fact of the theory of matching, known as Hall's lemma, gives an answer to the question about the presence of such a matching.

We introduce the notation - let $$$E$ This set of oriented edges of the tree, $$$B$ - many buttons, and $$$s (e)$ for $$$e \ in E$ this is the set of buttons that are in the subtree pointed to by the edge $$$e$ (formally speaking, the button $$$b \ in s (e)$ if and only if the edge end $$$e$ lies between the beginning of the edge $$$e$ and button $$$b$ ). Then Hall’s lemma says that the matching match we have exists exists if and only if for any set of oriented edges $$$A \ subseteq E$ in the union of the subtrees of all the edges in $$$A$ there are no fewer buttons than edges in the set $$$E$ :

$$

$$| A | \ leq \ left | \ bigcup \ limits_ {e \ in A} s (e) \ right |$$

For brevity, we will denote the union of the sets of buttons on the right side of this inequality for $$$s (a)$ . It is not yet clear how this criterion can be effectively verified, because it consists of an exponential number of conditions that correspond to the subset selection options. $$$A$ . However, as we shall see, most of the conditions tested are superfluous.

First, if the set $$$A$ such that in $$$A$ there is one and the same edge in two directions, or there are two edges $$$e_1$ and $$$e_2$ looking at each other, then $$$s (a)$ coincides with the set of all buttons in the tree, which means that regardless of the choice of such a set $$$A$ , on the right side of the inequality there will be the same edge. Hence, of all these inequalities, it is enough to check one of the strongest, namely, in which $$$A$ matches with $$$E$ Moreover, this check has a visual meaning - in fact, we check that there are no more oriented edges than there are buttons in the tree. We denote this condition by $$$(1)$ .

Otherwise, do the same. If a $$$e \ in A$ , you can add in the same way $$$E$ all edges that lie in a subtree $$$e$ and look the same way as $$$e$ (that is, the addition of which does not lead to the case described above). Indeed, the addition of such edges does not change the set of buttons covered by subtrees, which means that this only strengthens the condition we are testing.

Now it is clear what structure has many $$$A$ and the corresponding many buttons $$$s (a)$ . Lots of $$$A$ consists of a set of non-intersecting subtrees, in each of which all edges are taken, looking from the root of the subtree, and $$$s (a)$ is the union of the buttons for all these subtrees. Note that if the whole set $$$A$ not satisfied (i.e., $$$| A | > | s (A) |$ ), then at least in one of the subtrees in the composition $$$A$ also not satisfied, otherwise it can be summed up the corresponding inequalities for all subtrees to show that the set $$$A$ must also be satisfied.

So we finally understood for which subsets $$$A$ it suffices to verify the criterion from Hall’s lemma: it suffices to consider $$$2n - 2$ subsets, each of which is defined by a "root" oriented edge $$$e$ , and contains all edges looking in the direction $$$e$ in subtree $$$e$ . Again, the inequality for a given subset has a clear physical meaning - it is necessary that for any subtree of buttons in it there are no less than undirected edges in it plus one (here, plus one is taken from the root edge itself). We denote this condition for an oriented edge. $$$e$ behind $$$(2_e)$ .

Condition $$$(1)$ obviously you can check in linear time. Of conditions $$$(2_e)$ they are a linear quantity by themselves, but by simple preconception of the sizes of the tree subtrees and the number of buttons in them, all conditions can be checked for linear time in total.

Thus, we have learned to solve a simplified version of the problem. Let us return to the original one - it is distinguished from ours by the fact that now not for every edge we will go in both directions. It is easy to see that our path is now characterized by the final peak. $$$t$ , which is sure to be a sheet, and then from the set of oreintilated edges we visit, the edges lying on the way from $$$t$ to the starting peak $$$1$ . Let's hang a tree by the top $$$1$ then in another way it can be said that all the ascending edges from $$$t$ before $$$1$ .

Similarly, apply the Hall criterion and see what changes. The argument about the ribs looking at each other is still true, and it gives us the condition $$$(1 ')$ : oriented edges, which we pass, should be no more than the buttons of all. Note here that we will pass exactly $$$2n - 2 - depth (t)$ edges, thus, this condition sets the lower boundary to the depth of the desired terminal vertex $$$t$ : $$$depth (t) \ geq 2n - 2 - | B |$ (note that this condition can be met automatically if $$$2n - 2 \ leq | B |$ ).

The reasoning about the independent verification of the criterion for subnotes, defined by the oriented edge and all that lie in its subtree, is still true, but now the form of these subsets will change a little. Namely, if $$$e$ - an edge looking down, nothing will change for it (because compared to the simplified task, only the edges looking up have disappeared). If $$$e$ - edge looking up, then depending on the choice of the vertex $$$t$ edge $$$e$ it can either disappear from the bichromatic graph (then the condition corresponding to it simply does not need to be checked), or else, the left side of the condition corresponding to it will decrease by the number of fallen edges that lie in the subtree $$$e$ and look the same way as $$$e$ . It is easy to understand that the magnitude of the decrease in the left part is $$$depth (lca (e, t))$ where $$$lca (e, t)$ - the smallest common ancestor of the edge $$$e$ and terminal vertex $$$t$ in a hanging tree with root in $$$1$ .

Thus, we have a set of conditions of the following form:

$$

$$2n - 2 - depth (t) \ leq | B | \ quad (1 ')$$

For edges looking down:

$$

$$| edgesBelow (e) | + 1 \ leq | buttonsBelow (e) | \ quad (2_ {e \ downarrow} ')$$

For edges looking up:

$$

$$| edgesAbove (e) | + 1 - depth (lca (e, t)) \ leq | buttonsAbove (e) | ~ \ text {or} ~ t ~ \ text {in the subtree} ~ e \ quad (2_ {e \ uparrow} ')$$

Conditions $$$(2_ {e \ downarrow} ')$ check for linear time immediately, since they do not depend on the choice $$$t$ . The remaining two kinds of conditions are reformulated as a condition on the position of the vertex $$$t$ . $$$(1 ')$ as already noted, equivalent to the fact that the top $$$t$ low enough, that is, at a minimum depth $$$2n - 2 - | B |$ . Condition $$$(2_e ')$ it turns out to be equivalent to belonging $$$t$ to some subtree of our tree: indeed, moving to the left side of the inequality $$$(2_ {e \ uparrow} ')$ addend $$$depth (lca (e, t))$ , we obtain the constraint from below to the depth of the vertex, in which the path to $$$t$ branches off from the path to $$$e$ . It means that $$$t$ should be lower ( $$$| edgesAbove (e) | + 1 - | buttonsAbove (e) |$ ) -th vertex on the way from $$$s$ before $$$e$ which is also a condition of belonging to some subtree.

Note that the set of conditions of the form " $$$t$ belongs to a given subtree "can be checked for linear time - it is enough to bypass the tree, maintaining the number of satisfied conditions, and follow the vertices to which this number coincides with the number of conditions in general.

Finally, it is necessary to choose the deepest of all suitable vertices, check the condition in it $$$(1 ')$ , and it will be the desired answer. This solution can be implemented in linear time from the input data.

---

Problem C. No less dense than required

Problem author : Maxim Akhmedov (Yandex, MSU, HSE).

Input File Name:	Output File Name:	Time limit:	Memory limit:
standard input	standard output	3 seconds	512 megabytes

The density of an undirected graph is a natural quantity, assumed to be equal to the ratio of the number of edges to the number of vertices. An important task in the study of various graphs taken, including from real life (such as the graph of friendships in a social network, graph co-authorship in a scientific environment, or a network of protein-protein interactions in bioinformatics), is finding dense subgraphs - that is, sets of vertices such that the restriction of the graph to this set has a high density. Finding high-density subgraphs is a well-studied, but quite challenging task, and we will offer you an unusual look at this plot - we will offer to find a subgraph of at least a given density.

Consider an undirected graph consisting of $$$n$ vertices numbered with integers from $$$1$ before $$$n$ and $$$m$ ribs $$$(u_ {1}, v_ {1}), (u_ {2}, v_ {2}), \ ldots, (u_ {m}, v_ {m})$ . Let a set of $$$n$ nonnegative real numbers $$$x_1, x_2, \ ldots, x_n$ satisfying the condition $$$x_1 + \ ldots + x_n = 1$ . Put:

$$

$$\ lambda = \ sum \ limits_ {i = 1} ^ {m} \ min \ {x_ {u_i}, x_ {v_i} \}$$

It is required to find a subgraph of this graph having a density of at least $$$\ lambda$ . Formally, it is required to find such a non-empty set of vertices. $$$A \ subseteq \ {1, 2, \ ldots, n \}$ , what $$$\ frac {| E (A) |} {| A |} \ geq \ lambda$ where $$$E (A) = \ {(u_i, v_i) ~ \ mid ~ u_i, v_i \ in A \}$ .

Input Format

The first line contains two integers. $$$n$ and $$$m$ ( $$$1 \ leq n \ leq 200 \, 000$ , $$$0 \ leq m \ leq 200 \, 000$ ), the number of vertices and edges in the graph.

In the second line are $$$n$ real numbers $$$x_1, x_2, \ ldots, x_n$ ( $$$x_i \ geq 0$ , $$$x_1 + \ ldots + x_n = 1$ ), given with no more than six digits after the decimal point.

AT $$$i$ of the next $$$m$ rows are two integers $$$u_i, v_i$ ( $$$1 \ leq u_i, v_i \ leq n$ , $$$u_i \ neq v_i$ ), specifying vertices, connected $$$i$ m edge of the graph. It is guaranteed that there are no multiple edges and loops in the graph.

It is guaranteed that there is a subgraph in the graph that satisfies the requirement of the problem.

Output format

In the first line print an integer $$$k$ ( $$$1 \ leq k \ leq n$ ) - the number of vertices in the desired set $$$A$ .

In the second line print $$$k$ integers $$$d_1, d_2, \ ldots, d_k$ - the numbers of the vertices forming the density subgraph at least $$$\ lambda$ .

Your answer will be recognized as correct if the density of the subgraph that you derived is not less than $$$\ lambda - 10 ^ {- 7}$ . Vertices can be displayed in any order. If there are several possible answers, it is allowed to display any correct one.

Examples

standard input	standard output
4 4 0.2 0.1 0 0.7 12 2 3 3 1 3 4	3 1 2 4
5 6 0.25 0 0.25 0.25 0.25 2 1 13 3 5 5 4 4 1 15	four 1 5 3 4

Comment

In the first test of the condition: $$$\ lambda = \ min \ {0.2, 0.1 \} + \ min \ {0.1, 0 \} + \ min \ {0, 0.2 \} + \ min \ {0, 0.7 \} = 0.1 + 0 + 0 + 0 = 0.1$

In a subgraph consisting of vertices $$$1$ , $$$2$ and $$$4$ , the only edge is present $$$(1, 2)$ therefore its density is $$$1/3> 0.1$ .

In the second test from the condition:

$$

$$\ begin {eqnarray} \ lambda = \ min \ {0, 0.25 \} + \ min \ {0.25, 0.25 \} + \ min \ {0.25, 0.25 \} + \ min \ {0.25, 0.25 \} + \ min \ {0.25, 0.25 \} + \ min \ {0.25, 0.25 \} \ nonumber \\ = 0 + 0.25 + 0.25 + 0.25 + 0.25 + 0.25 = 1.25 \ nonumber \ end {eqnarray}$$

In a subgraph consisting of vertices $$$1, 5, 3, 4$ , there are 5 edges $$$(1, 3), (3, 5), (5, 4), (4, 1), (1, 5)$ therefore its density is $$$5/4 = $ 1.2$ .

Parsing task C

We note an obvious fact: if we could effectively find the subgraph of maximum density in a given graph, it would be exactly suitable as an answer, regardless of the set of values $$$x_i$ (since we are guaranteed that the answer exists). However, since the task of finding the subgraph of the highest density is rather difficult, which we clearly stated in the problem statement, it means that we must somehow use the values ​​given to us $$$x_i$ as a hint.

The following fact is true. Set $$$A (t) = \ {v ~ \ mid ~ x_v \ leq t \}$ . It is argued that the answer can always be found among all sorts of $$$A (t)$ , that is, among subgraphs formed by some suffix of vertices in the sort order by $$$x_i$ there is always at least one density subgraph no less $$$\ lambda$ . We show this fact.

We set, similarly, $$$E (t) = E (A (t)) = \ {(u, v) ~ \ mid ~ x_u \ leq t, x_v \ leq t \}$ . Consider the function $$$f (t) = | E (t) | - \ lambda | A (t) |$ . Let us argue by contradiction - suppose that it is strictly less than zero at each point of the half-interval $$$[0, M)$ (which just means that for any $$$t$ subgraph density $$$A (t)$ equal to $$$\ frac {| E (t) |} {| A (t) |}$ strictly less $$$\ lambda$ ).

Denote by $$$M$ maximum of numbers $$$x_i$ . Then $$$\ int \ limits_ {0} ^ {M} f (t) dt <0$ . However, the following chain of equalities is true:

$$

$$\ begin {eqnarray} \ int \ limits_ {0} ^ {M} f (t) dt = & \ int \ limits_ {0} ^ {M} | E (t) | - \ lambda \ int \ limits_ {0} ^ {M} | A (t) | \ nonumber \\ = & \ int \ limits_ {0} ^ {M} \ sum \ limits _ {(u, v) \ in E} \ mathbf {1} \ {x_u \ leq t, x_v \ leq t \} ~ dt - \ lambda \ int \ limits_ {0} ^ {M} \ sum \ limits_ {v = 1} ^ {n} \ mathbf {1} \ {x_v \ leq t \} ~ dt \ nonumber \\ = & \ sum \ limits _ {(u, v) \ in E} \ int \ limits_ {0} ^ {M} \ mathbf {1} \ {x_u \ leq t, x_v \ leq t \} ~ dt - \ lambda \ sum \ limits_ {v = 1} ^ {n} \ int \ limits_ {0} ^ {M} \ mathbf {1} \ {x_v \ leq t \} ~ dt \ nonumber \\ = & \ sum \ limits _ {(u, v) \ in E} \ min \ {x_u, x_v \} - \ lambda \ sum \ limits_ {v = 1} ^ n x_v \ nonumber \\ = & \ lambda - \ lambda = 0 \ nonumber \ end {eqnarray}$$

Thus, we get a contradiction, which means that at least at one point the semi-inverted $$$[0, M)$ true inequality $$$f (t)> 0$ that proves our statement.

Thus, the solution takes the following form: we arrange the vertices in descending order. $$$x_i$ , add vertices one by one and support the number of vertices in the current subgraph. If the density is not less $$$\ lambda$ , we derive the answer. The complexity of the resulting solution - $$$O (n \ log n + m)$ .

---

Task D. Shop hats

Problem Author : Mikhail Tikhomirov (MIPT)

Input File Name:	Output File Name:	Time limit:	Memory limit:
standard input	standard output	2 seconds	512 megabytes

Lined in the shop window $$$n$ hats numbered from left to right of $$$1$ before $$$n$ . Hats are of three types: male, female and universal. Buyers enter the store one by one, and each next buyer may turn out to be both a man and a woman.

Each customer goes along the window from left to right and chooses the first hat that fits him. So, the male buyer will choose the leftmost among the men's and universal hats, and the female buyer will choose the leftmost among the female and universal hats. If there are no suitable hats in the shop window, the buyer leaves without buying. Every time someone buys one of the hats, the seller records the number of the hat purchased.

By the end of the day, all the hats were sold out, and the seller had a transposition of numbers from $$$1$ before $$$n$ . How many options are there for this permutation? Since the answer can be quite large, determine the remainder of its division by $$$10 ^ 9 + 7$ .

Input Format

The first line contains a single integer. $$$n$ ( $$$1 \ leq n \ leq 5000$ ) - the number of hats in the window.

The second line is written $$$n$ characters - types of hats in the order of numbering. The symbol "M" means a man's hat, the symbol "W" - a woman's hat, and the symbol "U" - a universal hat.

Output format

Output the remainder of the answer divided by $$$10 ^ 9 + 7$ .

Example

standard input	standard output
3 Umw	2
3 MWU	four

Comment

In the first example, the first buyer must buy the first hat (regardless of gender). The remaining two hats can be purchased in any order.

In the second example, the following permutations are possible: $$$(1, 2, 3)$ , $$$(1, 3, 2)$ , $$$(2, 1, 3)$ , $$$(2, 3, 1)$ .

Analysis of task D

At any given time, some of the most left-handed male, female and universal hats should be sold, so you can come up with a simple solution for $$$O (n ^ 3)$ dynamic programming method: count the number $$$dp_ {m, w, u}$ - how many ways are there to be in the configuration in which it is sold $$$m$ first male $$$w$ first female and $$$u$ first universal hats.

It turns out that only $$$O (n ^ 2)$ States in this scheme DP is achievable. We will present another solution using DP. In the current configuration, we denote $$$i$ and $$$j$ the positions of the left-most unsold hats, which are suitable for men and women, respectively (if there are no suitable hats left, we put the corresponding index equal to $$$n + 1$ ). It is easy to make sure that all universal hats are to the left of the position. $$$\ max (i, j)$ must be sold. Let's pretend that $$$i \ geq j$ . If a man buys a hat, then we just move the index $$$i$ to the closest matching hat to the left. However, if a woman buys a hat, we must move forward. $$$j$ skipping universal hats. Also, if $$$i = j$ then $$$i$ hat universal and the next buyer (regardless of gender) will buy it, so the only move is to move $$$i$ and $$$j$ simultaneously to the nearest suitable positions. As a result, we obtain a solution with asymptotics $$$O (n ^ 2)$ .

---

Task E. Time to share the stones

Problem author : Oleg Khristenko (MSU, MIPT).

Input File Name:	Output File Name:	Time limit:	Memory limit:
standard input	standard output	1 seconds	512 megabytes

On one planet in a distant galaxy, the following legend exists:

At the beginning of time, the demiurge Jan Dex created a temple on the highest mountain in the world. In the center of the temple there is an altar on which lies a heap of $$$n$ precious stones. Every morning, two priests - a teacher and a student - begin to divide these stones, taking a non-zero amount of stones from the pile in turn. The teacher makes the first move; while the student at any point in time can not have more stones than a teacher. As a result, the stones should be divided equally, and not a single stone should remain on the altar.

At the moment when the priests will not be able to perform the task, or they will exactly repeat all the actions taken during the division in one of the previous days, the evil spirit-destroyer Bug will be released and destroy the planet.

For a given amount of stones $$$n$ calculate the maximum possible time for the existence of this world from the beginning of time to the coming of the Bag. Since the answer can be very large, output the remainder of its division by $$$10 ^ 9 + 7$ .

Input Format

Single line of input contains one integer $$$n$ ( $$$1 \ le n \ le 10 ^ 6$ ) - the number of gems on the altar.

Output format

Print a single integer - the maximum possible time of the planet existence in accordance with the legend in days modulo $$$10 ^ 9 + 7$ .

Examples

standard input	standard output
6	five
one	0

Parsing task E

This task is the easiest task of the competition. In fact, it is necessary to see in it an unusual reformulation of the well-known mathematical construction.

We reformulate the process of dividing stones. We assume that the teacher and the student go not in turns but in an arbitrary order, but the condition is still fulfilled that at no point in time will the number of stones at the student exceed the number of stones at the teacher. It is easy to see that such a reformulation is equivalent - each variant of the development of events of the original task is in one-to-one correspondence with the variant of the development of events of the reformulated problem.

Now it is easy to see that the condition on the number of stones is equivalent to the condition of the correctness of the bracket sequence of a string in which the symbol \ texttt {'('} corresponds to the teacher taking the stone, and the symbol \ texttt {')'} corresponds to the student taking the stone. As is well known from combinatorics, the number of regular bracket sequences of length $$$k$ equally $$$k$ number of Catalan, the formula for which looks like $$$\ frac {(2k)!} {k! (k + 1)!}$ . Now you need to carefully perform calculations on the module $$$10 ^ 9 + 7$ and get the answer to the problem, not forgetting to make out the case when the number $$$n$ odd and the answer is obviously 0.

---

Problem F. Playing with XOR

Problem Author : Lewin Gan (Dropbox)

Input File Name:	Output File Name:	Time limit:	Memory limit:
standard input	standard output	2 seconds	512 megabytes

Alice and Bob play with a list of $$$n$ integers $$$a_1, a_2, \ ldots, a_n$ .

First, Alice selects a positive integer. $$$k$ (not necessarily from the list) and reports it to Bob. Then Alice and Bob take turns in turns, taking the whole numbers from the list until the list is empty; Bob goes first.

At the end of the game, it is determined whether Alice can choose among her numbers a subset with a bitwise $$$\ operatorname {XOR}$ - sum exactly $$$k$ and if so, she wins, otherwise Bob wins.

Help Alice determine which values $$$k$ She can win in this exciting game.

Input Format

The first line contains a single integer. $$$n$ ( $$$2 \ leq n \ leq 15$ ).

The next line contains $$$n$ integers $$$a_1, a_2, \ ldots, a_n$ ( $$$1 \ leq a_i \ leq 10 ^ 9$ ).

Output format

— $$$m$ , .

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

Examples

four 3 1 3 2	3 1 2 3

, $$$k$ $$$1$ , $$$2$ and $$$3$ . , , $$$k=1$ . , $$$1$ , $$$1$ . , $$$2$ . $$$3$ , $$$1$ $$$2 \operatorname{XOR} 3$ .

F

:

• .
• $$$A,B$ $$$A+B$ $$$A-B$ .
• $$$span(A)$ , xor- $$$A$ (, ).
• $$$rank(A)$ , $$$span$ , as $$$A$ .

, $$$A$ . , , $$$B_1$ and $$$B_2$ , $$$span(A+B_1) = span(A+B_2)$ and $$$k \in span(A+B_1)$ . , $$$B_1$ and $$$B_2$ $$$span(A)$ , $$$span$ $$$A$ .

, $$$B_1,B_2$ $$$span(A+B_1) = span(A+B_2)$ and $$$k \in span(A+B_1)$ , , .

$$$rank(A+B_1) - rank(A)$ , . 0, $$$k$ $$$span(A)$ , .

, $$$B_1,B_2$ . $$$B_1$ or $$$B_2$ , . , $$$B_1$ and $$$B_2$ , $$$B_1$ and $$$B_2$ , , , . $$$p$ , , $$$B_1$ , $$$span((A+{p}) + B_1 - {p}) = span(A+B_1) = span(A+B_2) = span((A+{p})+B_2)$ $$$p \in span(A+B_2)$ . , $$$B_1' = B_1-{p}, B_2' = B_2$ .

, $$$p$ of $$$B_1$ . , $$$p \notin span(A)$ , $$$rank(A+\{p\}) > rank(A)$ . , , $$$A + B_1$ and $$$A + B_2$ $$$p \in (A + B_1) - (A + B_2) = B_1$ , $$$q$ at $$$(A + B_2) - (A + B_1) = B_2$ , $$$span(A + B_2 - \{q\} + \{p\}) = span(A + B_2)$ . , $$$B_1' = B_1 - p, B_2' = B_2 - q$ .

. , $$$A$ , . , $$$B_1,B_2$ such that $$$span(A+B_1) = span(A+B_2)$ and $$$k \in span(A+B_1)$ .

, . , , . , $$$rank(A+B_1) - rank(A)$ (, $$$B_1$ , — ).

If a $$$k \in span(A)$ , , 0 , ( ) $$$B_1$ and $$$B_2$ .

, $$$k \notin span(A)$ . , $$$p$ , $$$q$ . $$$X_1$ and $$$X_2$ such that $$$span(A+X_1+\{q\}) = span(A+X_2+\{q\})$ and $$$k \in span(A+X_1+\{q\})$ . , , $$$k \notin span(A+X_1)$ ( $$$B_1 = X_1$ , $$$B_2 = X_2$ ).

, , , $$$q$ . $$$r$ . , $$$Y_1$ and $$$Y_2$ such that $$$span(A+Y_1+\{r\}) = span(A+Y_2+\{r\})$ and $$$k \in span(A+Y_1+\{r\})$ (, , $$$k \notin span(A+Y_1)$ ).

, $$$q$ $$$X_1, X_2, Y_1, Y_2$ .

$$$Z_1 = Y_2 + X_2 + \{r\}$ and $$$Z_2 = Y_1 + X_1 + \{r\}$ .

notice, that $$$k \in span(A+Z_1)$ $$$k \in span(A+Y_2+\{r\})$ and $$$A+Y_2+\{r\} \subseteq A+Z_1$ . , $$$span(A+Z_1) = span(A+Y_2+X_2+\{r\}) = span(A+Y_2+X_2+\{k\}) = span(A+Y_1+X_1+\{k\}) = span(A+Z_2)$ .

$$$Z_1' = Z_1 - Y_1$ and $$$Z_2' = Z_2 - Y_2$ . , $$$Z_1' \cap Z_2' = {r}$ . , $$$rank(A+Z_1') = rank(A+Z_1)$ , $$$y \in Y_1$ $$$span(A+Y_2+\{r\})$ , , $$$span(A+Z_1') = span(A+Z_2')$ .

, $$$B_1 = Z_1' + \{q\} - \{r\}$ and $$$B_2 Z_2'$ . , $$$k \not\in span(A+Z_1'-\{r\})$ , $$$q \in span(A+Z_1')$ , .

, , , — . $$$span$ $$2 n subsets, after which we explicitly iterate$2 ^ n$$$$3 ^ n$ pairs of disjoint subsets and for suitable ones (containing $$$k$ in his $$$span$ 'e) we note all of them $$$span$ as suitable for inclusion in the response. The total complexity of the solution - $$$O (3 ^ n \ cdot n)$ .