Cheers everyone.

Today, on June 13 at 10:00 MSK the third and final qualification round of Yandex.Algorithm 2016 tournament will take place. I am the author of all tasks in this round. I wish to thank Ivan Gassa Kazmenko, Oleg snarknews Khristenko, and espically Aleksey Chmel_Tolstiy Tolstikov and Maxim Zlobober Akhmedov for their immense contribution to problems preparation. I also thank Yandex employees who were involved in testing this round.

Best of luck!

UPD: the round is complete! Congratulations to Um_nik, who was the only one to solve all problems!

You can find the elimination standings here. Congratulations to 25 best participants!

Editorial here

I'm terribly sorry for the delay.

Please report any mistakes.

614A - Link/Cut Tree

Author: Tigutor

Developers: Tigutor, ch_egor

You had to print all numbers of form k^x for non-negative integers x that lie with the range [l;r]. A simple cycle works: start with 1 = k⁰, go over all powers that do not exceed r and print those which are at least l. One should be careful with 64-bit integer overflows: consider the test l = 1, r = 10¹⁸, k = 10⁹, the powers will be 1, 10⁹, 10¹⁸, and the next power is 10²⁷, which does not fit in a standard integer type.

614B - Программа Гены

Author, developer: ch_egor

You were asked to print the product of n large numbers, but it was guaranteed that at least n - 1 are beautiful. It's not hard to see that beautiful numbers are 0 and all powers of 10 (that is, 1 followed by arbitrary number of zeros). If there is at least one zero among the given numbers, the product is 0. Otherwise, consider the only non-beautiful number x (if all numbers are beautiful, consider x = 1). Multiplying x by 10^t appends t zeros to its decimal representation, so in this case we have to find the only non-beautiful number and print it with several additional zeros.

We tried to cut off all naive solutions that use built-in long numbers multiplication in Python or Java. However, with some additional tricks (e.g., ``divide-and-conquer'') this could pass all tests.

613A - Петя и снегоуборочная машина

Author, developer: platypus179

Consider distances between the point P and all points of the polygon. Let R be the largest among all distances, and r be the smallest among all distances. The swept area is then a ring between circles of radii R and r, and the answer is equal to π (R² - r²).

Clearly, R is the largest distance between P and vertices of the polygon. However, r can be the distance between P and some point lying on the side of the polygon, therefore, r is the smallest distance between P and all sides of the polygon.

To find the shortest distance between a point p and a segment s, consider a straight line l containing the segment s. Clearly, the shortest distance between p and l is the length of the perpendicular segment. One should consider two cases: when the end of the perpendicular segment lies on the segment s (then the answer is the length of the perpendicular segment), or when it lies out of s (then the answer is the shortest distance to the ends of s).

613B - Навыки

Author: cdkrot

Developers: cdkrot, galilei2000, ch_egor

Let's save the original positions of skills and then sort the skills in non-increasing order (almost decreasing) by current level. We can always restore original order after.

Imagine that we have decided that we want to use the minimum level X and now we're choosing which skills we should bring to the maximum.

At first, let's rise all skills below X to level X, this will set some tail of array to X. But the original array was sorted, and this new change will not break the sort! So our array is still sorted.

Obviously, the skills we want to take to the maximum are the ones with highest current level. They are in the prefix of array. It is easy to show that any other selection is no better than this greedy one.

Now we have shown that the optimal strategy is to max out the skills in some prefix. Now let's solve the problem.

Let's iterate over prefix to max out, now on each iteration we need to know the highest minimum we can achieve, let's store the index of the first element outside the prefix such that it is possible to reach the minimum level  ≥ arr_index.

It is easy to recalc this index, it slightly moves forward each turn and, after precalcing the sum of all array's tails, you can update it easily (just move it forward until the invariant above holds). And knowing this index is enough to calc the current highest possible minimum level (min(A, arr_index + ⌊ sparemoney / (n - index)⌋).

How to restore the answer? Actually, all you need to know is the count of maximums to take and minimum level to reach.

613C - Бусы

Author: cdkrot

Developers: cdkrot, crossopt, ch_egor

Surprisingly, the nice cuts can't be put randomly. Let's take a look on the first picture above (red lines represent nice cut points). But since the necklace is symmetrical relative to nice cuts, the cut points are also symmetrical relative to nice cuts, so there is one more cut (see picture two). Repeating this process, we will split the whole necklace into parts of the same size (picture three).

If the number of parts is even, then each part can be taken arbitrarily, but the neighbouring parts must be reverses of each other (e.g. "abc" and "cba"). This is an implication of the cuts being nice.

If the number of parts is odd, then each part is equal to each other and is a palindrome, this is an implication of the cuts being nice too.

Anyway, the number of characters in each part is equal, so amount of parts can't be greater than . Actually, it may be zero, or its divisor.

• If the number of odd-sized colors is zero, then the sum is even and gcd is even, this way we can construct a building block containing exactly beads of i-th color, (gcd being gcd of all counts), then build beads of gcd parts, where each part equal to building block, with neighbouring parts being reverses. Since gcd is even, everything is ok.

• If the number of odd-sized colors is one, then the sum is odd and gcd is odd. Building block have to be built as a palindrome containing beads of i-th color, exactly n - 1 of colors will be even and one odd, put the odd one in center, others on sides (aabcbaa). Everything is ok.

• If num of odd counts is geq2. Gcd is odd, all its divisors too, so our building block has to be palindrome. Let k denote the number of parts. A building block will contain beads of color i, at least two of these numbers are odd, it is impossible to build such a palindrome. The answer is zero.

Complexity: O(sum), just to output answer.

Bonus. How to solve problem, if you are allowed to discard any subset of beads before constructing necklace?

Bonus. Given a necklace scheme (like one you were asked to output), how to determine number of nice cuts, O(sum), no suffix structures or hashes?

613D - Королевство и его города

Authors: ch_egor and others

Developer: cdkrot

Obviously, the answer is -1 iff two important cities are adjacent.

If there was a single query, can we answer it in O(n) time? Let's choose a root arbitrarily. We can note there is an optimal answer that erases two types of vertices: vertices that lie on a vertical path between two important vertices, or LCA of some pair of important vertices.

Let's do a subtree DP that counts the answer for the subtree of v, as well as if there is any important vertex still connected to v in the answer. How do we count it? If v is important, then we should disconnect it from any still-connected vertices from below by erasing these children which contain them. If v is not important, then we erase it iff there are more than one still-connected important vertices below. All calculations are straightforward here.

How do we process many queries now? There are many possible approaches here (for reference, look at the accepted solutions). The author's solution was as follows: if we have a query with k important vertices, then we can actually build an auxiliary tree with O(k) vertices and apply the linear DP solution to it with minor modifications.

How to construct the auxiliary tree? We should remember the observation about LCAs. Before we start, let us DFS the initial tree and store the preorder of the tree (also known as "sort by tin"-order). A classical exercise: to generate all possible LCAs of all pairs among a subset of vertices, it suffices to consider LCAs of consecutive vertices in the preorder. After we find all the LCAs, it is fairly easy to construct the tree in O(k) time. Finally, apply the DP to the auxiliary tree. Note that important cities adjacent in the auxiliary tree are actually not adjacent (since we've handled that case before), so it is possible to disconnect them.

If we use the standard "binary shifts" approach to LCA, we answer the query in time, for a total complexity of .

613E - Любитель кроссвордов

Author, developer: Endagorion

The key observation: any way to cross out the word w looks roughly as follows:

..v<1.>>v.2<...
..>>>>^.>>>^...

That is, there can be following parts:

• go back a symbols in one row, then go forward a symbols in the other row (possibly a = 0)

• go forward with arbitrarily up and down shifts in a snake-like manner

• go forward b symbols in one row, then go back b in the other row (possibly b = 0)

Note that the "forward" direction can be either to the left or to the right. It is convenient that for almost any such way we can determine the "direction" as well as the places where different "parts" of the path (according to the above) start. To avoid ambiguity, we will forbid a = 1 or b = 1 (since such parts can be included into the "snake").

Fix the direction. We will count the DP d_x, y, k for the number of ways to cross out first k letters of w and finished at the cell (x, y) while being inside the snake part of the way. The transitions are fairly clear (since the snake part only moves forward). However, we have to manually handle the first and the last part. For each cell and each value of k we can determine if the "go-back-then-go-forward" maneuver with parameter k can be performed with the chosen cell as finish; this can be reduced to comparing of some substrings of field of rows and the word w (and its reversed copy). In a similar way, for any state we can check if we can append the final "go-forward-then-go-back" part of the path to finally obtain a full-fledged path.

This DP has O(n²) states and transitions. However, there are still some questions left. How do we perform the substring comparisons? There is a whole arsenal of possible options: (carefully implemented) hashes, suffix structures, etc. Probably the simplest way is to use Z-function for a solution that does O(n²) precalc and answers each substring query in O(1) time (can you see how to do it?).

Also, there are paths that we can consider more than once. More precisely, a path that consists only of the "go-forward-the-go-back" part will be counted twice (for both directions), thus we have to subtract such paths explicitly. Every other path is counted only once, thus we are done. (Note: this does not exactly work when w is short, say, 4 symbols or less. The simplest way is to implement straightforward brute-force for such cases.)

As usual, a challenge comes with every problem. I tried not to repeat the mistakes of my previous editorials and made sure that all challenges have a solution =) (except for the italics parts that are open questions, at least for me). Go ahead and discuss them in the comments! General questions about problems and clarification requests are welcomed too.

UPD: I added codes of my solutions for all the problems. I didn't try to make them readable, but I believe most part of them should be clear. Feel free to ask questions.

538A - Разрезание плаката

Let me first clarify the statement (I really wish I didn't have to do that but it seems many participants had trouble with the correct understanding). You had to erase exactly one substring from the given string so that the rest part would form the word CODEFORCES. The (somewhat vague) wording some substring in the English translation may be the case many people thought that many substrings can be erased; still, it is beyond my understanding how to interpret that as 'more than one substring'. Anyway, I'm sorry for the inconvenience.

Right, back to the problem. The most straightforward approach is to try over all substrings (i.e. all starting and ending positions) to erase them and check if the rest is the wanted word. When doing this, you have to be careful not to forget any corner cases, such as: erase few first letters, erase few last letters, erase a single letter, and so on. A popular question was if an empty substring may be erased or not. While it is not clarified explicitly in the statement, the question is irrelevant to the solution, for it is guaranteed in the statement that the initial string is not CODEFORCES, so erasing nothing will not make us happy. From the technical point of view, you could erase a substring from the string using standard functions like substr in C++ or similar, or do some bare-hands work and perform conditional iterating over all symbols. Depending on the implementation, this would be either O(n²) or O(n³) solution; both of these fit nicely.

One way of solving this in linear time is to compute the longest common prefix and suffix for the given string and the string CODEFORCES. If their total length is at least 10 (the length of CODEFORCES), it is possible to leave only some parts of the common prefix and suffix, thus the rest part (being a substring, of course) may be removed for good. If the total length is less than 10, no such way exists. This is clearly O(n) solution (rather O(n) for reading the input, and O(|t|) for comparisons where t is CODEFORCES in our case).

Sample solution: 10973831

Challenge (easy). A somewhat traditional question: how many (modulo some prime number) large Latin letter strings of length n have the property that a (non-empty) substring may be cut out to leave a given string t? Can you solve it in O(n + |t|²) time? In O(n + |t|) time? Maybe even faster? =)

538B - Квазидвоичная сумма

n is up to 10⁶. We may note that there are only 2⁶ + 1 = 65 quasi-binary numbers not exceeding 10⁶, so we could find them all and implement a DP solution that counts the optimal representation for all numbers up to n, or even a brute-force recursive solution (which is not guaranteed to pass, but has a good odds).

Are there more effective solutions? Sure enough. First of all, one can notice that the number of summands in a representation can not be less than d — the largest digit in decimal representation of n. That is true because upon adding a quasi-binary number to any number the largest digit may not increase by more than 1 (easy enough to prove using the standard algorithm for adding numbers). On the other hand, d quasi-binary numbers are always enough. To see that, construct a number m as follows: for every digit of n that is not 0, place 1 in the corresponding digit of m, and for all the other digits place 0. Clearly, m is quasi-binary. If we subtract m from n, all non-zero digits will decrease by 1 (clearly, no carrying will take place), thus the largest digit of n - m will be equal to d - 1. Proceeding this way, we end up with the representation of n as a sum of d quasi-binary numbers. This solution is good for every numeric base, and works in where d is the base.

Sample solution: 10973842

Challenge (easy). Let us call a number pseudo-binary if its decimal representation contains at most two different digits (e.g., 1, 555, 23, 9099 are pseudo-binary, while 103, 908 and 12345 are not). Represent an integer n as a sum of pseudo-binary numbers; minimize the number of summands. n ≤ 10¹⁸.

538C - Записки туриста

We want to make the maximum height as large as possible. Consider the part of the chain that was travelled between d_i and d_i + 1; we can arrange it in any valid way independently of any other parts of the chain, thus we consider all these parts separately. There also parts before d₁ and after d_n, but it is fairly easy to analyze them: make them monotonously decreasing (respectively, increasing), as this maximizes the top point.

Without the loss of generality consider d_i = 0 and d_i + 1 = t (they may be increased of decreased simultaneously without changing the answer), and h_di = a, h_di + 1 = b. Clearly, in consistent data |a - b| ≤ t, so if this condition fails for a single pair of adjacent entries, we conclude the data is flawed.

If the condition holds, it is fairly easy to construct a valid way to move between the days under the |h_i - h_i + 1| ≤ 1 condition: increase or decrease the height while it differs from b, than stay on the same height. That does not make the optimal way, but at least we are sure that the data is not inconsistent.

How to construct the optimal arrangement? From the adjacent difference inequality if follows that for any i between 0 and t the inequalities h_i ≤ a + i and h_i ≤ b + (t - i) hold. Let h_i = min(a + i, b + (t - i)) on the [0; t] segment; clearly, every h_i accomodates the largest possible value, therefore the value of maximum is also the largest possible. It suffices to show that these h_i satisfy the difference condition. Basically, two cases should be considered: if for h_i = a + i and h_i + 1 = a + i + 1, or h_i = b + (t - i) and h_i + 1 = b + (t - i - 1), the statement is obvious. Else, h_i = a + i but h_i < b + (t - i) = h_i + 1 + 1, and h_i + 1 = b - (t - i - 1) but h_i + 1 < a + (i + 1) = h_i + 1. Thus, |h_i - h_i + 1| < 1, and h_i = h_i + 1.

To find the maximum value of maximum height (I really struggle not to use 'maximum maximum') we may either use ternary search on the h function, or find the point where lines a + i and b + (t - i) intersect and try integer points besides the intersection. If we use this approach analytically, we arrive at the formula (t + a + b) / 2 (try to prove that yourself!).

Sample solution: 10973854

Challenge (medium). Given the same data (that is, a subsequence h_di for a sequence h_i), determine how many (modulo a prime number) integer sequences of length n with the property |h_i - h_i + 1| ≤ 1 agree with the subsequence and have global maximum equal to H? Can you solve the problem in O(n²) time? In time? Maybe even faster?

538D - Странные шахматы

Instead of trying to find out where the piece may go, let's try to find out where it can not go. Initially mark all the moves as possible; if there is a field (x₁, y₁) containing a piece, and a field (x₂, y₂) not containing a piece and not being attacked, clearly a move (x₂ - x₁, y₂ - y₁) is not possible. Let us iterate over all pieces and over all non-attacked fields and mark the corresponding moves as impossible.

Suppose we let our piece make all the rest moves (that are not yet marked as impossible), and recreate the position with all the pieces in the same places. If a field was not attacked in the initial position, it will not be attacked in the newly-crafted position: indeed, we have carefully removed all the moves that could take a piece to this field. Thus, the only possible problem with the new position is that some field that was attacked before is not attacked now. But our set of moves is maximal in the sense that adding any other move to it will cause the position to be incorrect. Thus, if the new position doesn't coincide with the initial position, the reconstruction is impossible. Else, we have already obtained a correct set of moves. This solution has complexity of O(n⁴) for iterating over all pieces and non-attacked fields. No optimizations were needed to make solution this pass.

Sample solution: 10973859

Challenge (medium). Solve the same problem in time.

538E - Демиурги играют снова

With such large constraints our only hope is the subtree dynamic programming. Let us analyze the situation and how the subtrees are involved.

Denote w(v) the number of leaves in the subtree of v. Suppose that a non-leaf vertex v has children u₁, ..., u_k, and the numbers to arrange in the leaves are 1, ..., w(v). We are not yet sure how to arrange the numbers but we assume for now that we know everything we need about the children's subtrees.

Okay, what is the maximal number we can achieve if the maximizing player moves first? Clearly, he will choose the subtree optimally for himself, and we are eager to help him. Thus, it makes sense to put all the maximal numbers in a single subtree; indeed, if any of the maximal numbers is not in the subtree where the first player will go, we swap it with some of the not-so-maximal numbers and make the situation even better. If we place w(u_i) maximal numbers (that is, w(v) - w(u_i) + 1, ..., w(v)) in the subtree of w(u_i), we must also arrange them optimally; this task is basically the same as arranging the numbers from 1 to w(u_i) in the subtree of w(u_i), but now the minimizing player goes first. Introduce the notation for the maximal possible result if the maximizing/minimizing (depending on the lower index) player starts. From the previous discussion we obtain . Thus, if we know for all children, the value of can be determined.

How does the situation change when the minimizing player goes first? Suppose that for each i we assign numbers n_1, 1, ..., n_1, w(ui) to the leaves of the subtree of u_i in some order; the numbers in the subtree of u_i will be arranged so that the result is maximal when the maximizing player starts in u_i. Suppose that numbers n_i, j are sorted by increasing of j for every i; the minimizing player will then choose the subtree u_i in such a way that is minimal. For every arrangement, the minimizing player can guarantee himself the result of at most . Indeed, if all the numbers are greater than r, all the numbers n_i, j for should also be greater than r; but there are numbers n_i, j that should be greater than r, while there are only w(v) - r possible numbers from 1 to w(v) to place; a contradiction (pigeonhole principle). On the other hand, the value of r is easily reachable: place all the numbers less than r as n_i, j with , and r as, say, n_{1, dpmax(u1)}; the first player will have to move to u₁ to achieve r. Thus, .

The previous, rather formal argument can be intuitively restated as follows: suppose we put the numbers from 1 to w(v) in that order to different subtrees of v. Once a subtree of u_i contains dp_max(u_i) numbers, the minimizing player can go to u_i and grab the current result. It follows that we may safely put dp_max(u_i) - 1 numbers to the subtree of u(i) for each i, and the next number (exactly r) will be grabbed regardless of what we do (if we do not fail and let the minimizing player grab a smaller number).

That DP scheme makes for an O(n) solution, as processing the k children of each node is done in O(k) (provided their results are already there). As an easy exercise, think about how the optimal arrangement of number in the leaves can be constructed; try to make implementation as simple as possible.

Sample solution: 10973864

Challenge (medium). Suppose that we are given numbers n, a, b, and we want to construct a tree with n leaves such that dp_max(root) = a and dp_min(root) = b. For which numbers n, a, b is this possible? (I'm sure you will like the answer for this one. =)) Can you propose an algorithm that constructs such a tree?

538F - Куча куч

The first approach. For a given k and an element v, how do we count the number of children of v that violate the property? This is basically a range query 'how many numbers in the range are greater than v' (because, evidently, children of any element occupy a subsegment of the array); the answers for every k are exactly the sums of results for queries at all non-leaf vertices. Online data structures for this query type are rather involved; however, we may process the queries offline by decreasing v, with a structure that is able to support an array, change its elements and take sum over a range (e.g., Fenwick tree or segment tree). This can be done as follows: for every element of the initial array store 1 in the same place of the structure array if the element has already been processed, and 0 otherwise. Now, if we sum over the range for the element v, only processed elements will have impact on the sum, and the result of the query will be exactly the number of elements greater than v. After all the queries for v, we put 1 in the corresponding element so that queries for smaller elements would take it into account. That makes for an solution. Estimate q: notice that for a given k there are only non-leaf vertices, thus the total number of queries will be (harmonic sum estimation). To sum up, this solution works in time.

Sample solution (first approach): 10973867

The second approach. Let us index the elements of the array starting from 0. It is easy to check that for a given k the parent of the element a_v is the element . One can show that there are only different elements that can be the parent of a_v for some k. Indeed, if , the index of the parent is less that , and all produce no more than different parents too. Moreover, each possible parent corresponds to a range of values of k. To show that, solve the equality for k. Transform: , pk ≤ v - 1 < (p + 1)k, , . For every k in the range above the property is either violated or not (that depends only on a_v and a_p); if it's violated we should add 1 to all the answers for k's in the range. That can be done in O(1) offline using delta-encoding (storing differences between adjacent elements in the process and prefix-summing them in the end). There will be only queries to the delta array (as this is the number of different child-parent pairs for all k). This makes for a simple solution which barely uses any heavy algorithmic knowledge at all.

Sample solution (second approach): 10973868

Challenge 1 (medium). Denote c_k the minimal number of elements that should be changed (each to a value of your choice) so that the array becomes a valid k-ary heap. Can you find a single c_k (for a given k) in time? Can you find all c_k (for 1 ≤ k ≤ n - 1) at once in O(n²) time? Can you do better than these estimates?

Challenge 2 (hard). Solve the problem from Challenge 1 if an arbitrary rooted tree with numbers in vertices is given (that is, change the minimal number of elements so that no element is greater than its parent). Can you do it in O(n²)? In ? In ? (I'm pretty certain my approach should work, but I would be glad if anyone could check me on this one. That being said, I'm eagerly waiting for your comments.) Not likely, but maybe you could do even better?

538G - Осатаневший робот

First of all, we'll simplify the problem a bit. Note that after every command the values of x + y and x - y are altered by  ± 1 independently. Suppose we have a one-dimensional problem: given a sequence of x's and t's, provide a looped program of length l with commands  ± 1 which agrees with the data. If we are able to solve this problem for numbers x_i + y_i and x_i - y_i separately, we can combine the answers to obtain a correct program for the original problem; if one of the subproblems fails, no answer exists. (Most — if not all — participants who solved this problem during the contest did not use this trick and went straight ahead to the two-dimensional problem. While the idea is basically the same, I'm not going into details for their approach, but you can view the submitted codes of contestants for more info on this one.)

Ok, now to solve the one-dimensional problem. Let us change the command set from  ± 1 to  + 0 /  + 1: set . If the division fails to produce an integer for some entry, we must conclude that the data is inconsistent (because x_i and t_i should have the same parity). Now it is clear to see that the operation  - 1 becomes operation 0, and the operation  + 1 stays as it is.

A program now is a string of length l that consists of 0's and 1's. Denote s_i the number of 1's among the first i commands, and s = s_l for simplicity. Evidently, an equation holds, because the full cycle is executed ⌊ t_i / l⌋ times, and after that more first commands. From this, we deduce .

Suppose that we know what s is equal to. Using this, we can compute all ; they are fixed from now on. One more important fixed value is s_l = s. In any correct program s_i ≤ s_i + 1 ≤ s_i + 1, but not all values of s_i are known to us. When is it possible to fill out the rest of s_i to match a correct program? If s_a and s_b are adjacent entries that are fixed (that is, every s_c under a < c < b is not fixed), the inequality 0 ≤ s_b - s_a ≤ b - a must hold (a and b may coincide if for different i several values of coincide). Furthermore, if the inequality holds for every pair of adjacent fixed entries, a correct program can be restored easily: move over the fixed values, and place s_b - s_a 1's between positions a and b in any possible way, fill with 0's all the other positions in between.

The trouble is that we don't know s in advance. However, we know the positions and the order in which fixed values of s_a come! Sort them by non-decreasing of a. All fixed s_a can be expressed as linear functions of s; if we substitute these expressions in the 0 ≤ s_b - s_a ≤ b - a, from each pair of adjacent fixed values we obtain an inequality of general form 0 ≤ p·s + q ≤ d, where p, q, d are known values. If the obtained system of inequalities has a solution, we can get ourselves a valid s and restore the program as discussed above.

It suffices to notice that every inequality of the system has a set of solutions of general form l ≤ s ≤ r (if the set is not empty), where l and r should be calculated carefully depending on the sign of p. All the intervals should be intersected, and the resulting interval provides a range of valid values of s.

Overall, the solution works in , or even in O(n + l) if we use bucketing instead of sorting. Note that the l summand in the complexity is only there for the actual program reconstruction; if we were only to check the existence of a program, an O(n) solution would be possible.

Sample solution: 10973870

Challenge (kinda hard). Under the same statement, how many (modulo a prime number) different programs agree with the given data? Assume that all elementary modulo operations (including division) take O(1) time. Can you solve this problem in O(nl)? In O(n + l)? Maybe even better (in , for example?)

538H - Летняя дихотомия

The problem has several possible approaches.

The first approach. More popular one. Forget about t and T for a moment; we have to separate teachers into two groups so that no conflicting teachers are in the same group, and the number of students in each group can be chosen to satisfy all the teachers.

Consider a connected component via the edges which correspong to conflicting pairs. If the component is not bipartite, there is clearly no valid distribution. Else, the teachers in the component can be separated into two sets such that each set should be in the same group, and the groups for the sets should be different. The teachers in the same set will always go together in the same group, so we may as well make them into a single teacher whose interval is the intersection of all the intervals for the teachers we just compressed. Now, the graph is the set of disjoint edges (for simplicity, if a teacher does not conflict with anyone, connect him with a 'fake' teacher whose interval is [0;∞]).

Consider all possible distributions of students; they are given by a pair (n₁, n₂). Provided this distribution, in what cases a pair of conflicting teachers can be arranged correctly? If the teachers' segments are [l₁, r₁] and [l₂, r₂], either l₁ ≤ n₁ ≤ r₁ and l₂ ≤ n₂ ≤ r₂, or l₂ ≤ n₁ ≤ r₂ and l₁ ≤ n₂ ≤ r₁ must hold. Consider a coordinate plane, where a point (x, y) corresponds to a possible distribution of students. For a pair of conflicting teachers the valid configurations lie in the union of two rectangles which are given by the inequalities above. Valid configurations that satisfy all pairs of teachers lie exactly in the intersection of all these figures. Thus, the problem transformed to a (kinda) geometrical one.

A classical approach to this kind of problems is to perform line-sweeping. Note that any 'union of two rectangles' figure (we'll shorten it to UOTR) is symmetrical with respect to the diagonal line x = y. It follows that for any x the intersection of the vertical line given by x with any UOTR is a subsegment of y's. When x sweeps from left to right, for any UOTR there are O(1) events when a subsegment changes. Sort the events altogether and perform the sweeping while updating the sets of subsegments' left and right ends and the subsegments intersection (which is easy to find, given the sets). Once the intersection becomes non-empty, we obtain a pair (x, y) that satisfies all the pairs of teachers; to restore the distribution is now fairly easy (don't forget that every teacher may actually be a compressed set of teachers!).

Didn't we forget something? Right, there are bounds t and T to consider! Consider an adjacent set of events which occurs when x = x₁ and x = x₂ respectively. The intersection of subsegments for UOTRs obtained after the first event will stay the same while x₁ ≤ x < x₂. Suppose the y's subsegmen intersection is equal to [l;r]. If we stay within x₁ ≤ x < x₂, for a satisfying pair of (x, y) the minimal value of x + y is equal to x₁ + l, and the maximal value is x₂ + r - 1. If this range does not intersect with [t;T], no answer is produced this turn. In the other case, choose x and y while satisfying all boundaries upon x, y and x + y (consider all cases the rectangle can intersect with a 45-angle diagonal strip). Thus, the requirement of t and T does not make our life much harder.

This solution can be implemented in using an efficient data structure like std::set or any self-balancing BST for sets of subsegments' ends. The very same solution can be implemented in the flavour of rectangles union problem canonical solution: represent a query 'add 1 to all the points inside UORT' with queries 'add x to all the points inside a rectangle', and find a point with the value m.

Sample solution (first approach): 10973887

The second approach. Less popular, and probably much more surprising.

Imagine that the values of t and T are small. Introduce the set of boolean variables z_i, j which correspond to the event 'n_i does not exceed j' (i is either 1 or 2, j ranges from 0 to T). There are fairly obvious implication relations between them: . As t ≤ n₁ + n₂ ≤ T, we must also introduce implications (here i' is 1 or 2 not equal to i) because if a + b ≥ t and a ≤ j, b must be at least t - j, and for a similar reason. In this, z_i, j for j < 0 clearly must be considered automatically false, and z_i, j for j ≥ T must be considered automatically true (to avoid boundary fails).

The last thing to consider is the teachers. For every teacher introduce a binary variable w_j which corresponds to the event 'teacher j tutors the first group'. The implications and are pretty much self-explanating. A conflicting pair of teachers j and k is resolved in a straightforward way: , .

If a set of values for all the boolean variables described satisfies all the restrictions, a valid distribution can be restored explicitly: n₁ and n₂ are maximal so that z_1, n1 and z_2, n2 hold, and the teachers are distributed unequivocally by values of w_j. It suffices to notice that the boolean system is a 2-SAT instance, and can be solved in linear time. If we count carefully, we obtain that the whole solution has linear complexity as well: O(n + m + T).

Didn't we forget something? Right! The value of T may be too much to handle Ω(T) variables explicitly. To avoid that, one may notice that the set of possible values of n₁ and n₂ may be reduced to 0, t, l_i, t - l_i, r_i, t - r_i. We can prove that by starting from any valid values of n₁ and n₂ and trying to make them as small as possible; the listed values are the ones we may end up with. Thus, we can only use O(n) variables instead of Ω(T). The implications can be built similarily, but using lower/upper bound on the list of possible values instead of exact values (much care is advised!). Finally, this solution can be made to work in , with the logarithmic factor from all the sorting and lower/upperbounding.

Sample solution (second approach): 10973881

Challenge (easy, for a change) Don't you think it's wrong that a group may be without a teacher altogether? Come up with an algorithm that finds a distribution that places at least one teacher in each group. The complexity should not become worse. How about at least k teachers in each group?

Whew, wasn't it a long run! I tried to be verbose and elaborate where it was possible, hope it was worth the wait. Let me know what you think of this write-up!

Hello, Codeforces!

On Sunday, April 26th at 19:00 MSK the 300'th regular Codeforces Round will take place.

I would like to congratulate all Codeforces members and administration on this remarkable milestone. The platform has grown hugely in size and quality since its foundation, has hosted lots of exciting competitions, and has been providing the opportunity to everyone to hone their problem solving and algorithmic mastery. For this we thank the Codeforces platform creator MikeMirzayanov and all the Codeforces crew. Keep up the incredible job, guys!

That being said, I'm excited to announce that the problems on the jubilee three-hundredth Codeforces Round will be set by me, Mikhail Tikhomirov (Endagorion). You may remember the past rounds with my problems: #99, #109, #265, #283, and (in part) #295. I thank the Codeforces problems coordinator Max Akhmedov (Zlobober) for helping me in preparing this round, and Maria Belova Delinur for translating the statements in English. Also, special gratitude to Vladislav Isenbaev (winger), Alex Fetisov (AlexFetisov) and Pavel Kunyavskiy (PavelKunyavskiy) for testing the problemset and help with preparation.

This round will be shared for both divisions and will last two hours and a half (as you can see at the Contests page). The round will feature several ( ≥ 6) problems, varying in difficulty and topics involved. I hope that everyone will find an interesting and satisfying problem just for themselves! The scoring will be announced later.

To add up to the excitement, there are 30 exclusive Codeforces T-shirts to compete for in this round! The top 15 participants will get their T-shirts right away; another 15 will be randomly distributed among those who place in the top 300. Even if you think your chances on being the very best are weak, there are still good odds you will get a treat! =)

That's it. Mark your calendars and come back to compete for the prizes and for the fun!

UPD: there will be 8 problems. The scoring is standard (i.e. not dynamic): 500-1000-1500-1500-2000-2500-3000-3000.

UPD2. In order to choose people getting T-Shirts we will use the following python3.4 code that you can manually run in "custom invocation" tab on Codeforces. It uses an integer as a seed for random generator, this integer should be equal to the last submission number that happened during the contest.

import random
seed = int(input())
rnd = random.Random(seed)
# all contestants except top-15
contestants = list(range(16, 301))
rnd.shuffle(contestants)
tshirts = list(range(1, 16)) + contestants[:15]
for x in sorted(tshirts):
    print(x)

UPD3: Thanks for participating!

The winners are:

1. bmerry
2. Egor
3. Petr
4. rng_58
5. scott_wu
6. jqdai0815
7. eatmore
8. atetubou
9. qwerty787788
10. niyaznigmatul

The list of places getting the T-shirts are 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 40 46 67 75 80 102 103 144 152 161 169 198 233 243 269. The lucky participants are as follows: bmerry, Egor, Petr, rng_58, scott_wu, jqdai0815, eatmore, atetubou, qwerty787788, niyaznigmatul, gs12117, W4yneb0t, JoeyWheeler, zxqfl, yeputons, kcm1700 & HYPERHYPERHYPERCUBELOVER (sharing the 40-th place, so both get a T-shirt), piob, Leo_Yu, matrix & Nerevar (sharing the 75-th place), Haghani, ACube, DemiGuo, etal, Emarci15, hlwt, Salvare001, dzy97, FatalEagle, gchebanov & Jimanbanashi (sharing the 243-rd place), and Solaris (please let me know about any mistakes). Congratulations!

UPD4: At long last, the editorial is up! Enjoy, and sorry for the waiting.

We would like to thank the testers of this round's and Winter Computer Camp olympiad's problems: alger95, thefacetakt, adamant, -imc-, riskingh, ASverdlov.

Make sure to comment if you find any mistakes.

UPD: I've just remembered to put up the usual challenges for the problems. So, here they go.

520A - Pangram

Idea: Endagorion

Preparation: Endagorion

To check that every letter is present in the string we can just make a boolean array of size 26 and for every letter set the corresponding variable to TRUE. In the end check that there are 26 TRUEs. That is an O(n) solution. Also don't forget to change all letters to lowercase (or all to uppercase).

To make all the letters lowercase, one could use standard functions, like tolower in Python. Also, it is known that the letters from a to z have consecutive ASCII numbers, as well as A to Z; an ASCII number of symbol is ord(c) in most languages. So, to get the number of a lowercase letter in the alphabet one can use ord(c) - ord('a') in most languages, or simply c - 'a' in C++ or C (because a char in C/C++ can be treated as a number); to check if a letter is lowercase, the inequality ord('a') <= ord(c) && ord(c) <= ord('z') should be checked.

Challenge: how many pangrams of length n are there? Strings that differ only in capitalization of some letters are considered distinct. Can you find the answer modulo some prime p in linear time?

520B - Two Buttons

Idea: Endagorion

Preparation: Endagorion

The simplest solution is simply doing a breadth-first search. Construct a graph with numbers as vertices and edges leading from one number to another if an operation can be made to change one number to the other. We may note that it is never reasonable to make the number larger than 2m, so under provided limitations the graph will contain at most 2·10⁴ vertices and 4·10⁴ edges, and the BFS should work real fast.

There is, however, an even faster solution. The problem can be reversed as follows: we should get the number n starting from m using the operations "add 1 to the number" and "divide the number by 2 if it is even".

Suppose that at some point we perform two operations of type 1 and then one operation of type 2; but in this case one operation of type 2 and one operation of type 1 would lead to the same result, and the sequence would contain less operations then before. That reasoning implies that in an optimal answer more than one consecutive operation of type 1 is possible only if no operations of type 2 follow, that is, the only situation where it makes sense is when n is smaller than m and we just need to make it large enough. Under this constraint, there is the only correct sequence of moves: if n is smaller than m, we just add 1 until they become equal; else we divide n by 2 if it is even, or add 1 and then divide by 2 if it is odd. The length of this sequence can be found in .

Challenge: suppose we have a generalized problem: we want to get n starting from m using two operations "subtract a" and "multiply by b". Generalize the solution to find the minimal number of moves to get from n to m in time if a and b are coprime. Can you do it if a and b may have common divisors greater than 1?

520C - DNA Alignment/521A - DNA Alignment

Idea: Endagorion

Preparation: Endagorion

What is ρ(s, t) equal to? For every character of s and every character of t there is a unique cyclic shift of t that superposes these characters (indeed, after 0, ..., n - 1 shifts the character in t occupies different positions, and one of them matches the one of the character of s); therefore, there exist n cyclic shifts of s and t that superpose these characters (the situation is symmetrical for every position of the character of s). It follows that the input in ρ from a single character t_i is equal to n × (the number of characters in s equal to t_i). Therefore, ρ(s, t) is maximal when every character of t occurs the maximal possible number of times in s. Simply count the number of occurences for every type of characters; the answer is Kⁿ, where K is the number of character types that occur in s most frequently. This is an O(n) solution.

Challenge: we know that ρ_max(s) = n²·C(s), where C(s) is the maximal number that any character occurs in s. How many strings s of length n with characters from an alphabet of size k have C(s) = m? Can you find an O(kn²) solution? An solution? An solution? Maybe even better? (Hint: the modulo should be an appropriately chosen prime number for a fast solution =)).

520D - Cubes/521B - Cubes

Idea: savinov

Preparation: savinov, sokian, zemen

Basically, the first player should maximize the lexicographical order of numbers, and the second player should minimize it. Thus, at every move the first player should choose the largest available number, and the second should choose the minimal one.

First of all, how do we check if the cube can be removed? It is impossible only if there is some cube "supported" by it (i.e., it has coordinates (x - 1, y + 1), (x, y + 1), (x + 1, y + 1)) such that our cube is the only one supporting it. This can be checked explicitly. The large coordinates' limitations do not allow us to store a simply array for that, so we should use an associative array, like a set in C++.

Now we should find the maximal/minimal number that can be removed. A simple linear search won't work fast enough, so we store another data structure containing all numbers available to remove; the structure should allow inserting, erasing and finding global minimum/maximum, so the set C++ structure fits again.

When we've made our move, some cubes may have become available or unavailable to remove. However, there is an O(1) amount of cubes we have to recheck and possibly insert/erase from our structure: the cubes (x ± 1, y) and (x ± 2, y) may have become unavailable because some higher cube has become dangerous (that is, there is a single cube supporting it), and some of the cubes (x - 1, y - 1), (x, y - 1) and (x + 1, y - 1) may have become available because our cube was the only dangerous cube that it has been supporting. Anyway, a simple recheck for these cubes will handle all the cases.

This solution is if using the appropriate data structure.

Challenge (inspired by questions from jk_qq and RetiredAmrMahmoud): suppose that the players put the numbers from right to left, that is, from the least significant digit to the most significant. The first player still wants to maximize the resulting number, and the second wants to minimize it. If the original rules of taking cubes apply, finding the optimal strategy for the players seems intractable. Try to solve this problem in the case where all the cubes are stacked in several independent towers; that is, a cube may only be taken from the top of any tower.

520E - Pluses everywhere/521C - Pluses everywhere

Idea: Endagorion

Preparation: gchebanov, DPR-pavlin

Consider some way of placing all the pluses, and a single digit d_i (digits in the string are numbered starting from 0 from left to right). This digit gives input of d_i·10^l to the total sum, where l is the distance to the nearest plus from the right, or to the end of string if there are no pluses there. If we sum up these quantities for all digits and all ways of placing the pluses, we will obtain the answer.

For a given digit d_i and some fixed l, how many ways are there to place the pluses? First of all, consider the case when the part containing the digit d_i is not last, that is, i + l < n - 1. There are n - 1 gaps to place pluses in total; the constraint about d_i and the distance l means that after digits d_i, ..., d_{i + l - 1} there are no pluses, while after the digit d_i + l there should be a plus. That is, the string should look as follows:

Here a dot means a gap without a plus, and a question mark means that it's not important whether there is a plus or not. So, out of n - 1 possible gaps there are l + 1 gaps which states are defined, and there is one plus used in these gaps. That means that the other (n - 1) - (l + 1) = n - l - 2 gaps may contain k - 1 pluses in any possible way; that is, the number of such placements is . A similar reasoning implies that if the digit d_i is in the last part, that is, i + l = n - 1, the number of placements is .

To sum up, the total answer is equal to

Let us transform the sum:

To compute these sums, we will need to know all powers of 10 up to n-th (modulo 10⁹ + 7), along with the binomial coefficients. To compute the binomials, recall that , so it is enough to know all the numbers k! for k upto n, along with their modular inverses. Also we should use the prefix sums of d_i, that is, the array . The rest is simple evaluation of the above sums.

The total complexity is , because the common algorithms for modular inverses (that is, Ferma's little theorem exponentiation or solving a diophantine equation using the Euclid's algorithm) have theoritcal worst-case complexity of . However, one can utilize a neat trick for finding modular inverses for first n consecutive numbers in linear time for a total complexity of O(n); for the description of the method refer to this comment by Kaban-5 (not sure why it has a negative rating, I found this quite insightful; maybe anyone can give a proper source for this method?).

Challenge: now we want to find the sum of all expressions that are made by placing k pluses with a ≤ k ≤ b; that is, we want to find the sum of the answers for the original problem with k = a, ..., b; here a and b can be any integers with 0 ≤ a ≤ b ≤ n - 1. There is an obvious O(n²) solution: just find the answers for all k separately. Can you find a linear solution?

521D - Shop

Idea: Endagorion

Preparation: gchebanov

Suppose the only type of upgrades we have is multiplication. It doesn't even matter for the answer which particular skill we are going to multiply, so we just choose several upgrades with greatest values of b_i.

Now we have additions as well; set multiplications aside for a moment. It is clear that for every skill we should choose several largest additions (maybe none). Let us sort the additions for every skill by non-increasing; now we should choose several first upgrades for each type. Now, for some skill the (non-increasing) sorted row of b's is b₁, ..., b_l, and the initial value of the skill is a. Now, as we have decided to take some prefix of b's, we know that if we take the upgrade b_i, the value changes from a + b₁ + ... + b_i - 1 to a + b₁ + ... + b_i - 1 + b_i. That is, the ratio by which the value (and the whole product of values) is going to be multiplied by is the fraction . Now, with that ratio determined unambigiously for each addition upgrade, every addition has actually become a multiplication. =) So we have to compute the ratios for all additions (that is, we sort b's for each skill separately and find the fractions), and then sort the multiplications and additions altogether by the ratio they affect the whole product with. Clearly, all multiplications should be used after all the additions are done; that is, to choose which upgrades we use we should do the ratio sorting, but the order of actual using of upgrades is: first do all the additions, then do all the multiplications.

Finally, let's deal with the assignment upgrades. Clearly, for each skill at most one assignment upgrade should be used, and if it used, it should the assignment upgrade with the largest b among all assignments for this skill. Also, if the assignment is used, it should be used before all the additions and multiplications for this skill. So, for each skill we should simply determine whether we use the largest assignment for this skill or not. However, if we use the assignment, the ratios for the additions of current skill become invalid as the starting value of a is altered.

To deal with this problem, imagine that we have first chosen some addition upgrades, and now we have to choose whether we use the assignment upgrade or not. If we do, the value of the skill changes from a + b₁ + ... + b_k to b + b₁ + ... + b_k. That is, the assignment here behaves pretty much the same way as the addition of b - a. The only difference is that once we have chosen to use the assignment, we should put it before all the additions.

That is, all largest assigments for each skill should be made into additions of b - a and processed along with all the other additions, which are, as we already know, going to become multiplications in the end. =)

Finally, the problem is reduced to sorting the ratios for all upgrades. Let us estimate the numbers in the fractions. The ratio for a multiplication is an integer up to 10⁶; the ratio for an addition is a fraction of general form . As k can be up to 10⁵, and b_i is up to 10⁶, the numerator and denominator of such fraction can go up to 10¹¹. To compare fractions and we should compare the products ad and bc, which can go up to 10²² by our estimates. That, unfortunately, overflows built-in integer types in most languages. However, this problem can be solved by subtracting 1 from all ratios (which clearly does not change the order of ratios), so that the additions' ratios will look like . Now, the numerator is up to 10⁶, the products in the comparison are up to 10¹⁷, which fits in 64-bit integer type in any language.

Challenge: suppose that you have to compare two fractions and , where a, b, c, d may be up to 10¹⁸. What way would you use to do that? Can you find a simple solution that does not involve long arithmetics, floating-point number or magic built-in integer types tricks (but may perform a non-constant number of operations)?

521E - Cycling City

Idea: Endagorion

Preparation: Endagorion

We have to find two vertices in an undirected graph such that there exist three vertex- and edge-independent paths between them. This could easily be a flow problem if not for the large constraints.

First of all, we can notice that all the paths between vertices should lie in the same biconnected component of the graph. Indeed, for every simple cycle all of its edges should lie in the same biconnected component, and the three-paths system is a union of cycles. Thus, we can find all the biconnected components of the graph and try to solve the problem for each of them independently. The computing of biconnected components can be done in linear time; a neat algorithm for doing this is described in the Wikipedia article by the link above.

Now, we have a biconnected component and the same problem as before. First of all, find any cycle in this component (with a simple DFS); the only case of a biconnected component that does not contain a cycle is a single edge, which is of no interest. Suppose that no vertex of this cycle has an adjacent edge that doesn't lie in the cycle; this means the cycle is not connected to anything else in the component, so the component is this cycle itself, in which case there is clearly no solution.

Otherwise, find a vertex v with an adjacent edge e that doesn't lie in the cycle (denote it c). If we can find a path p starting with e that arrives at a cycle vertex u (different from v), then we can find three vertex-distinct paths between v and u: one path is p, and two others are halves of the initial cycle. To find p, start a DFS from the edge e that halts when it arrives to vertex of c (that is different from v) and recovers all the paths.

What if we find that no appropriate path p exists? Denote C the component traversed by the latter DFS. The DFS did not find any path between vertices of C\ {v} and c\ {v}, therefore every such path should pass through v. That means that upon deletion of v, the component C\ {v} becomes separated from all vertices of c\ {v}, which contradicts with the assumption that the component was biconnected. That reasoning proves that the DFS starting from e will always find the path p and find the answer if only a biconnected component was not a cycle nor a single edge.

Finally, we obtain that the only case when the answer is non-existent is when all the biconnected components are single edges or simple cycles, that is, the graph is a union of disconnected cactuses. Otherwise, a couple of DFS are sure to find three vertex-disjoint paths. This yields an O(n + m) solution; a few logarithmic factors for simplification here and there are also allowed.

Challenge: how many graphs G on n labeled vertices exist such that there exist two vertices of G connected by three disjoint paths? (Hint: we have already shown that it suffices to count the number of disjoint unions of cacti.) Find the answer modulo 10⁹ + 7. Can you come up with any polynomial-time solution? An O(n³) solution? Maybe even better?

Hello, Codeforces!

On March, 2nd at 10:00 MSK Codeforces Round #295 will be held in both divisions.

The round will be held at the same time with Winter Computer Camp olympiad, the problemsets will be highly similar. The problems are by me (Endagorion) and Evgeny Savinov (savinov). The problems are prepared by members of the Winter Computer Camp technical committee: Georgy Chebanov (gchebanov), Filipp Rukhovich (DPR-pavlin), Alexander Mashrabov (map), Sergey Kiyan (sokian), Konstantin Semenov (zemen), Kinan Alsarmini (Sarkin).

Big thanks to Max Akhmedov (Zlobober) for his help with preparing the problems, Maria Belova (Delinur) for translating the statements in English, and Mike Mirzayanov (MikeMirzayanov) for creating Codeforces and Polygon systems.

The scoring is standard for both divisions: 500-1000-1500-2000-2500.

Please note that the Winter Computing Camp olympiad is scheduled to finish later than the Codeforces round. Thus, we ask you not to discuss the problems and solutions in the comments until 14:10 MSK. Also, viewing of other participants' solutions will be closed until that time. The editorial will also be published later.

UPD: you are free to discuss the problems now.

UPD2: the editorial is finally up! Sorry for the delay.

Also, grats to our Div.1 winners:

1. Petr
2. hos.lyric
3. Syloviaely
4. andrew.volchek
5. xyz111

Special respect goes to Petr and rng_58 for solving the hardest problem E!

Each problem comes with a challenge — a bonus task somehow related to the problem; you may tackle at the challenges for fun and practice, also feel free to discuss them at the comments. =)

496A - Minimum Difficulty

For every option of removing an element we run through the remaining elements and find the maximal difference between adjacent ones; print the smallest found answer. The solution has complexity O(n²). It can be noticed that after removing an element the difficulty either stays the same or becomes equal to the difference between the neighbours of the removed element (whatever is larger); thus, the difficulty for every option of removing an element can be found in O(1), for the total complexity of O(n). Any of these solutions (or even less efficient ones) could pass the tests.

Challenge: suppose we now have to remove exactly k arbitrary elements (but the first and the last elements have to stay in their places). How small the maximal difference between adjacent elements can become? Solve this problem assuming the limitations are as follows: 1 ≤ k ≤ n - 2, n ≤ 10⁵, a_i ≤ 10⁹.

496B - Secret Combination

We observe that the order of operations is not important: we may first perform all the shifts, and after that all the additions. Note that after n shifts the sequence returns to its original state, therefore it is sufficient to consider only the options with less than n shifts. Also, after 10 times of adding 1 to all digits the sequence does not change; we may consider only options with less than 10 additions. Thus, there are overall 10n reasonable options for performing the operations; for every option perform the operations and find the smallest answer among all the options. As performing the operations for every option and comparing two answers to choose the best takes O(n) operations, this solution performs about 10n² elementary operations. The multiple of 10 can be get rid of, if we note that after all shifts are made the best choice is to make the first digit equal to zero, and this leaves us but a single option for the number of additions. However, implementing this optimization is not necessary to get accepted.

Challenge: can you solve the problem in time? in O(n) time?

496C - Removing Columns/497A - Removing Columns

Let's look at the first column of the table. If its letters are not sorted alphabetically, then in any valid choice of removing some columns it has to be removed. However, if its letters are sorted, then for every valid choice that has this column removed it can be restored back to the table; it is clear that the new choice is valid (that is, the rows of the new table are sorted lexicographically) and the answer (that is, the number of removed columns) has just became smaller.

Consider all columns from left to right. We have already chosen which columns to remove among all the columns to the left of the current one; if leaving the current column in place breaks the lexicographical order of rows, then we have to remove it; otherwise, we may leave it in place to no harm. Arguing in the way of the previous paragraph we can prove that this greedy method yields an optimal (moreover, the only optimal) solution. The complexity is O(n²).

Challenge: compute how many (say, modulo 10⁹ + 7) n × m tables are there for which the answer for this problem is k? The more efficient solution you come up with, the better.

496D - Tennis Game/497B - Tennis Game

Choose some t; now emulate how the match will go, ensure that the record is valid for this t and by the way find the corresponding value of s. Print all valid options for s and t. This solution works in O(n²) time, which is not good enough, but we will try to optimize it.

Suppose the current set if finished and we have processed k serves by now. Let us process the next set as follows: find t-th 1 and t-th 2 after position k. If t-th 1 occurs earlier, then the first player wins the set, and the set concludes right after the t-th 1; the other case is handled symmetrically. If the match is not over yet, and in the rest of the record there are no t ones nor t twos, then the record is clearly invalid. This way, every single set in the record can be processed in time using binary search, or O(1) time using precomputed arrays of positions for each player.

Now observe that for any t a match of n serves can not contain more than n / t sets, as each set contains at least t serves. If we sum up the upper limits for the number of sets for each t, we obtain the total upper limit for the number of sets we may need to process: (which is the famous harmonic sum). Using one of the approaches discussed above, one obtains a solution with complexity of or ; each of these solutions fits the limit nicely.

Obviously, for every t there is no more than one valid choice for s; however, maybe a bit unexpected, for a given s there may exist more than one valid choice of t. The first test where this takes place is pretest 12. The statement requires that the pairs are printed lexicographically ordered; it is possible to make a mistake here and print the pairs with equal s by descending t (if we fill the array by increasing t and then simply reverse the array).

Challenge: while preparing this problem I discovered that it's quite hard to find a test such that the number of pairs in the answer is large; in the actual tests the maximal number is 128, which is the number of divisors of the number 83160. Can you beat this record? If you have a test with n ≤ 10⁵ that has larger number of pairs in the answer, feel free to brag in the comments; also don't hesitate to share any insights on how one could bound the maximal number analytically.

496E - Distributing Parts /497C - Distributing Parts

Sort all the parts and actors altogether by increasing lower bounds (if equal, actors precede parts); process all the enitities in this order. We maintain a set of actors which have already occured in the order; if we meet an entry for an actor, add it to the set. If we currently process a part, we have to assign it to an actor; from the current set of actors we have to choose one such that his d_i ≥ b_j (the c_i ≤ a_j constraint is provided by the fact that the i-th actor has occured earlier than the j-th part); if there are no such actors in the set, no answer can be obtained; if there are several actors satisftying this requirement, we should choose one with minimal d_i (intuitively, he will be less useful in the future). Assign the chosen actor with the current part and decrement his k_i; if k_i is now zero, the actor can not be used anymore, thus we remove him from the set.

To fit the limits we should implement the set of current actors as some efficient data structure (e.g., an std::set or a treap). The resulting complexity is .

Challenge: suppose that now there are q_j copies of the j-th part (1 ≤ q_j ≤ 10⁹), and each copy must be separately assigned with an actor in a valid way. Can you solve this new problem with all the old constraints (as the actual distribution now has too much entries, it is sufficient to check whether an answer exists)?

497D - Gears

When a collision happens, a vertex of one polygon lands on a side of the other polygon. Consider a reference system such that the polygon A is not moving. In this system the polygon B preserves its orientation (that is, does not rotate), and each of its vertices moves on some circle. Intersect all the circles for vertices of B with all the sides of A; if any of them intersect, then some vertex of B collides with a side of A. Symmetrically, take a reference system associated with B and check whether some vertex of A collides with a side of B. The constraints for the points' coordinates are small enough for a solution with absolute precision to be possible (using built-in integer types).

Another approach (which is, in fact, basically the same) is such: suppose there is a collision in a reference system associated with A. Then the following equality for vectors holds: x + y = z; here z is a vector that starts at P and ends somewhere on the bound of A, x is a vector that starts at Q and ends somewhere on the bound of B, y is a vector that starts at P and ends somewhere on the circle centered at P that passes through Q. Rewrite the equality as y = z - x; now observe that the set of all possible values of z - x forms the Minkowski sum of A and reflection of B (up to some shift), and the set of all possible values of y is a circle with known parameters. The Minkowski sum can be represented as a union of nm parallelograms, each of which is the Minkowski sum of a pair of sides of different polygons; finally, intersect all parallelograms with the circle.

Both solutions have complexity O(nm). As noted above, it is possible to solve the problem using integer arithemetics (that is, with absolute precision); however, the fact that the points' coordinates are small lets most of the solutions with floating point arithmetics pass. It was tempting to write an approximate numerical solution; we struggled hard not to let such solutions pass, and eventually none of them did. =)

Many participants had troubles with pretest 8. It looks as follows (the left spiral revolves around the left point, and the right spiral revolves around the right point):

Challenge: suppose we want a solution that uses floating point arithmetics to fail. In order to do that, we want to construct a test such that the polygons don't collide but pass really close to each other. How small a (positive) distance we can achieve, given the same constraints for the number of points and the points' coordinates?

497E - Subsequences Return

Consider some string; how does one count the number of its distinct subsequences? Let us append symbols to the string consequently and each time count the number of subsequences that were not present before. Let's append a symbol c to a string s; in the string s + c there are as many subsequences that end in c as there were subsequences in s overall. Add all these subsequences to the number of subsequnces of s; now each subsequence is counted once, except for the subsequences that end in c but were already present in s before; these are counted twice. Thus, the total number of subsequences in the new string is twice the total number of subsequences in the old string minus the number of subsequences in the old string which end in c.

This leads us to the following solution: for each symbol c store how many subsequences end in c, denote cnt_c. Append symbol c; now cnt_c becomes equal to the sum of all cnt's plus one (for the empty subsequence), and all the other cnt's do not change.

For example, consider the first few symbols of the Thue-Morse sequence:

• ε — (0, 0)

• 0 — ( 0 + 0 + 1 = 1, 0)

• 01 — (1, 1 + 0 + 1 = 2)

• 011 — (1, 1 + 2 + 1 = 4)

• 0110 — ( 1 + 4 + 1 = 6, 4)

• ...

Let us put the values of cnt in the coordinates of a vector, and also append a coordinate which is always equal to 1. It is now clear that appending a symbol to the string alters the vector as a multiplication by some matrix. Let us assign a matrix for each symbol, and also for each string as a product of matrices for the symbols of the strings in that order.

Now, consider the prefix of the sequence a_i of length k^m. Divide it into k parts of length k^m - 1; x-th (0-based) of these parts can be obtained from the 0-th one by adding x modulo k to all elements of the part. Let us count the matrices (see above) for the prefixes of length k^m, and also for all strings that are obtained by adding x to all of the prefixes' elements; denote such matrix A_m, x.

It is easy to see that if m > 0, then . This formula allows us to count A_m, x for all and all x from 0 to k - 1 in time. Now, upon having all A_m, x we can multiply some of them in the right order to obtain the matrix for the prefix of the sequence a_i of length n.

Unfortunately, this is not quite enough as the solution doesn't fit the time limit yet. Here is one way to speed up sufficiently: note that the product in the formula can be divided as shown: A_{m - 1, x}... A_{m - 1, k - 1} × A_{m - 1, 0}... A_{m - 1, x - 1} (if x = 0, take the second part to be empty). Count all the "prefixes" and "suffixes" products of the set A_m, x: P_m, x = A_m, 0... A_{m, x - 1}, S_m, x = A_m, x... A_{m, k - 1}. Now A_m, x = S_{m - 1, x}P_{m - 1, x}. Thus, the computation of A_m, x for all x and a given m can be done as computing all P_{m - 1, x}, S_{m - 1, x} using O(k) matrix multiplications, and each A_m, x is now can be found using one matrix multiplication. Finally, the solution now works in time, which fits the limits by a margin.

Challenge: solve the problem for k ≤ 100.

Hi, Codeforces.

Today, on December 17 at 19:30 MSK regular, 283-rd Codeforces round will take place. Problems are authored by me, Mikhail Tikhomirov. Maxim Akhmedov (Zlobober) helped me with discussing and preparing the problemset, Maria Belova (Delinur) translated problem statements in English, and Georgy Chebanov (gchebanov), Alexander Mashrabov (map) and Niyaz Nigmatullin (niyaznigmatul) tested the round and helped us with finding bugs and mistakes; let's give them a round of applause!

The round will be for both divisions. The scoring is standard (not dynamic); score distribution is as follows:

Div. 1: 750-1250-1250-2000-2500

Div. 2: 500-1000-1750-2250-2250

This is going to be my fourth round at Codeforces. I really hope it will go as good as three before it. =) Wish you all the best of luck!

UPD: the round is over, thanks for participating!

Grats to the winners:

Div. 1:

1. SirShokoladina

2. Petr

3. rowdark

4. anta

5. Marcin_smu

6. Merkurev

7. qwer1561

8. Ra16bit

9. kuviman

10. Um_nik

Div. 2:

1. SergeyMelnikov

2. sepehr103

3. StarCuriosity

4. dotato

5. husheyn

Editorial is here ( UPD: now in English!).

A new long challenge is up at Al Zimmerman's Programming Contests -- Delacorte Numbers. Find the description here. Neat prizes are announced for two best participants. You must register in order to compete.

The problem seems really cool, so I encourage you to try it, especially if you like TopCoder Marathon Matches or something like that.

I'll upload my example solutions and will post links to them as soon as it becomes possible.

Some of the problems editorials contain an additional challenge which is apparently harder to comprehend than the original problem. Feel free to share and discuss your ideas in the comments. =)

465A - inc ARG

If we add 1 to a number, its binary representation changes in a simple way: all the least significant 1's change to 0's, and the single following 0 changes to 1. It suffices to find the length of largest suffix which contains only 1's, suppose its length is l. Then the answer is l + 1 except for the case when all the string consists of 1, when the answer is l.

It is amusing that div1E problem is concerned with addition of 1 to a binary integer as well. =)

465B - Inbox (100500)

Optimal strategy is as follows: for every segment of consecutive 1's open the first letter in segment, scroll until the last letter in segment, if there are more unread letters left, return to list.

It is easy to show that we can not do any better: observe the moment we read the last letter from some segment of consecutive 1's. There are no adjacent unread letters now, so we either have to scroll to some read letter or return to list of letters, either way we make an operation which does not result in reading an unread letter, so every segment (except for the last) must yield at least one such operation.

464A - No to Palindromes!

If string s contains a non-trivial palindromic substring w, then it must contain palindromic substring of length 2 or 3 (for instance, center of w). Therefore the string is tolerable iff no adjacent symbols or symbols at distance 1 are equal.

Now for the lexicographically next tolerable string t. t is greater than s, so they have common prefix of some size (maybe zero) and the next symbol is greater in t than in s. This symbol should be as right as possible to obtain minimal possible t. For some position i we can try to increment s_i and ensure it's not equal to s_i - 1 or s_i - 2. If we find some way to do this, the suffix can always be filled correctly if only p ≥ 3, as at most two symbols are forbidden at every moment. Every symbol from suffix should be as small as possible not to make conflicts. So, a greedy procedure or some kind of clever brute-force can be implemented to solve the problem in O(n). Cases p = 1 or 2 are easy, as only strings of length at most 1, and at most 2 respectively fit.

This is an application on general approach to generate next lexicographical something: try to increment rightmost position so that suffix can be filled up in some way, then fill the suffix in least possible way.

As pointed out in Russian discussion, this problem is a simplified version of the problem from some previous round: 196D - The Next Good String. We were not aware of this and apologize for the misfortune. Luckily, no copied solutions from that problem were spotted. If you enjoyed this simple version, you may want to try the harder one know. =)

464B - Restore Cube

There are several ways to solve this problem. We'll describe the most straightforward one: we can generate all possible permutations of coordinates of every point and for every combination check whether given point configuration form a cube. However, number of configurations can go up to (3!)⁸ > 10⁶, so checking should work quite fast.

One way to check if the points form a cube is such: find minimal distance between all pairs of points, it should be equal to the side length l. Every vertex should have exactly three other points at distance l, and all three edges should be pairwise perpendicular. If these condition are met at every point, then configuration is a cube as there is no way to construct another configuration with these properties. This procedure performs roughly 8² operations for every check, which is fast enough. There are even more efficient ways of cube checking exploiting various properties of cube.

There are various optimizations to ensure you fit into time limit. For instance, applying the same permutation to coordinates of all points keeps every property of the cube, therefore we can fix order of coordinates for one point and permute all other. This single trick speeds up the algorithm 6 times, which allows some less efficient programs to be accepted.

A challenge: apparently, checking may be done as follows: find the length side l, then count number of pairs on distance l, , . A cube must contain exactly 12 pairs of first kind, 12 pairs of second kind and 4 pairs of third kind. Can you prove that this condition is sufficient for configuration to form a cube? Is it true if we allow points to have non-integer coordinates? Can you propose an even easier algorithm for checking?

464C - Substitutes in Number

It is quite diffcult to store the whole string after each query as its length grows exponentially and queries may change it dramatically. The good advice is: if you can't come up with a solution for a problem, try solving it from the other end. =)

Suppose we know for some sequence of queries that digit d will turn into string t_d for every digit. Then string s = d₁... d_n will turn into t_d1 + ... + t_dn (+ for concatenation). Denote v(s) numeric value of s. Then v(s) can be expressed as v(t_dn) + 10^|d_n|(v(t_dn - 1) + 10^{|d_n - 1|}(...)). So v(s) can be computed if we know m_d = v(t_d) and s_d = 10^|t_d| for all d. As we need answer modulo P = 10⁹ + 7 we can store these numbers modulo P.

Now prepend some new query d_i → t_i to given sequence. How will m_d and s_d change? Clearly, for all d ≠ d_i these numbers won't change, and for d_i they can be computed according to the rule above. This recounting is done in O(|t_i|) time. After adding all queries, find answer for s using the same procedure in O(|s|) time. Finally, our time complexity is . The code for this problem pretty much consists of the above formula, so implementation is as easy as it gets once you grasp the idea. =)

Optimized simple solutions which just replaced substrings could manage to pass pretests. Sorry for that.

A challenge: this problem has a natural modification when you have to give an answer after each query. Using algorithm described above it can be solved offline in O(n²) time. Can we do better than this? What if we are limited to answer online?

464D - World of Darkraft - 2

This problem required some skill at probabilities handling, but other than that it's quite simple too.

Denote number of earned coins as X, and number of earned coins from selling items of type i as X_i. Clearly X = X₁ + ... + X_k, and EX = EX₁ + ... + EX_k (here EX is expectation of X). As all types have equal probability of appearance, all X_i are equal, so EX = kEX₁. Now to find EX₁.

If we look only at the items of one type, say, 1, items generation looks like this: with probability we get nothing, and with probability we get out item with level distributed as usual. Denote d_n, t expectation of earned money after killing n monsters if we have an item of level t at the start. Clearly, d_0, t = 0 (we have no opportunity to earn any money), and , which is equal to = . To get the answer note that EX₁ = d_n, 1. The sad note is that this DP has Ω(n²) states, which is too much for .

Maybe if we cut off some extremely-low-probability cases we can do better? For instance, it is clear that probability of upgrading an item descreases with its level, so apparently it does not get very high. We know that expected number of tries before first happening of event with probability p in a series of similar independent events is 1 / p. Therefore, expected number of monsters we have to kill to get item of level T is . So, in common case our level can get up to about , which does not exceed 500 in our limitations. We would want to set such bound B that ignoring cases with t > B would not influence our answer too much. That can be done with rigorous bounding of variance of T and applying some bounding theorem, or with an empirical method: if we increase the bound and the answer doesn't visibly change, then this bound is fine. It turns out B ≥ 700 is good enough for achieving demanded precision. Thus solution with complexity is obtained (here we assert that , and constant C is buried in the big O).

A challenge: suppose we have the same rules of killing monsters and obtaining items, but now we are free to choose whether to sell a new item or an old one. We act so that to maximize our number of coins in the end. What is the expected number of coins if we act optimally?

Now it is sometimes more profitable to sell a powerful item, but sometimes it isn't. How fast a solution can you come up with?

464E - The Classic Problem

This seems to be a simple graph exercise, but the problem is with enormous weights of paths which we need to count and compare with absolute precision to get Dijkstra working. How do we do that?

The fact that every edge weight is a power of two gives an idea that we can store binary representation of path value as it doesn't change much after appending one edge. However, storing representations explicitly for all vertices is too costly: the total number of 1's in them can reach Ω(nd) (d is for maximal x_i), which doesn't fit into memory even with bit compression woodoo magic.

An advanced data structure is needed here which is efficient in both time and memory. The good choice is a persistent segment tree storing bit representation. Persistent segment tree is pretty much like the usual segment tree, except that when we want to change the state of some node we instead create a new node with links to children of old node. This way we have some sort of ''version control'' over tree: every old node is present and available for requests as its subtree can never change. Moreover, all queries are still processed in time, but can create up to new nodes.

What queries do we need? Adding 2^x to binary number can be implemented as finding nearest most significant 0 to x-th bit, setting it to 1 and assigning 0's to all the positions in between. Usual segment tree with lazy propagation can do it, so persistent tree is able to do it as well.

Comparing two numbers can be done as follows: find the most singificant bit which differs in two numbers, then number with 0 in this bit is smaller; if no bits differ, then numbers are clearly equal. That can be done in if we store hashes of some sort in every node and perform a parallel binary search on both trees. Time and memory limits were very generous so you could store as many different hashes as you wanted to avoid collisions.

That concludes the general idea. Now we use this implementation of numbers as a black-box for Dijkstra algorithm. Every operation on numbers is now slowed by a factor of , so our solution has complexity. However, great caution is needed to achieve a practical solution.

First of all, in clueless implementation comparison of two "numbers" may require additional memory as we must perform "push" operation as we descend. memory is too much to fit even in our generous ML. There are plenty of ways to avoid this, for instance, if we want to push the value from node to children, we actually know that the whole segment consists of equal values and can answer the query right away.

I would like to describe a clever trick which optimizes both time and memory greatly and also simplifies implementation. It allows to get rid of lazy propagation completely. Here it comes: initially build two trees containing only 0's and only 1's respectively. Now suppose we want to assign some value (0, for instance) on a segment and some tree node completely lies inside of query segment. Instead of creating a new node with a propagation mark, we can replace the node with corresponding node from tree filled with 0. This way only new nodes are created on every query (which is impossible to achieve with any kind of propagation which would require at least ), and also nodes need to store less information and become lighter this way. Also, no "push" procedure is required now.

No challenges for this problem as it is challenging enough itself. =) Implementing this problem is a great exercise for anyone who wants to become familiar with complicated structures and their applications, so solving it in the archive is advisable.

That's pretty much it. If there are still questions, you may ask them in the comments. Thanks for reading!

Hi all.

On Sunday, September 7, at 19:30 MSK regular, 265-th, Codeforces round will take place. Problems are prepared by me, Mikhail Tikhomirov. Round will be for both divisions.

Standard (not dynamic) scoring will be used for this round.

Div. 1: 500-1500-1500-2000-2500

Div. 2: 500-1000-1500-2500-2500

I would like to thank Gerald Agapov (Gerald) for his help in problems preparation, Filipp Rukhovich (DPR-pavlin) and Alexander Mashrabov (map) for round testing, Maria Belova (Delinur) for English statements and Mikhail Mirzayanov (MikeMirzayanov) for creation and development of Codeforces project.

This is going to be my third round on Codeforces, and I tried to make problems as interesting and diverse as possible. Hope you will enjoy this round. Best of luck! =)

UPD: round is over. Thanks for participating, hope you liked the problems.

Grats to all the winners:

Div. 1:

1. tourist
2. Petr
3. rng_58
4. al13n
5. ecnerwala
6. qwerty787788
7. marek.cygan
8. KADR
9. Merkurev
10. hos.lyric

Special respect goes to simonlindholm, the only participant to solve the hardest problem E!

Div. 2:

1. matthew99
2. acrrca
3. ccdream
4. Chameleon2460
5. newSolars

Editorial is here.

Hello everyone.

Recently I encountered a problem which included checking whether given graph is colorable using k colours. More specifically:

• graphs given are quite large (up to several thousands of vertices) but not very dense (average degree is about 10-20, max degree may be about 50).

• k is not too big (something up to 10).

• it is important to get a reliable answer (even one-sided error is not tolerated).

I stumbled upon a lib that is able to count the chromatic number of a graph (notable that it does quite well on average for that scale, still some instances take very long to treat). k-colorability checking sure is simpler than counting the chromatic number, so specialized solution for it is expected to do somewhat better; sadly I couldn't find any code or description of practical solution for this problem.

Do you have any experience with this particular problem or something related? What did you use and what results have you got? Any advice, useful links and relevant comments are also encouraged. Thanks.

Hi, Codeforces.

Could anybody kindly tell me something about fast calculating radius and/or diameter of non-weighted undirected graph (definitions can be found here) ? Fast = faster, than in O(MN) (breadth-first searches from each vertex). Any results are welcome: probabilistic, good in average, good for sparse graphs, etc. Thanks.

155A - I_love_\%username\%

You should do what is written: go through the sequence and count the elements which are greater or less than all of its predecessors. We don't even have to store the whole sequence, just the current minimum and maximum. Complexity — O(N), but squared still works fine.

155B - Combination

Clearly, we can play the cards with b_i > 0 first as each of them gives at least one extra move. After that, the number of extra moves left doesn't depend on the order of playing. The left cards all have b_i = 0, so we play those of them which have larger a_i. Simpler version of this solution: sort all the cards by decrease of b_i, if equal — by decrease of a_i, and then go through the sorted array from beginning to end, simulate the counter and sum up the points. Remember not to fall over the edge of array if the sum of b_i's is larger than the number of cards. Complexity — O(n log n) (or O(n^2), if using bubblesort, which is still accepted).

155C - Hometask

154A - Hometask

Constriction saying that no letter occurs in more than one forbidden pair lets us to use the greedy solution. Without the constriction the problem is quite hard.

Let's look at all occurences of letters from some pair. They form several continuous substrings divided by some other letters. We can note that in optimal solution the substrings cannot merge, 'cause we can leave at least one letter in each of such parts. So, for each of these substrings problem is solved independently. To resolve conflicts within a substring, one has to remove all letters of some kind, 'cause while there are letters of both kinds there will be conflicts. Clearly, from each continuous substring of forbidden letters we remove all letters of the kind which number is less than another.

The answer can be counted in O(kN) with k runs through the string.

155D - Colliders

154B - Colliders

The clueless solution ''store all the enabled numbers and compare each new number with each of them'' works too slow, as we can add all the prime numbers below n, number of which is O(n / log n).

We can note that for each number k > 1 at any time no more than one collider is turned on which number is divided by k. Let us store an array which has in k-th element the number of turned-on collider which is divided by k, on 0 if there is no such at the moment. To enable the collider with number q we can look over q's divisors and check whether all the array's elements with these numbers have 0's. If some of them has a positive integer, that's the number of collider we conflict with — we can just print it and go on. Otherwise, we have to put q into all the overlooked elements.

This works in O(M sqrt(N) + N). There's faster solution as we can store all of the above only for prime divisors. Total size of the prime divisors list for number from 1 to N is O(N log log N). Thus we have a solution with complexity O(N log log N + M log N), as the number of prime divisors of k doesn't exceed log k (exact upper bound — log k / log log k * (1 + o(1)).

155E - Double Profiles

154C - Double Profiles

We want to count the number of pairs of vertices in a undirected graph which neighbours' sets are equal up to these vertices. To count the pairs which sets of neighbours are equal we can hash these sets (for instance, count the polynomial hash of adjacency matrix row) and sort the hashes. Than we have to add the pairs of doubles which have an edge between them.

We can note that there are no more such pairs than there are edges in the graph. So we can iterate through edges and check hashes for equivalence considering the presence of the edge (in case of polynomial hash we just add some degrees to them and then compare them). Other solution was to count another version of the previous hash, now adding a loop to each vertex, and to count the number of pairs just like in the previous case.

Moreover, we could try and sort the whole lists of adjacencies (which previuosly should be sorted too). As their total size is 2M, this works fine too, but needs an accurate realization. Hash solution complexity — O(N log N + M).

154D - Flatland Fencing

As the moves choices are symmetrical for both players, if one player can reach another in one move from some disposition, the other player also can reach the first. So, if we are allowed to stand in one place (i.e. a <= 0 <= b), we can just stand still and wait for another player to come. If she wants to win, she will have to step within our reach before that so that we can get her. So, if the first player doesn't reach the second initially, there is a draw as no one can ensure her victory. Thus we finished the case a <= 0 <= b: either the first player wins in one move, or there is a draw.

Now, let a and b have the same sign. Denote d = x2 — x1. If a <= b < 0, we can go to the situation with (d, a, b) = (-d, -b, -a), which is similar to the initial. So later on 0 < a.

So we have the following game: there are integers d and 0 < a <= b. In one move each player can substract an arbitrary integer number from segment [a; b] from d. The player who gets d = 0 after her move wins. If at some point d < 0, a draw is proclaimed (as no one can win anymore).

The interesting case is d > 0. Note that if d mod (a + b) = 0, the second player can use the symmetrical strategy: for every first player's move x of she can make a move a + b — x, and support the condition d mod (a + b) = 0. As d decreases, the second player eventually moves to 0 and wins. So, if d mod (a + b) = 0, the second player wins. Thus, if d mod (a + b) is in [a; b], the first player wins, as he can reduce the game to the previous case by letting the second player move in the losing situation.

What about all the other situations? Turns out all the other position are draws. We prove that by induction: let d = k(a + b) + l, where l in [0; a + b). Case l = 0, as we just proved, is losing, cases l in [a; b] are winning. If l is in [1; a — 1], we cannot move to losing position (we use the induction assumption for lesser k), but after the move a, we move to the draw position (if k = 0, we move to the negative number, otherwise we get into [(k — 1)(a + b) + b + 1; k(a + b) — 1] segment, every position from which is a draw by assumption). Similarily for l = [b + 1; a + b — 1], move to a draw — b.

154E - Martian Colony

We have to find the area of intersection of all circles containing the given set of points (it's clear that the intersection has the least area, and we have an unlimited number of circles). First, what shape does such an intersection have? Its border contains some circle arcs of radius R meeting at some points of convex hull. If we determine which points are present in the border, we can count the total area as the sum of polygon area and several circle segments.

So, how to determine those points? It's clear that if there is a circle of radius R containing all the points and having some of them on its border, then this particular point is present in the border of the intersection. If we fix the circle and move it in some direction, it eventually will run into some point — so we can find at least one point. Then we can perform something similar to ''present wrapping'' — go around the convex hull and support the set of the border points while controlling the relative position of the arcs. While this solution is fast, it is very hard to write and it was not assumed that it should be written during the contest.

There is much simpler solution based on quite different idea. We build the convex hull of the set so that no three points lie on the same line. Let us take the very large R so that every point of convex hull is present in the intersection border. As we gradually decrease R, some points will start to disappear from the border. How to determine which point falls out first? For point u in the convex hull denote its left and right neighbours l(u) and r(u). It's clear, that the first point to disappear will be such point u which has the largest radius of circle going through u, l(u) and r(u) (when R becomes equal to this radius, two arcs will merge into one in point u, while all the other will have joints in them; we will call this radius critical for u). Then we remove u from convex hull and do not take it into account. We repeat while the largest critical radius is larger than R. The rest points will be exactly the points forming the border.

How to do this fast? Note that when we remove some point from the set the critical radii will change only for its two neighbours. Let us store a priority queue containing critical radii along with point numbers. On every iteration we extract the largest critical radius, remove the corresponding point from the set, and refresh the information about the neighbours in the queue. We repeat while the largest radius is greater than R. As we just simulate the process of R decreasing, everything works correctly. The complexity of this procedure is O(n log n), as we have no more than n iterations and on every iteration we perform the constant number of operations with the queue of size at most n.

There is an unclear case, when the border contains only two points. Then on the last phase we have three points in the set and the algorithm doesn't have a clue which one to remove as they have equal critical radii. But we know that the triangle with vertices in these points is obtuse-angled, as we cannot shrink the circumcircle of an acute-angle triangle, as that would contradict with the circle existence condition. So we have to remove the point with the obtuse angle.

Hello everyone. I'm Mikhail Tikhomirov and I'm the author of today round. I want to say big thanks to Gerald Agapov (Gerald) and Artem Rakhov (RAD) for great help in preparing this contest, and also Maria Belova for translating the statements into English (Delinur).

Today round is for contestants from both divisions. Each division has five problems, which intersect, as always. Score distributions are also standard (500-1000-1500-2000-2500). In short, it's a usual round. Or not?.. =)

Hope that problems will be interesting, tests will be secure, server will be fast, solutions — (mostly) correct, and the round will be rated. =) Wish you best of luck!

Round finished, thank you all for participating!

Results:

div1:

1. tourist
2. peter50216
3. Egor
4. YuukaKazami
5. gchebanov
6. kelvin
7. shangjingbo
8. rowdark
9. kterry
10. rng_58

div2:

1. jonathanasdf
2. Tranvick
3. ProForward
4. Eurekash
5. neex.emil

Editorial is finally up!

139A - Petr and Book

139B - Wallpaper

139C - Literature Lesson

138A - Literature Lesson

The hardest part is to check whether two lines rhyme or not.

We have to check the suffixes starting in K-th vowels from the ends for equality. Notice that if a line has less then K vowels, it can NOT be part of any rhyme (even with the identical string).

To check this we can use two pointers running from two ends simultaneously, or use some built-in functions for taking substrings (like s.substr(...) in C++).

Now, let us take three boolean variables: aabb, abab and abba. Each one says if every quatrain we have seen before satisfies the corresponding type of rhyme. To support them, for each new quatrain we must check for rhyming every pair of lines it and change variables if needed.

If at the end of the poem all variables are set to TRUE, then the type is aaaa. If all of them are FALSE's, then the answer is NO. Otherwise exactly on of them is TRUE, and answer is clear. 

Complexity - O(S), where S is the sum of all lines' sizes.

139D - Digits Permutations

138B - Digits Permutations

It turned out to be surprisingly hard, possibly because of lots of cases to think of.

How to determine the number of zeros at the end of the sum of two numbers? First we skip all the positions from the end where both numbers have zeros. If on the next position the sum of digits is not 10, that's it. If it is, we go on while the sum of digits is 9.

Now we take two transitions of digits in N. Let's fix the number of common zeros at the end of both transitions. If, moreover, we fix the digits that sum up to 10 at the next positions, we can find the maximal number of zeros to get with the remaining digits as min(a₀, b₉) + ... + min(a₉, b₀), where a₀, ..., a₉ are the quantities of every remaining digit in the first transition after taking out the last zeroes and the digit for the 10-sum, and b₀, ..., b₉ are the same numbers for second transition (initially these quantities are equal to quantities of digits in N).

So, if we store a₀, ..., a₉ and b₀, ..., b₉, and then run through the numbers of common zeros at the end and the 10-sum digits, we determine the maximal zeros number (and configuration giving that answer) in O(10 * 10 * N) = O(N) time. Getting the transitions now is easy - we build them from right to left according to the saved answer.

The most common mistake was to think that maximal number of zeros at the end gives the maximal answer. It was disproved by 4-th pretest - 1099. As we can see, the optimal configuration is 1901 + 1099, giving three zeros, which cannot be achieved by placing both zeros at the ends.

139E - Mushroom Gnomes - 2

138C - Mushroom Gnomes - 2

138D - World of Darkraft

138E - Hellish Constraints

Hello.

Today round is prepared by me. My name is Mikhail Tikhomirov, i am fourth grade student at mech.-math. dep. of MSU, also i work as developer-researcher at Yandex.

I want to thank Artem Rakhov (RAD) for valuable help and thoughtful coordination, Maria Belova (Delinur) for great-as-always translating statements into English, and alsoMikeMirzayanov for letting us all get together today. =)

Round will be for both divisions. Every division will have five problems as usual, some of them will be the same, some will be not.

Score distribution:

Div1: 500-1000-2000-2000-2500.

Div2: 500-1000-1500-2000-3000.

Today round is the last round in 2011. I want to thank Codeforces team, everyone who invented, prepared or helped in preparing problems this or past years, and those, who help developing the project. Codeforces now is not just a platform for programming competitions, it is a place where everyone can learn something from another, get a bit of knowledge from more experienced fellows, become more advanced by solving contests and trainings, or just enjoy cool and beautiful problems.

Let's wish the Codeforces project good luck in development next year and long years of existence.