Online Round 3 and its analysis were prepared by Chmel_Tolstiy, aropan, Romka, SobolS, Ra16bit, snarknews and Gassa.

During the third round of “Yandex.Algorithm” 265 participants have made at least one attempt, 177 of them solved at least one problem. There were 559 attempts for A (137 successful), 127 attempts for B (47 successful), 111 attempts for C (64 successful), 64 attempts for D (15 successful), 45 attempts for E (20 successful) and 606 attempts for F (129 successful).

Problems of the Round 3 proved to be easier on average than the problems of the first two rounds, and it became apparent during the contest that the winner would probably solve all problems. Indeed, Petr has solved all problems by the 72nd minute, although all of them were submitted “open”. Five minutes till the end of the contest KADR takes 2nd place with 6 problems, he has also solved all problems “open”. But almost immediately nkurtov (Nikolay Kurtov, Switzerland) solves his 6th problem and takes 1st place, as he has solved three problems “blind”. Two minutes before the end of the contest winger takes place with two problems submitted “blind” in the beginning of the round and all others submitted “open”. And at the last minute s.quark (s-quark) from China submits problem E “blind” and takes the first place: he has submitted only B “ open”. Overall five participants have solved all problems before the system test: s.quark is 1st, nkurtov — 2nd, winger — 3rd, Petr — 4th and KADR — 5th.

After the system tests it turns out that s.quark's F which he submitted “blind” on the 25th minute failed. Also nkurtov's С and D failed. Both winger's “blind” solutions passed, so he took the final 1st place in the Online Round 3. Petr took the 2nd place, but he had already qualified to the finals before. KADR stayed at the 3rd place, ainu77 (ainu7) from South Korea moved to 4th, and s.quark still took 5th place even after failing a problem and qualified to the final round.

Problem A (Candy Mood)

Let us count the number of candies M that are not tasty. If M = 0, the answer is . Otherwise, consider the expected increase in the mood braught by i-th candy if it is tasty. It can be equally probable in M + 1 positions relative to the not tasty candies, and only in one case you will eat the tasty one. So, the expected increase in the mood braught by one tasty candy A_i is equal to . For candies that are not tasty the expected change in the mood is , as each of the not tasty candies can become the first not tasty candy. Overall, the expectation of the mood change is equal to .

Problem B (Marbles)

Without loss of generality we will assume N ≤ M.

Let us consider the case N = 1. Denote the number of marbles on the photo by k. Note that we can keep any k marbles. But we cannot get all possible relative positions, because we cannot change their relative order. We can choose any k positions and place marbles on them, though. So, there are different possible photos.

Let N ≥ 2. Then if there are k = N·M marbles, we can get only one such photo, because we didn't make any move (the first move necessarily removes one marble from the field). If k = N·M - 1, then after the first move we can only move to the free cell on the field — it is equivalent to the well-known brainteaser “15 puzzle”; in this case, exactly half of the permutations are reachable (see the link above). If k < N·M - 1, let us consider any two free cells, first get a configuration where they are adjacent. Then the “15 puzzle” is solvable for one of them (it depends on the sum of the number inversions in the permutation and the numbers of row and column of the free cell, and the sum of numbers of row and column differ by one for adjacent cells). Then, choosing the right free cell, we only have to solve the “15 puzzle”.

Thus, the overall number of photos is .

Problem C (Fan Placement)

The easiest way of solving this problem was to generate all possible permutations of the fans. Let us fix an order of fans, for example, from bottom to top, and let i-th fan have initial number p_i. Obviously, if for each fan the fan immediately before him does not block the view, then everybody sees the field comfortably. Let us consider all pairs of adjacent fans. If h_pi ≤ h_pi + 1, then this pair does not create any limitations on the placement: for any placement of the fan p_i + 1 fan p_i will not block his view because p_i is lower. If h_pi > h_pi + 1, there appear the following restrictions: fan p_i + 1 cannot take the next h_pi - h_pi + 1 rows after the fan p_i. So, these h_pi - h_pi + 1 rows should be removed from the consideration for this fixed order of the fans. After performing this operation for all adjacent pairs of fans, we should add the number of combinations of K out of the number of rows left, where K is the total number of fans. To make this operation fast, we precompute the table of values C_n^k for n and k not exceeding 1000.

Time complexity: O(n² + k!·k).

There is a harder way using dynamic programming where the state is triple “how many rows already considered, mask of seated fans, number of the last fan”. Transition in this case consists of iterating through the “pre-last seated fan”. For this solution to work fast we have to store a table of cumulative sums parallel to the dynamic programming table to avoid inner loop through the rows.

Problem D (Interesting Language)

Let us first describe the bruteforce solution. Find all pairs of words such that one of them is a prefix of another. Remove the shorter word from the longer one, leaving only the suffix. If we compute for each suffix how many ways are there to get it using this operation and denote the number of ways by cnt_suff, the answer for the problem is , where the sum is over all suffixes.

To compute for each suffix the number of such pairs let us use a trie. Let us build two tries based on the input array of words: the first one will contain all the input words, and the second one will contain all the reversed words. Go through the nodes of the trie with reversed words. Each time we enter a terminal node, go up from this node to the root while in parallel going down using the same symbols in the trie with the input words. If we enter a terminal node in the trie with input words during this process, we should increase by one the counter for the suffix where we are at the moment in the trie with reversed words. If we've left the trie with input words during the process, we can stop.

After such pass through the trie there will be the correct value cnt_suff in each node of the trie, and we just have to compute the answer using the formula above.

Time complexity: O(sumL), where sumL is the sum of lengths of all words.

Problem E (Taxes and Roads)

Let us see what paying the tax in some city gives us. After paying the tax in city A we can visit some other cities free of charge. Those are cities that are reachable from A and from which A is also reachable. If we get from the cities to graph theory, we can say that we can now visit free of charge all the vertices from the same strongly connected component of A. So, if we find the strongly connected components in the initial graph, we can pay the tax only when entering each component. As entering a strongly connected component “opens” for free of charge travel all the component and all taxes are non-negative, it will never be profitable to pay the tax in any other city of the same component.

Let us build a new graph based on the initial one. Its vertices will correspond to the strongly connected components of the initial graph. The weights of the edges will be set the following way: for each pair of strongly connected components that have an edge between them in the initial graph, create an edge in the new graph with the weight equal to the minimum of the taxes in all the cities which are the endpoints of the edges connecting this pair of components in the initial graph. Of course, we should account for the orientation of the edges.

After the new graph is built, we need to find the shortest path between the vertices that correspond to the strongly connected components which contain vertices 1 and n of the initial graph. It can be done either using the Dijkstra algorithm or by dynamic programming taking into account that the new graph is a directed acyclic graph. We also have to consider the start of the trip separately, as one can only pay the tax when he enters a city.

Problem F (Place for Capital)

If the angle between the radii is more than two radians, the minimum distance is the sum of radii. Otherwise, it is the difference of radii plus the length of the arc passing through the point with smaller radius. It follows from the fact that in the “curvilinear trapezoid” made out of two radial edges and two arcs the shortest path between the opposite nodes is the path through a radial edge and the arc of smaller radius.

We are left to compute everything accurately. Usage of the atan2() function allows to surpass most of the pitfalls. Without using atan2() there are problems with precision in case of two close points with big radii; in this case it helps to use asin instead of acos to avoid loss of precision.

Second online round and its analysis were prepared by rng_58, snuke, snarknews and Gassa.

In the second round of “Yandex.Algorithm”, 495 participants have made at least one attempt, 425 of them have solved at least one problem. There were 503 attempts for problem A with 73 successful, 11 attempts for problem B with 2 successful, 472 attempts for problem C with 76 successful, 846 attempts for problem D with 386 successful, 42 attempts for problem E with 16 successful and 624 attempts for problem F with 182 successful.

The results of internal testing made us hope that the number of participants who solve 5 problems will be higher than in the first round, and that the winner will solve all 6 problems. But it turned out too optimistic. By the middle of the round two leaders appeared: tourist and eatmore who submitted all the problems “blind”. There also was a whole group of pursuers each of which solved no more than two problems “blind”. The first one to solve 5 problems was cgy4ever from China who had problem C submitted “blind”. On the 75th minute three more participants solved 5 problems: maciej.klimek (maciejk) from Poland, Jedi_Knight (ivan.popelyshev) and burunduk3. On the 77th minute tourist submitted his 5th problem and took first place with 5 problems “blind”, and also eatmore; submits “blind” problem B which was not solved by anybody else by then. Still, tourist stays in the first place. One minute before the end of the contest natalia submits problem E which becomes 5th for her and with four problems “blind” out of 5 takes 3rd place.

After the system tests it turned out that only tourist stayed in the top-3 thanks to all 5 “blind” submissions accepted. However, he had already passed into the finals from the first round, so the 5th place became a way to the finals. For eatmore, problem E which he submitted next to last — failed; for natalia, problem F which she also submitted next to last — failed. On the other hand, the last submitted problems — B which was solved only by two people (other than eatmore it was s-quark from China) for eatmore and E, submitted at 1:39, for natalia — passed the system tests.

In the end vepifanov took 2nd place, yeputons took 3rd place. They both submitted only problem D “blind” on the 5th minute. All the following participants submitted all problems “open”. Jedi_Knight (ivan.popelyshev) took the 4th place, and peter50216 from Taiwan took the 5th place and also got to the finals.

Problem A (Degree Sequence)

First, if the sum of d_i is not 2(N - 1), it can't be a degree sequence of a tree, so output “None”. Otherwise, it's easy to prove that it can be a degree sequence of some tree.

Let c be the number of i such that d[i] ≥ 2. There are several cases:

1. c = 0. In this case d = {1, 1}. Clearly, the answer is “Unique”.
2. c = 1. The tree must look like a star. The answer is “Unique” again.
3. c = 2. There are two vertices with degree  ≥ 2. Let us call them s and t. There must be an edge that connects s and t, and all other edges connect one of {s, t} and a leaf. Therefore, the answer is “Unique” again.
4. c = 3. There are three vertices with degree  ≥ 2. Let us call them s, t and u. Consider three pairs of vertices {s, t}, {t, u} and {u, s}. Exactly two of them must be connected by an edge (if all of them are connected by an edge, the edges form a cycle; if one or less are connected by an edge, we can't make the graph connected), so there are three ways to connect them. If the degrees of s, t, u are all the same, all of those three trees are isomorphic, so return “Unique”. Otherwise return “Multiple”.
5. c ≥ 4. If the degree sequence looks like {1, 1, 2, ..., 2}, the tree must be a chain, so return “Unique”. Otherwise we have at least one vertex with degree  ≥ 3. We can construct two non-isomorphic trees using this vertex: one possible way is to construct a chain with vertices with degree >= 2 and add leaves to it, the other is to construct three chains with one common vertex. In this case return “Multiple”.

Problem B (Frogs)

Let f(t) be the position of Frog k at time t. We are asked to compute minimal t such that t - f(t) ≥ d. Note that t - f(t) is a non-decreasing function because for any t, f(t + 1) - f(t) is 0 or 1. Since t - f(t) is monotonous, we can use binary search. The main part of the solution is computing f(t).

For simplicity let us assume that k = 2 (otherwise we can repeat a similar algorithm k - 1 times). Let us call n good if the sum of beauty between cell 1 and cell n is a multiple of m. It has period m(p - 1), i.e. n is good if and only if is good. For each n ≤ m(p - 1), precalculate whether n is good. It turns out that f(t) is (the number of good numbers between 1 and t), so we can calculate it quickly with precalculated table.

Problem C (Green Triangle)

We want to compute the sum of signed areas pqr of all clockwise triplets (p, q, r). If we fix points p and q, the signed area of pqr is a linear function of coordinates of r, so we just want to know the sum of x-coordinates (or y-coordinates) of all points in the halfplane.

Fix a point p. Sort other points by the angle from point p in clockwise order (let us call them p₀, ..., p_n - 2). Then we should use a two-pointer algorithm: we should keep two indices i and j. Here, j is the biggest index that satisfies the condition “three points p, p_i, p_j are clockwise in this order”. We increment i from 0 to n - 2 and change j properly. If we increment i, j never decreases, so the total number of changes of i and j is O(n). Overall the algorithm works in O(n^2 log n).

There are some problems with precision in this problem under the given limits on the coordinates: double precision is not enough in case of triangles with small area and large perimeter. This is especially troublesome for Java where there is no long double type and using BigInteger leads to Time Limit Exceeded.

One of the variants to cope with precision problems is to store the sum of areas of triangles with the same base both in double and in a 64-bit integer. In this case double will store the highest 52 bits of the result and 64-bit integer will store the lowest 64 bits.

Problem D (MathWorlds)

This is the easiest problem. You should check all operators, and count the number of operators that satisfy the equation “x [operator] y = z”. You should carefully consider the case when y = 0: for example, for y = 0 don't check the division operator at all. Solutions that transform division into multiplication don't work for test 0 0 1 which became a problem for a lot of participants.

Problem E (Small Cycltes)

The properties in the statement are equivalent to the following:

1. G has a spanning tree. Fix one spanning tree T, and let us call edges contained in T “tree edges”, and call other edges “non-tree edges”.
2. If e = {u, v} is a non-tree edge, the distance between u and v in T is exactly two.
3. For each non-tree edge e = {u, v}, color the path between u and v in T. No edge is colored more than once.

The original problem can be reduced to the following problem: You are given a tree, and some edges are already colored. In each operation, you must choose a path of length 2 and color it (you can't color an edge if the edge is already colored). How many operations can you perform?

This task can be solved greedily. See the tree as a rooted tree, and find the deepest uncolored edge e. If e is not adjacent to other uncolored edges, you can't color this edge, so ignore it. If e is adjacent to one of its sibling edges (let's call it e₂), you should color e and e₂ at the same time (otherwise you can't color both). If e is adjacent only to its parent edge, you should color e and its parent at the same time. After either e is colored or is ignored, find the deepest uncolored edge once again and repeat the process.

Problem F (Swap Balls)

If the answer of (p, q, r, s) is “Yes”, then the answer of (p + 2, q, r, s) is also “Yes”. This is because if you perform the same operation twice in a row, nothing changes. It is intuitive that if p is quite big, the answers to (p, q, r, s) and (p + 2, q, r, s) are the same. In fact we can prove that if p ≥ 48, this is true. With these observations, you can assume that p, q, and r are small, so we can use dynamic programming to solve the task (dp[p][q][r][s]: is it possible to change s to “RGB” using the operations p, q, r times respectively?).

Here is the formal proof. Construct a graph with 48 vertices. Each vertex corresponds to a tuple: (the parity of p, the parity of q, the parity of r, s). A sequence of operations corresponds to a path in this graph. If this path is very long, the path contains cycles. If the cycle contains p', q', and r' times of each operation, these numbers are even, and we can delete this cycle and prove that the answer of (p - p', q - q', r - r', s) is “Yes”. We can repeat this process until p, q and r satisfy  ≤ 48.

It turns out that 48 can be replaced with 3 (if you experiment using a computer).

In the first online round of Yandex.Algorithm competition 609 participants submitted at least one solution and 396 submitted at least one correct solution. Problems Non-Squares and Kingdom Division were fairly easy, both resulted in approximately 300 correct submissions. Problem Stacks of Coins was moderately easy and was solved by 145 participants. The three other problems proved to be more difficult. Stickers could be a very challenging string problem, but small input size allowed for dynamic programming solution, which 22 contestants got right. Assistants was solved by 13 participants; it required binary search, greedy, and some basic data structures to get it under time limit.During the contest, nobody was able to solve State Roads, which was a neat graph-theoretical problem with a simple to code, but a quite tricky solution.

Congratulations to Kenny_HORROR who was the only one to solve five problems, and to Petr, tourist, and eatmore who solved four problems and with negative penalty times also advanced to the final round.

The problem set of this round was brought to you by the Polish team: Tomasz Idziaszek ( Kingdom Division ), Jakub Łącki ( State Roads ), Marcin Pilipczuk ( Assistants ), and Jakub Radoszewski ( Non-Squares, Stacks of Coins ). Special thanks goes to Professor Costas Iliopoulos for suggesting the idea of the problem Stickers.

Solutions, test data and analysis were prepared by marek.cygan, monsoon, and jakubr.

Problem A (Assistants)

In this problem we need to find the minimum number of days in which n research tasks can be completed. The i-th task can be executed by the professor using p_i consecutive days or can be delegated to an assistant who will execute it using a_i consecutive days. Every engaged assistant can execute only one task, and the professor needs one day to find such an assistant.

First we show how to check whether the project can be completed in k days. Then it is only matter of using binary search to obtain the answer.

It is easy to see that there exists an optimal schedule in which the professor first searches for assistants, and then he executes unassigned tasks. Moreover, it means that we do not have to worry whether the professor executes his tasks during consecutive days. Formally speaking, if there is an optimal schedule in which the professor assigns tasks to assistants and he executes the remaining tasks (but not necessarily in consecutive days), then there exists an optimal schedule in which the professor delegates the tasks from T during the first #T days, and later he executes the remaining tasks (each task in consecutive days). Therefore, if the professor delegates the tasks from T, then he will finish the remaining tasks before the deadline if and only if .

Now we show an algorithm which will check whether such T exists. We consider days d = k, k - 1, ..., 1, and during some days we will be delegating tasks to assistants. Assume that we are in day d and we already delegated tasks during days after d. Let be the set of tasks which can be assigned in day d such that an assistant will complete them before the deadline. The main observation is as follows: if is not empty, then we can in day d greedily assign task which maximizes the value of p_i.

Now we prove it. Suppose that there exists a schedule S, which in the days after d is the same as our plan. If the schedule S assigns task i in day d, then we are done. Otherwise in the schedule S in day d the professor assigns task j ≠ i or executes task j himself (in this case possibly j = i).

In the first case, the professor assigns task j ≠ i. Then (since assistant will finish before the deadline) and (we assume that S is the same as our plan in the following days). From our greedy choice we have that p_i ≥ p_j. If in S the professor assigns task i in day d', then d' ≤ d (since , and S is the same as our plan in the following days) and we can swap in S the days in which we assign tasks i and j. Otherwise, if in S the professor executes task i himself, then we can alter S as follows: we delegate task i in day d, and execute task j during these days in which the professor have executed task i (we can do that since p_i ≥ p_j).

In the second case, the professor executes task j in day d. If j = i, then we can also delegate this task in day d (since ). Otherwise, if j ≠ i, we can delegate task i in day d, and reclaim the missing day to execute task j in the moment in which the professor was working on task i (delegating or executing it) in the schedule S.

In all the cases we get a correct optimal schedule in which the professor delegates task i in day d, therefore the key observation is proved.

How fast can we implement the above algorithm? Choosing maximum from the set can be implemented using a binary heap ordered by p_i. When moving from day d + 1 to day d we add the elements from to the heap (i.e. tasks with a_i = k - d; we need to sort the tasks by a_i to do this), and we remove the maximal element (and we add it to T).

Observe, that we do not have to iterate over all days, but we can start from the day d = min(k, n), since there is no need to assign tasks after the n-th day. Thus the whole solution (with the fixed k) works in time .

We can improve it by iterating not over the days, but over the tasks sorted non-increasingly by p_i. Every time we try to assign task i in the latest day from {1, 2, ..., d_i} where d_i = min(k - a_i, n) in which no task is yet assigned. It is not hard to see that the set T we get will be the same as in the previous algorithm. This assignment can be performed in almost-linear time, using the structure for disjoint sets. Each set contains the free day d and all the days after it in which some task are assigned. Now assigning the task boils down to finding the set which contains d_i, obtaining the minimal element d' in this set, assigning task i during day d', and joining the set with the set containing element d' - 1.

We can now estimate the final time complexity. Since assigning all the tasks to assistants is a valid solution, thus the answer will always be smaller than n + A, where . Adding binary search, we get the solution which works in time .

Problem B (Kingdom Division)

In this problem we are to divide an n × m grid into the maximum number of parts of distinct sizes formed by connected sets of unit squares. We need to present an example of such a division using characters from to denote the resulting parts. A solution to this problem can be obtained in three natural steps.

In the first step we forget for a moment about the requirement of connectivity and ask what sizes of parts would imply the maximum result. The answer is simple, the sizes should be equal to 1, 2, 3, ... If the last part is smaller than required, we join it with the next-to-last part.

In the second step we note that the division proposed in the previous step is actually possible to obtain. We can cover the whole grid with a snake-like pattern and then cut the snake at appropriate positions to form the respective parts which will certainly be connected sets, see the figure to the left.

The third step is to label parts with the letters from so that no two adjacent parts receive the same label. A tempting idea would be to label them in the order they appear in the snake. However, such a labeling does not work in some cases.

One possible correct solution is to label each part with the smallest letter that does not occur among its neighbours (and perform the labeling in the snake-order). Another idea is to label the parts in the first row using the letters A and B, in the second row use the letters C and D, in the third row use the letters E and F, in the fourth row again A and B and so on (see the figure to the right). Starting from the point when each part covers at least one row, we can stick to just two letters, A and B. In the latter labeling we use only 6 distinct letters.

An interesting question is to find what is the minimum number of letters sufficient to solve every test case.

Of course the above algorithm can be easily implemented in O(nm) time.

Problem C (Non-Squares)

In this problem we need to check if a given positive integer n can be represented as a product of k positive integers all of which are not integer squares. Let us call such a representation a non-square representation.

A generic approach could be dynamic programming over the set of divisors of n. All divisors of n can be found in time. Let D(n) be the number of divisors of n. It turns out that for n ≤ 10⁹ we have D(n) ≤ 1344.

We compute a 2-dimensional Boolean array , where is true if and only if the divisor d can be represented as a product of j non-squares. The computation uses the following Boolean formula that works for j ≥ 1 and :

The time complexity of this solution is due to a map-like data structure required to keep track of the divisors of n. The memory complexity is O(D(n)k).

One could also improve the running time of this solution by noting that the parameter k is actually bounded by , which in our case is 29. Indeed, for the answer is always “NO” (an argument for this can be inferred from the next solution).

There is also a far simpler solution that examines the decomposition of n into prime factors. Let n = p₁^α₁p₂^α₂... p_m^α_m where p_i are distinct prime numbers. Then the solution is the following:

1. If α₁ + α₂ + ... + α_m < k then output “NO”.
2. Otherwise, if m > 1 then output “YES”.
3. Otherwise we have m = 1. If k - α₁ is even, then output “YES”, otherwise output “NO”.

Let us provide some justification for this solution. Point (1) follows from the fact that any non-square divisor must have a prime factor. For m = 1, we simply need to check if α₁ can be represented as a sum of k odd integers, which is possible if and only if the parity of k and α₁ are the same. This yields point (3) of the algorithm.

Finally, consider point (2). We need to show that if α₁ + α₂ + ... + α_m ≥ k and m > 1 then there exists a non-square representation of n. Let us take as the first k - 1 non-square divisors the prime divisors of n: first α₁ times the divisor p₁, then α₂ times the divisor p₂ and so on. As the last divisor, d, we take the product of all the remaining prime factors. If d is not an integer square, we have the requested representation. Otherwise we change the last divisor to d / p_m and the first divisor to p₁ p_m, thus obtaining the representation.

This solution only requires to find the prime decomposition of n and works in time.

Problem D (Stacks of Coins)

In this problem m gold and silver coins are arranged into n stacks of different heights. We are to rearrange the coins so that there is a maximum number of unicolor stacks (a unicolor stack has only gold or only silver coins). We are allowed to perform any number of operations of swapping two coins that are located at the same height of different stacks.

Let k denote the result, that is, the maximum number of unicolor stacks that can be formed. Let us do a binary search for k. From now on we are left with a decision problem: given k, check if it is valid. Clearly it is optimal to try to make k smallest of the stacks unicolor.

Since the number of operations is not bounded, our problem can be reformulated as follows. Let h be the height of the k-th smallest stack. For each height level 1, ..., h we know the total number of gold and silver coins at this level. We need to check if these numbers are sufficient to create k unicolor stacks. This task will reduce to computing an intersection of O(h) intervals.

First we consider each height level separately. Assume there are g_i gold and s_i silver coins available at this level and the k smallest stacks contain in total t_i coins at this level. Using these numbers, we can compute an interval [a_i, b_i] such that if and only if one can take x gold coins and t_i - x silver coins to form the i-th level of the selected stacks. Note that such an interval implies the interval [t_i - b_i, t_i - a_i] for the number of silver coins.

Finally we need to make sure that the intervals for different levels allow to find a valid solution. We iterate from the bottommost to the topmost level. For a given level i, we need to intersect the interval [a_i, b_i] with [a_i - 1, b_i - 1] and similarly the intervals for the silver coins. Thus we obtain a single updated interval [a_i, b_i] which we then use to update the intervals for higher levels.

The whole solution works in time.

This problem has also a linear-time solution. Let g_i be the total number of gold coins which are located on the i-th level above the ground. Let g'_i be the maximum number of stacks which can be formed such that they have all gold coins on the i-th level and below. It can be easily computed using the following recurrence:

Similarly, we define s_i and s'_i for silver coins.

Let h_i be the height of the i-th stack, and suppose that stacks are sorted non-increasingly by heights, i.e. h₁ ≥ h₂ ≥ ... ≥ h_n. We iterate over stacks and “color” them (making them unicolor) when possible. Suppose we consider stack i and we already colored stacks numbered 1, 2, ..., i - 1 in such a way that we got G gold stacks and S silver stacks.

The i-th stack can be colored gold if and only if g'_hi > G. In such case we show that there is an optimal solution in which this stack is colored gold and stacks 1, 2, ..., i - 1 are colored the same as in our solution. Consider any optimal solution in which stacks 1, 2, ..., i - 1 are colored the same as in our solution. Let j ≥ i be the highest gold stack in this optimal solution (it must exist, otherwise we can add stack i and get a better solution). Now we can swap all the coins from the stack j to the stack i and, since g'_hj + 1 ≥ g'_hi > G, we also have sufficiently many gold coins to swap into the stack i above level h_j.

Similarly, if we cannot color the i-th stack gold, but we can color it silver (i.e. s'_hi > S), there is an optimal solution in which we can do this.

Otherwise we have g'_hi + s'_hi ≤ G + S, which means that we cannot color more than G + S stacks of heights not less that h_i.

Since we can sort the heights of the stacks using counting sort, the above algorithm runs in O(n + m) time.

Problem E (State Roads)

In this problem we are given a graph in a dynamic setting. The set of nodes V is fixed, but the edges of the graph are added and deleted over time. We are to answer queries of the following type: given a set of nodes and a moment of time, check whether these nodes form one or more whole connected components of the graph in this moment of time.

We present a randomized solution to this task, which is very simple to code, but also quite tricky. For each edge that is added to the graph we pick at random an integer weight. For each node we store in the -product of weights of all edges that are adjacent to this node. Note that such values can be updated in O(1) time upon insertion and deletion of edges.

Now the crucial observation is that {u₁, u₂, ..., u_k} forms a number of whole connected components if and only if each edge in the graph is adjacent to exactly zero or two of the nodes u_i. Hence, to answer a query, we compute:

where denotes the -operation. If the above value is non-zero, we know that the answer is “NO”. Otherwise with high probability the answer is “YES”. The probability of an incorrect positive answer is where M is the maximum weight of an edge. This probability turns out sufficiently small for M = 2³² or M = 2⁶⁴.

The whole solution works in linear time with respect to the size of the input.

Problem F (Stickers)

In this problem we are given n kinds of stickers s₁, ..., s_n, where each s_i is a word of length d. We are asked what is the minimum number of stickers needed to paste a given word t of length m.

We present a simple dynamic programming solution to this problem. Denote by dp[i] the minimum number of stickers needed to paste exactly the suffix t[i..m] and by the same number, but when we allow stickers to overflow and cover positions from t[i - d..i - 1] (but not necessarily with correct letters). The answer to the problem is dp[1].

Let us see how to compute dp[i]. The i-th position of t must be at some point covered by a sticker pasted in this position. Since all the stickers have the same length, we can restrict ourselves to pasting this sticker as the last one or as the first one. This gives us two cases:

1. For some j we have s_j = t[i..i + d - 1]. Thus we can paste the suffix t[i + d..m] possibly covering letters from t[i..i + d - 1] and after that paste s_j at position i. In this case we use stickers.
2. We have s_j[1..d'] = t[i..i + d' - 1] for some j and some d' ≤ d. Thus we can paste s_j at position i and then paste t[i + d'..m] with restriction that we cannot modify the letters before position i + d'. In this case we use 1 + dp[i + d'] stickers.

If for every position i we know the maximum l[i] such that t[i..i + l[i] - 1] is a prefix of some sticker, then the case (1) is possible if d = l[i], and the outcome from the case (2) is equal to min_{1 ≤ j ≤ l[i]}(1 + dp[i + j]).

We compute similarly, but now instead of the set of all stickers we consider the set of all the suffixes of stickers. Thus we compute l[i] as the maximum number such that t[i..i + l[i] - 1] is an infix of some sticker.

The above solution can be implemented in the time complexity of O(mnd²). Surprisingly, this problem can be solved in linear time with respect to the size of the input, even with stickers of different lengths, but such solution is a lot more complicated.

Hi!

The next stage will consist of three elimination rounds that will be held on:

Online round 1 — 14 Jul 2013, 21:00 MSK; Materials; Analysis

Online round 2 — 18 Jul 2013, 13:00 MSK; Materials

Online round 3 — 22 Jul 2013, 05:00 MSK; Materials

Each contest round lasts 100 minutes. Links to the rounds are avaliable on the round names above.

The scoring model for this stage will be Grand Prix 30.

To advance to the final round in St. Petersburg, Russia, you don't have to participate in all online rounds. You will need to place within one of these groups:

*top 4 in one of three rounds among contestants who have not yet advanced to the final round;

*top 9 in the cumulative results of two out of three rounds among contestants who have not yet advanced to the final round; or

*top 4 in the cumulative results of three rounds among contestants who have not yet advanced to the final round,

All finalists, another 75 best participants of elimination stage and another 75 random participants of the elimination stage, who will solve at least one problem will get a T-shirt!

You can always read the full schedule and regulations on the official website.

Good luck! Next stop: Saint Petersburg!

UPD: Results of the online round 1 are now official and we congratulate Kenny_HORROR for impressive victory using "all open" strategy.

First finalists are: Kenny_HORROR, Petr, tourist, eatmore.

UPD2: Congratulations to tourist for the online round 2 victory. We are glad to invite vepifanov, yeputons, ivan.popelyshev, peter50216 to the final round!

UPD3: Based on their scores in round 3, winger, KADR, ainu7, s-quark are invited to the final round. Congratulations!

Rightful place among finalists goes to

based on two out of three elimination stage rounds : burunduk3, misof, niyaznigmatul, cerealguy, Mimino, liympanda, romanandreev, watashi, RAVEman;

for the overall performance in the stage: Nerevar, ilyakor, dreamoon_love_AA, pparys.

Dear finalists! Congratulations and see you soon in St. Petersburg. I will contact you shortly on the matter of your final round participation. Please, do not ignore my emails and answer promptly =)

UPD4 Materials of the second test round are published: Test round 2; Materials

Qualification Round and its analysis were prepared by Chmel_Tolstiy, aropan, Romka, SobolS, Ra16bit, snarknews and Gassa.

1732 participants have started in the Qualification Round of Yandex.Algorithm, 1606 of them have made at least one attempt, 1558 have solved at least one problem. Interestingly, the number of registered participants was 3397 which is almost twice as much as the number of participants who have started the round. We don't know why is that.

As the qualification round was a virtual contest, participants could choose the most convenient time to compete. The maximum number of participants online (around 280) was at the start, the minimum number — between 3 a.m. and 4 a.m. Moscow time (around 20 participants). First one chronologically who solved all 6 problems was Scott.Ai from China; all problems were submitted "open". Soon i.metelsky (Ivan Metelsky, Belarus) who started around 10 p.m. MSK solved problems A-D "blind", E "open" on the second attempt, F "open" on the first attempt and took the 1st place with a very strong result. However, vepifanov (Vladislav Epifanov, Russia) who started 4 hours later solved A, B, C, F "blind" and D, E "open" on the first attempt, and he took the 1st place thanks to smaller penalty time. On Tuesday morning, first place was taken by world champions from ITMO: first eatmore (Evgeny Kapun, ACM ICPC world champion 2009 and 2012) who started at 11 a.m. solves all 6 problems "blind"... but he was the leader only for several hours: with the same strategy but better penalty time, current world champion tourist (Gennady Korotkevich, Belarus) bypasses him. 24 hours after the start of the Qualification Round the top-3 is Korotkevich — Kapun — Epifanov. In the Test Round, Gennady Korotkevich was second, Vladislav Epifanov was third. The Test Round winner — Антон Лунёв (Anton Lunyov, Ukraine) — started close to the end of the Qualification Round. He solved A, B, F, D "blind", then solved E "open" on the second attempt, then solved C "blind" and took the final 3rd place from vepifanov who moved to the 4th place. Thus all three winners of the Test Round got into top-4, but in a different order. Evgeny Kapun has also advanced to the online rounds from the Test Round, so the best participant who had not advanced before was Ivan Metelsky who finished 5th. Overall 34 participants solved all 6 problems, and the best result of a participant who solved all problems "open" was 9-10 place.

We also noticed that some participants had unexpected problems because of the fact that stdin and stdout were specified as input and output files in the problem statements. Some participants interpreted them as the filenames. Jury decided to rejudge such solutions specifying corresponding filenames; in the future system will use phrases "Standard input" and "Standard output" instead.

Problem A (Ancient Basketball)

In this problem one just had to implement what was described in the problem statement. It is sufficient to create two variables to count points of each team, and after reading records about throws, increase the corresponding variable by the specified number of points. To choose which variable to increase, operator if should be used.

Problem B (Prime Problem)

Let us move 1 to the left-hand side — we get k² - 1 = p₁·p₂ or after factorization (k - 1)(k + 1) = p₁·p₂. As k > 2, both multipliers in the left-hand side are not equal to 1, thus (k - 1) = p₁ и (k + 1) = p₂ (without loss of generality we can assume p₂ > p₁). Indeed, left-hand side must be divisible by p₁ and p₂, so if k - 1 = a·p₁ and k + 1 = b·p₂, then (k - 1)(k + 1) = ab·p₁·p₂ = p₁·p₂, and as a and b are positive integers, a = b = 1. If k - 1 was divisible by p₂, it would turn out that k - 1 = p₂, k + 1 = p₁, but it is a contradiction with p₂ > p₁.

So, the problem is now reduced to searching for such k that both k - 1 and k + 1 are prime (so-called "twin primes"; interestingly, it is not yet known whether the set of such primes is finite or infinite).

Under the given constraints this search can be implemented in any way, even searching through all (not only even) k and while checking primality searching through all possible divisors up to the number itself. Given that n ≥ 4, "empty" answer is impossible as k = 4 satisfies the equation.

Another way is to factorize k² - 1 and check that the factorization is just a product of two primes.

Problem C (Board Game)

Answer for the first question is very easy to compute. It is the total number of atoms in all the groups. It is equal to .

To answer the second question, let us first reformulate it. It is known from game theory that position in such game is losing if of numbers of atoms in all groups is equal to 0. So, we have to find the number of first moves such that after each of them of all group sizes will be 0. Let us denote . There is a fast method to compute x. To do it we can use the fact that for any non-negative integer k . Thus .

If we fix group number i to make the first move in it, then the number of atoms that must be left in it after the move is determined unambiguously. It is equal to of all other group sizes which is . So, if we are able to make the first move from group i it must be true that . It is only possible if at position p where x has the highest set bit number i also has set bit. We have to compute the number of such i up to N. Among the numbers less than exactly half are such i. If N has set bit at position p, should be added to the answer.

Problem D (Infinite Sum)

Let us make several transformations of the expression:

If we denote , we get

Now we only have to compute the recurrence and output the answer.

Problem E (Homework)

Cases with X = 0 or K = 0 are trivial and can be solved separately. It is advantageous if Gennady solves the maximum number of problems he can each day and the other students can be distributed on the topics, and they can adapt to Gennady's work. If there still exists a topic with at least X problems to solve, Gennady works at maximum this day and solves X problems. If there is no such topic, he takes the topic with maximum number of problems to solve and solves all of them. Thus, it is easy to compute how many problems will be left after Gennady if he works for k days. Then we can use binary search on the number of days and check whether other students will be able to solve all the problems left after Gennady in time.

Time complexity of such solution is . We should also note that one has to initially sort topics by value of to search for topics with the maximum number of problems to solve when Gennady can't solve X problems. Using the fact that and properties of we get complexity .

An alternative solution is to consider the optimal strategy of other students. When we know the optimal strategy for Gennady, we can determine how the other students should work: first they have to solve problem in the topic with the minimum value of and solve this topic until becomes equal to 0. When such topics are all gone and there are still problems to solve, they can choose any topic and solve problems in it until all problems in the topic are solved. So, we have to find out what happens first: Gennady has no more topics with A_i ≥ X, or students have no more topics with .

Time complexity: .

Problem F (Atoms: There and Back Again)

Number of groups doubles after each division. Thus if N is not a power of 2, the given state cannot be reached, and the answer is "NO".

Consider the last division, that is, the division of state right before the current state. Group of size X was created from each group. So, at least half of the groups are of size X. Then we can discard those groups and get the same problem with N / 2 groups. If at any step there is no such size that at least half of the groups have this size, the answer is "NO".

To solve the problem we can cluster the groups by size. Then simulate the process described above using heap (priority queue). We can also greedily separate each cluster of same-size groups into parts of sizes that are powers of 2, so that each power appears exactly once, except for the 0-th power (there must be two parts with 0-th power).

Time complexity is .

Hi!

Qualification round of the Yandex.Algorithm competition that will start on July 8, 2013, at 7 p.m. This round is virtual, so you need to start your qualification within 24 hours from the beginning of the qualification round. Qualification will last 100 minutes even if you will start at 6:59 p.m. Please, do not discuss the problems until 8:40 p.m. July 9 — someone can be still solving the problems.

The 2,000 best contestants who have solved at least one problem will advance to the elimination stage. Already advanced from test round participants will have a chance to work with the TCM/Time.

Good luck! Almost 200 t-shirts and more than half a million rubles are waiting for you!

Registration

Link to the contest

UPD: Archive is at the competition site.

Test Round and its analysis were prepared by snarknews and Gassa. Problems of the Test Round have already been used before in different competitions. The following rounds will consist of new original problems, and you can still register and compete in the Qualification Round.

During the round a lot of participants tried to make "blind" submits, from time to time even going to the top places, but as the system tests showed with only one problem solved in fact.

By the end of the round tourist was at the first place with all problems but B submitted "blind". vepifanov was at the second place with A, C and D submitted "blind", but B and F — submitted "open" (both with a wrong attempt), Anton_Lunyov was at the third place with only C submitted "blind". All other participants had less than 5 problems solved. After the system tests it turned out that tourist had a wrong solution for A, and vepifanov had a wrong solution for D. So, the only participant who solved 5 problems was Anton_Lunyov. tourist got second place, vepifanov was third.

It is a bit strange that problems B and E, although their solutions don't require special knowledge, remained mostly "unclaimed": all participants who solved these problems were in the top-3 with tourist solving E, Anton_Lunyov and vepifanov solving B.

It also turned out that file input and output can be an obstacle for the participants: 90% of questions were concerned with this. So we decided not to use file input and output in the future rounds of Yandex.Algorithm.

Problem A (Circles)

This problem is an advanced variant of a problem that was used in the 0th (pilot) season of OpenCup which happened in May of 2004. It can also be considered an easier version of a problem used in the Moscow Grand Prix of OpenCup in 2005.

Using the formula for area of triangle S = abc / 4R, we obtain R = abc / 4S, where a, b and c are lengths of the triangle's sides. Taking into account that the vertices of triangle have integer coordinates, we conclude that squares of lengths of the sides and doubled triangle area are integers. So, R² can be computed exactly as an integer fraction .

As the coordinates do not exceed 1400, numerator doesn't exceed , so it fits into unsigned int64. To compare such fractions one has to either use long arithmetics or use modular arithmetics or compute GCD or store high-order number part separately...

We point out that type double is insufficient even without considering the errors of computation: there exists an example of two triangles with circumscribed circle radiuses differing by less than 2^- 52. For example, triangles with vertices (0, 0), (1312, 164), (134, 1372) and (0, 0), (1351, 169), (106, 1317).

The example above was foundf using the following approach: fix one of the vertices at (0, 0) and the other two at (1400, 0) and (0, 1400). Bruteforce the coordinates of the last two points in some neighborhood, compute the circumference radiuses, sort them and find the minimal difference between two adjacent values.

As we expected, there were a lot of failed submissions for this problem which tried to solve problem using doubles and "search for espilon". Most participants who thought of exact solution right away didn't have problems with implementation.

Problem B (Three Fractions)

This problem was first used in the Moscow Grand Prix of OpenCup in 2005. That version was simpler: it didn't have multitest.

The easiest is to solve this problem using precalc.

Under the given restrictions on n and on the queries number it is reasonable to precalculate the full table of answers. If n is composite number and the problem is solved for all prime numbers less than n, then represent n as product n = a·p where p is prime. Then . So it is sufficient to precalculate answers for all prime n and for n = 4 and then compute the answers for composite n.

Let's make a very rough estimate on c and b. As , then . As a > b > c, then , so and . Using the same logic and . So, let us bruteforce through all prime n, all b and c in the ranges we found above and check whether 4bc - nb - nc divides nbc. If it does, the answer can be found as .

Such precalc takes less than a minute even using a very slow CoreDuo 1.6Ghz. One can just store b and c in the code. That was code size won't exceed 50k, which is less than source limit.

Another way is to bruteforce c and try to represent difference as a sum of two "egyptian" fractions using Fibonacci's algorithm. This solution passes the Time Limit without precalc.

This problem is a particular case of famous mathematical problem — Erdos-Straus conjecture. It is not solved in the general case, but there are solutions for all n ≤ 10¹⁴.

For those who appreciate constructive solutions — some formulas.

• If n = 3k + 2, we get ,
• If n = 4k, we get ,
• If n = 4k + 2 and k > 1, then ,
• If n = 4k + 3, we get ,
• If n = 8k + 5, we get .

So, there is no explicit formula only for n = 24k + 1.

Problem C (Select The Digits)

This problem was first used at a school informatics circle in Saint-Petersburg Anichkov Palace in 2006.

This problem is rather simple and allows for many different ways of solving. Let us name a few. Below, we assume that s is the given string and res is the result we seek.

Solution 1

We can simply look over all quadruples of positions we select. Here is a sample of code in Pascal:

res := 9999;
for i := 1 to 5 do
  for j := i + 1 to 6 do
    for k := j + 1 to 7 do
      for l := k + 1 to 8 do
        res := Min (res, StrToInt (s[i] + s[j] + s[k] + s[l]));

Solution 2

In a high-level programming language, there could be tools which do all the dirty job related to searching by themselves. Here is a solution in Python looking over all combinations of four elements:

res = "".join (min (itertools.combinations (s, 4)))

Solution 3

The search could be organized recursively. Here is a function in Java taking two parameters: position p in the string s and number of positions q we have yet to take. The function is called from the main program like recur (8 - 1, 4) and looks over the positions from back to front.

int recur (int p, int q) {
  if (q < 0 || p + 1 < q) return 9999;
  if (p < 0) return 0;
  return Math.min (recur (p - 1, q),
    recur (p - 1, q - 1) * 10 + s.charAt (p) - '0');
}

Solution 4

The problem can be solved by dynamic programming. The two parameters are number of visited positions i and number of selected positions j. The value of target function f(i, j) is the minimal number which can be obtained. There are two transitions from each state: first, we either select or drop the current position, and then we move to the next position in string s. Below is a program in C/C++ demonstrating the approach. The answer is contained in cell f[8][4].

memset (f, 0x3F, sizeof (f));
f[0][0] = 0;
for (i = 0; i < 8; i++) {
  for (j = 0; j <= 4; j++) {
    f[i + 1][j] = min (f[i + 1][j], f[i][j]);
    f[i + 1][j + 1] = min (f[i + 1][j + 1],
      f[i][j] * 10 + (s[i] - '0'));
  }
}

Problem D (Product of Different)

This problem was first used at a school informatics circle in Saint-Petersburg Anichkov Palace in 2009.

Let us start by presenting a test which had the number 15: n = 112 500 = 2²·3²·5⁵. Its complexity lies in the fact that we can not choose divisor 2·3 = 6: in that case, the total number of divisors will be no more than six. Instead, we should choose the following factorization into seven factors: 112 500 = 1·2·3·5·10·15·25.

This is the minimal test which breaks some simple yet wrong solutions. One of them is to greedily choose the divisors, starting with the smallest possible, as long as after we add the next divisor d, the remaining number is strictly greater than d. On this test, it finds divisors 1·2·3·5·6, and then tries to factor 625 = 5⁴, but neither 5 nor 25 = 5² could be taken.

The author's solution is an exhaustive search. A trivial recursive brute-force search which considers divisors up to in increasing order manages to pass in under a second. The following function in C/C++ must be run as recur (n, 1, 0). It writes the number of different divisors into res and the divisors themselves into the array best. The parameters have the following meaning: n is the number remaining to be factorized, k is the lowest possible value of the next divisor, and cur is the number of divisors already selected.

void recur (int n, int k, int cur) {
  if (res < cur + 1) {
    res = cur + 1;
    now[cur] = n;
    memmove (best, now, sizeof (best));
  }
  for (int d = k; d * (d + 1) <= n; d++)
    if (n % d == 0) {
      now[cur] = d;
      recur (n / d, d + 1, cur + 1);
    }
}

How does one estimate how fast is such a program? We can note that the answer is rather small: as the product of the first 13 positive integers is greater than 10⁹, the answer is not greater than 12. This means that the first if will be triggered no more than 12 times. Another useful fact is that the numbers up to 10⁹ have no more than 1344 different divisors each (http://oeis.org/A066150).

The easiest way is to write a program to give a crude upper bound on the number of divisions and or remainder calculations (example in C/C++). Here, n is the number remaining to be factorized, and k is the lowest possible value of the next divisor.

int count (int n, int k) {
  int res = 0;
  for (int d = k; d * (d + 1) <= n; d++)
    res += 1 + count (n / d, d + 1);
  return res;
}

This program differs from the actual solution: here, we step into recursion on every iteration of the cycle by d, and in the actual solution, we call recur only when n is evenly divisible by d. On the other hand, it allows us to use the maximal possible value of n to get an estimate (albeit crude) of the worst case, instead of searching for some large number with many divisors which make the real program run as slow as possible.

If we call count (1000000000, 1) the result will be 151 631 365. If we account for the fact that division by unity can be treated separately and start our search from divisor 2, the upper bound will be the result of calling count (1000000000, 2), it is 75 815 682 (half of the above). In fact, we know that the square root of about 10⁹ is about 30 000, and the number of divisors less than the square root is no more than 1344 / 2 = 672, it is obvious that the actual number of divisions will be a few times less. The maximal number of divisions and/or remainder calculations in all jury tests turned out to be 15 395 811.

There are faster ways to do an exhaustive search as well. For example, instead of looking over all numbers up to the square root of n, we can just look over all divisors of n which can be found in advance in time. Also we can first decompose n into prime factors and then search for divisors as tuples of powers for each of these prime factors.

Problem E (Table of Championship)

This problem is an version of problem from the Moscow Grand Prix of OpenCup 2005 adapted for memory limit=64 MiB. In the initial version memory limit was 3Mb and lengths of team names didn't exceed 15 symbols.

There are two cases: when all three lost numbers are in the same line and when at least one of them concerns a different team (or less than 3 numbers were lost).

Let's denote the number of matches played by i-th team by P_i, number of wins by W_i, number of draws by D_i, number of losses by L_i and number of points by S_i.

Then the following equations hold: W_i + D_i + L_i = P_i and 3W_i + D_i = S_i. If not all 3 numbers lost concern the same team, we have to solve several systems of linear equations with not more than 2 variables.

In the case when all 3 lost numbers concern the same team, we get one more equation from the fact that the total number of wins of all teams equals the total number of losses of all teams. W_i + W_- i = L_i + L_- i where W_- i is the total number of wins of all teams but i-th and L_- i is the total number of losses of all teams but i-th.

So the unique restoration of numbers is always possible.

The main difficulty in this problem is that the whole table doesn't fit into memory.

So one has to read input file twice: first to build the system of equations (while reading, we sum W_i and L_i to build the system of equations in the second case), second to find the line which holds the answer.

Problem F (Taxis)

This problem was first set by polish authors and was first used at the first stage of All-Poland school olympiad 2012-2013.

Obviously, either one can go the path from the taxi base to the destination without switching taxis or it is impossible to get to the destination (as the taxi that will arrive at destination has to go through the whole segment from the taxi base to the destination). So let's "reserve" a taxi with the minimum fuel sufficient to go from the taxi base to the destination. Also let's construct the farthest point from the destination from which this car can get a passenger and drive him to the destination. If the taxi base is at the destination, no "reservation" is made.

Then let's sort cars which are not "reserved" by descending amount of fuel and each time choose the car with the maximum fuel. We will now prove that this algorithm gives a solution which is not worse than any other possible solution. Suppose we first use a taxi with fuel X₁ and then a taxi with fuel X₂, and the passenger starts at distance a before the taxi base. Then the passenger will go (X₁ - a) + (X₂ - (2a - X₁)) = 2X₁ + X₂ - 3a kilometers. If X₂ > X₁, then if we change X₂ and X₁ we'll see that the distance travelled increased. If the car with the largest fuel left can't go already (or there are no cars left that are not "reserved" before the passenger gets past Z), then it is impossible to get to the destination.

If passenger is at point Z or closer to the destination at some point, he can already arrive at the destination using the "reserved" car. We also have to check if passenger can get to the destination right away, without using the "reserved" car.

June 27 is an important date – that’s when the test round of Yandex.Algorithm kicks off. Don’t miss your chance to register, so you can be in the running for a place in the final round, which takes place on August 21-23, 2013 in St. Petersburg. The final round venue is truly unusual for such an IT event – the palace of Grand Duke Vladimir, built in 1870, will welcome finalists with all its historical charm.

In the final round, the best participants will be left one-on-one with the testing system – no internet connection or prewritten code, only properly set-up computers and IDEs. We will provide text coverage of the round.

If you want to be part of the action, don’t leave your registration to the last minute – remember, the test round starts tomorrow.

More good news: we decided to almost double the number of T-shirts. The best 75 non-finalists among participants of the elimination stage, another 75 random participants of the elimination stage who successfully submit a correct solution to at least one problem and, of course, all finalists will receive an exclusive Yandex.Algorithm T-shirt.

UPD: The test round is available for participants now: http://algorithm.contest.yandex.com/contest/306.

Current standings are open for everyone: http://algorithm.contest.yandex.com/contest/306/standings.

UPD2: Official results are avaliable on the official website

UPD3: Round archive is avaliable at the official website