Всем привет.

Сегодня, 13 июня в 10:00 MSK состоится третий и последний отборочный раунд Яндекс.Алгоритма 2016. Я являюсь автором всех задач этого раунда. Благодарю за помощь Ивана Gassa Казменко, Олега snarknews Христенко, и особенно Алексея Chmel_Tolstiy Толстикова и Максима Zlobober Ахмедова, которые внесли большой вклад в подготовку задач. Также благодарю сотрудников Яндекса, которые прорешивали раунд.

Желаю удачи!

UPD: раунд завершен! Поздравляем Um_nik, единственного, решившего все задачи!

Общую таблицу результатов отборочного этапа можно найти здесь. Поздравляем 25 лучших участников, прошедших в финал!

Разбор (пока что только на английском) можно найти тут

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 - Gena's Code

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 - Peter and Snow Blower

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 - Skills

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 - Necklace

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 - Kingdom and its Cities

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 - Puzzle Lover

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.)

There's always a problem to fall asleep after a late night (early morning) match, also drinking coffee during competition doesn't exactly help with that. So, here comes a rough write-up of div1 problems.

250 — MissingLCM

As one can verify easily using prime factorization theorem, the LCM of a set of numbers is , where α_p is the maximal power of p which divides some element of the set. Let us find largest p^t ≤ n for every prime p ≤ n; there should be a number in [n + 1;m] that divides p^t as well. Thus, ; there is a case when the new number divides some greater power of p, but we're fine with that. Find the greatest lower constraint for all p ≤ n. Use the Eratosphene's sieve to find all the primes. An O(n) solution is possible.

450 — ColorfulLineGraphs

Consider vertices from left to right. How many ways there are to place a new vertex along with an outcoming edge (if any)? There are k ways to place the vertex without an edge; if we choose the incoming vertex for the new edge, this excludes one color among possible options. Thus, if x vertices were already placed, there are exactly k + x(k - 1) ways to place a new vertex, possibly with an edge. The answer is simply the product k·(k + (k - 1))·(k + 2(k - 1))·.... It suffices to notices that M is rather small, and the product elements are looped modulo M, thus it is easy to find out how many times an element contributes to the product. Take care not to overflow int64. An solution is possible.

1000 — BridgeBuilding

Connecting two vertices with a zero-weight edge is effectively the same as merging the vertices into one; we will further go with this interpretation.

Call the parts of the graph between the merged vertices the havens (or whatever); a haven can be a loop or a pair of paths joined together. A loop haven can be represented by a pair of numbers (l, r) — the numbers of merged points in the original enumeration. Denote L_l, r (R_l, r) the largest distance from a vertex of (l, r)-haven to the merged vertex l (r), S_l, r the largest distance between any two vertices of (l, r)-haven, and D_l, r the distance between l and r (after merging each of them). All these numbers can be computed in O(n³) for all pairs (l, r) (use two pointers to compute S_l, r).

Suppose we have chosen pairs of vertices to merge; which pair of vertices can be farthest apart now? The farthest pair of vertices (u, v) can lie in the same haven, or in different havens. In the first case all pairs of vertices will be considered explicitly; in the second case the distance is equal to L + D₁ + ... + D_k + R, where L is the distance from u to the closest merged vertex, D₁, ..., D_k are distances between consecutive merged vertices inside a single haven, and R is the distance from the last merged vertex to v.

Binary search the diameter x. Compute dp_i, j with the following meaning: suppose we merged j pairs of vertices with last pair to merge having index i, we also took care that in the processed part no pair of vertices is at distance larger than x; than dp_i, j is the largest value of L + D₁ + ... + D_k such that the last merged vertex of D_k is the merged vertex i. Initialize dp_i, 1 with the two-paths havens, after that consider all possible options for the next vertex i; consider pairs of points in the current haven using S_l, r and all the rest using the DP value. Finally, to find the answer use such dp_i, k that the last two-paths haven does not have its vertices too far apart, and also dp_i, k + tail_i ≤ x, where tail_i is the largest distance from i to any of the ends. That makes for an solution, also probably a highly optimized O(n⁴) might pass.

Just a few quick notes about problems (not the full-sized editorial as usual).

A — Buildind a Bookshelf

Iterate over all possible lengths of top/floor l_t and walls l_w (note that they can be equal); reserve two planks of chosen lengths for each. If there are a_i planks of length l_i left, there should at least (be careful not to divide by zero of l_w = 1!) departments of width l_i. The number of inner walls is equal to the number of departments, except for the case when the total width of departments is equal to the width of the bookshelf (we don't need the last inner wall). Check if there are sufficient planks for inner walls, and also if the departments fit into the bookshelf; also, excessive inner walls should placed in the free space. That's an O(n³) solution; finally, notice that the floor should be longer than all the shelves, thus it makes sense to try only the two largest types of planks for the floor. Finally, O(n²).

B — Flatland Division

The most failed problem of the contest. Most accepted solutions are for this problem, I guess, due to a) it was in the beginning of the problemset, and b) this type of problem occurs frequently on many contests. I apologize for the low quality of the problem.

The idea is as follows: the dividing line can be moved so that is nearly passes throw some two cities. Iterate over the pair of these 'border' cities, and find the total population on both sides of the line; choose the best option. To speed up, fix one border city and rotate the line around it. there are O(n) events when a changes side respective to the line; sort them by angle and process iteratively. That makes up for an solution. I tried to make sure no O(n³) solutions pass, but it seems I failed even at that. =(

C — Solitaire Simplified

There is a straightforward O(n⁴) DP solution which basically stores all the interesting info about the state of the game; it can be probably optimized to O(n³). I will describe another, more thought-requiring solution.

Consider an inverse permutation of the deck; that is, if the i-th number of the deck is p_i, numbers q_i are determined by q_pi = i. The number 1 will be surely thrown out on the first discarded through the cards; the number will be discarded on the first pass if q₂ > q₁ or q₂ > q₃ > ... > q_n; and so on.

We see that on each pass through the cards maximal increasing prefix and maximal decreasing suffix of q will be discarded; on the next pass the new maximal monotonous prefix and suffix will be discarded and so on. Suppose there will be m passes through the deck, and the final number is k; this means that there are exactly m - 1 increases in q to the right of k, and exactly m - 1 drops (or, in other words, k - (m - 1) increases) to the left of k; thus the total number of increases will be k - 1 regardless of m. The problem reduced to a classic one: count the number of permutations of n number with exactly k - 1 increases. It can be done straightforwardly in O(n³), or even faster using some ingenious formulas.

D — Xor

Coming up.

E — Tree Growing

The information about the tree can be stored simply as a sequence of operations. The sizes of the tree after each operation will also be useful. The "+ k" is thus trivial.

Now to find the distance between two vertices. This can be divided into two tasks: finding depth (distance from the root) d(v) of the vertex v given its number, and determining depth of the LCA of two vertices; the distance is given by d(x) + d(y) - 2d(lca(x, y)).

If v = 1, the depth is clearly 0. Otherwise, the number of the subtree of the root which contains v is ⌊ (v - 1) / s, where s is the size of a single subtree. Similarly, the number of vertex v in the subtree in its original numeration is . We have reduced the problem to the similar one concerning the subtree; treat it recursively. The sequence of sizes provides all the necessary information; thus, the depth can be found in O(h), where h is the height of the tree.

To find LCA of x and y, proceed similarly; the root of the current tree if the LCA if one of x or y is the root, or they are contained in different subtrees. Thus, the depth of LCA can also be found in O(h).

Unfortunately, h can be rather large. However, there can be very few operations (less than 60) with k ≥ 2 as the total number of vertices is at most 10¹⁸. We can store the operations with k = 1 in compressed form, as they just attach one edge to the root of tree. Finally, all the operations with little enhancement can be done in O(h'), where h' is the number of operations with k > 1.

F — To Saw Or Not To Saw

If a = c, the answer is simply min(b, d) (the shortest sawtooth length).

Otherwise, suppose a > c. Consider the space between two sawtooths of (c, d)-saws; we may as well consider the (a, b)-saw wrapped up around the space. The ends of the sawtooths of (a, b)-saw form a modular sequence , which is the same set of ends as the periodical sequence with diffence ; thus the (a, b)-saw can be changed to the saw with difference but the same angle of sawtooths. Finally, we arrive at the previous situation with the common difference of ; the saw with the least steep angle of sawtooth will determine the maximal length. Thus, the answer is . Do not forget to use 64-bit integers for multiplication.

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 - Cutting Banner

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 - Quasi Binary

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 - Tourist's Notes

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 - Weird Chess

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 - Demiurges Play Again

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 - A Heap of Heaps

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 - Berserk Robot

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 - Summer Dichotomy

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!

Привет, Codeforces!

В воскресенье, 26-го апреля в 19:00 MSK состоится 300-ый регулярный раунд Codeforces.

Я поздравляю всех членов и администрацию Codeforces с этой замечательной цифрой. С момента создания платформа стала гораздо больше и круче, провела множество соревнований и предоставила возможность любому интересующемуся человеку прокачаться в знании алгоритмов и решении сложных задач. За это мы благодарим создателя платформы Codeforces MikeMirzayanov и всю команду Codeforces. Жгите дальше!

Я рад объявить, что задачи трехсотого юбилейного раунда составил я, Михаил Тихомиров (Endagorion). Возможно, вы помните прошлые раунды на моих задачах: #99, #109, #265, #283 и (частично) #295. Хочу поблагодарить координатора задач Codeforces Макса Ахмедова (Zlobober) за помощь в подготовке этого раунда и Марии Беловой (Delinur) за перевод условия на английский. Отдельное спасибо Владиславу Исенбаеву (winger), Александру Фетисову (AlexFetisov) и Павлу Кунявскому (PavelKunyavskiy) за тестирование задач и помощь в подготовке.

Раунд будет общим для обоих дивизионов и продлится два с половиной часа (как видно на странице Соревнования). В раунде будет несколько ( ≥ 6) задач, разнообразных по сложности и направленности. Надеюсь, каждый найдет задачу как раз для себя! Разбалловка будет объявлена позже.

В раунде будет разыграно 30 эксклюзивных футболок Codeforces. Футболки получат первые 15 участников по результатам раунда; кроме этого, среди остальных участников, вошедших в первые 300, мы выберем 15 случайным образом и наградим их тоже. Так что даже если вы слабо верите в то, что попадете в число самых лучших, ваши шансы на получение слонов все равно не так уж и плохи. =)

Такие дела. Приходите посоревноваться ради призов и ради удовольствия!

UPD: в контесте будет 8 задач. Разбалловка стандартная (не динамическая): 500-1000-1500-1500-2000-2500-3000-3000.

UPD2. Для определения людей, получающих футболки, будет использован следующий код на python3.4, который вы можете самостоятельно запустить во вкладке "запуск" на Codeforces. В качестве сида для инициализации генератора случайных чисел используется число, которое будет равно номеру последнего сданного во время контеста решения.

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: Спасибо за участие!

Поздравляем победителей:

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

Список мест, которые выигрывают футболки: 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. Вот счастливчики, занявшие эти места: bmerry, Egor, Petr, rng_58, scott_wu, jqdai0815, eatmore, atetubou, qwerty787788, niyaznigmatul, gs12117, W4yneb0t, JoeyWheeler, zxqfl, yeputons, kcm1700 & HYPERHYPERHYPERCUBELOVER (поделили 40-е место, поэтому каждый получает по футболке), piob, Leo_Yu, matrix & Nerevar (поделили 75-ое место), Haghani, ACube, DemiGuo, etal, Emarci15, hlwt, Salvare001, dzy97, FatalEagle, gchebanov & Jimanbanashi (поделили 243-е место) и Solaris (пишите мне, если найдете ошибки). Поздравляем!

UPD4: и наконец-то появился разбор (пока что только на английском, перевод будет позже).

Somehow I don't feel sleepy at all at 6am, which is kinda weird. I wonder if writing an editorial will help.

SquareScores (250)

The standard trick is to use the linearity of expectation: for every substring count the probability that it consists of the same characters, and sums all these probabilities. There are O(n²) substrings, which is a reasonable amount in the given limitations. However, iterating over all symbols in the substring yields O(n³) solution, so we should optimize something.

My way was as follows: fix the beginning of the substring, and process all substrings with this beginning altogether. Count q_c — the probability that current substring consists only of characters c. If we append one symbol from the right, q_c changes in a simple way: if the symbol is a letter x, then all q_c with c ≠ x become zeros, while q_x does not change; else, if the symbol is question mark, every q_c gets multiplies by p_c. So, we process all substrings with fixed beginning in O(mn) (where m is the number of different symbols), for a O(mn²) solution.

Do you have a more effective/simple solution for this problem?

SuccessiveSubstraction (450)

When we open all the brackets, every number adds up with a plus or a minus sign by it. Which configurations are possible? It is not difficult to prove that all possible configurations are as follows: the first number is always a plus, the second is always a minus, while all other numbers with a plus sign form no more than two consecutive segments. So, we just have to find two subsegments of the array with the greatest total sum. There are lots of ways to do it in O(n), the most straightforward (IMO) being DP (how many elements are processed; the number of consecutive segments already closed; is a segment currently open). Simply recalculate the DP after every change in the array, for a solution of O(n²) complexity.

TwoEntrances (850)

What if there is only one entrance in the tree? The problem becomes a classic one: count the number of topological orderings of rooted tree with edges directed from the root. There is a simple subtree DP solution; also, a closed formula is available: , where n is the total number of vertices, w(v) is the number of vertices in the subtree of v.

Now, two entrances s₁ and s₂ are present. Consider vertices that lie on the path connecting s₁ and s₂ in a tree; every vertex of the path can be associated with a subtree consisting of vertices not on the path. The last vertex to cover will be either s₁ or s₂ (WLOG, assume it's s₁), the second-to-last will be either s₂ or the neighbour of s₁ in the path, etc. The observation is that at any moment there is a consecutive subsegment of the s₁-s₂ path which is covered.

Count dp_l, r — the number of ways to cover the subsegment from l-th to r-th vertex in the path with all the hanging subtrees. The number of ways such that the l-th vertex is the last to cover is , where ord_l is the number of topological orderings of the subtree of l-th vertex (which can be calculated as described above), t_l is the size of this subtree, and T_l, r is the total number of vertices in the subtrees of l-th, ..., r-th vertices. The intuition behind this formula is that we independently deal with the segment [l + 1;r] and the l-th subtree, and the last vertex is always the l-th vertex of the path. The number of ways that cover r-th vertex in the last place is obtained symmetrically; dp_l, r is simply the sum of those two quantities. The base of DP is clearly dp_l, l = ord_l.

Clearly, this subsegment DP is calculated in O(n²), with all the preliminaries being simple DFS'es and combinatorial primitives which also can be done in O(n²).

Мы хотели бы также поблагодарить тестеров задач этого раунда и олимпиады ЗКШ: alger95, thefacetakt, adamant, -imc-, riskingh, ASverdlov.

Пожалуйста, пишите в комментариях о найденных ошибках.

UPD: я вспомнил, что забыл написать регулярные бонусные челленджи. Так что вот, пожалуйста.

520A - Панграмма

Идея:Endagorion

Подготовка:Endagorion

Чтобы проверить, что все буквы присутствуют, заведем массив длины 26 и для каждой буквы поставим в соответствующую ячейку единичку. В конце надо проверить, что все 26 единичек на месте. Решение работает за O(n). Также надо не забыть перевести все буквы к нижнему регистру (или наоборот, все буквы к верхнему).

Чтобы перевести буквы в нижний регистр, можно использовать встроенные функции, например, tolower в Python. Также можно пользоваться тем, что буквы от a до z идут подряд по их ASCII-номерам; ASCII-номер для символа можно получить при помощи ord(c) во многих языках. Теперь, чтобы получить номер буквы в алфавите, надо написать ord(c) - ord('a'), а на C++ или C просто c - 'a' (поскольку в C/C++ символ — это число, равное его ASCII-номеру). Также, например, чтобы проверить, что буква имеет нижний регистр, надо написать неравенство ord('a') <= ord(c) && ord(c) <= ord('z').

Challenge: сколько существует различных панграмм длины n? Строки, отличающиеся капитализацией некоторых символов, считаются различными. Сможете ли вы придумать линейное по времени решение?

520B - Две кнопки

Идея: Endagorion

Подготовка: Endagorion

Самое простое решение — просто запустить обход в ширину. Построим граф, в котором вершины — числа, а ребра ведут из одного числа в другое, если можно получить второе из первого за одну операцию. Можно заметить, что первое число никогда не выгодно делать больше, чем 2m, поэтому в графе будет не больше 2·10⁴ вершин и 4·10⁴ ребер, и BFS сработает очень быстро.

Однако, есть решение гораздо быстрее. Развернем задачу: изначально у нас есть число m, и мы хотим получить число n, пользуясь операциями "прибавить к числу 1" и "поделить число на 2, если оно четно".

Пускай мы в какой-то момент применили две операции типа 1, и потом операцию типа 2; но эти три операции можно заменить на две: сначала операция типа 2, а потом одна операция типа 1, и количество операций от этого уменьшится. Отсюда следует, что применять больше одной операции типа 1 имеет смысл только тогда, когда операций типа 2 больше не будет, то есть, когда n меньше m и осталось сделать несколько прибавлений, чтобы их сравнять. На самом деле, теперь существует ровно одна последовательность операций, удовлетворяющая таким требованиям: если n меньше m, прибавляем единички пока нужно, иначе если n четно, делим на 2, а если нечетно, прибавляем 1 и потом делим на 2. Количество операций в такой последовательности можно найти за время .

Challenge: рассмотрим обобщенную задачу: мы хотим получить число n из числа m с помощью операций двух типов "отнять a" и "умножить на b". Обобщите решение исходной задачи и научитесь находить минимальное количество операций за время в случае, если a и b взаимно просты. Справитесь ли вы, если у a и b могут быть нетривиальные общие делители?

520C - Выравнивание ДНК/521A - Выравнивание ДНК

Идея: Endagorion

Подготовка: Endagorion

Что это за функция — ρ(s, t)? Для каждого символа t и каждого символа s существует ровно один циклический сдвиг, который их совмещает (действительно, после 0, ..., n - 1 сдвигов символ t пробежит все возможные положения в строке, и ровно одно из них — это положение символа из s); поэтому, существует ровно n способов циклически сдвинуть s и t, при которых выбранные символы совместятся (поскольку ситуация симметрична для любого положения символа из s). Таким образом, вклад в ρ, который дает символ t_i, равен n × (количество символов s, равных t_i). Поэтому ρ(s, t) максимально, когда каждый символ t встречается в s наибольшее количество раз. Посчитаем для каждого символа количество вхождений в s; ответ равен Kⁿ, где K — это количество типов символов, которые встречаются в s чаще всего. Решение за O(n).

Challenge: мы знаем, что ρ_max(s) = C(s)·n², где C(s)--- максимальное количество вхождений какого-либо символа. Сколько существует строк s длины n над алфавитом размера k, таких что C(s) = m? Сможете придумать решение за время O(kn²)? За время ? За время ? Может быть, еще быстрее? (Подсказка: для быстрого решения необходим удачно подобранный простой модуль. =))

520D - Кубики/521B - Кубики

Идея: savinov

Подготовка: savinov, sokian, zemen

В эквивалентной формулировке, первый игрок стремится максимизировать лексикографиский порядок последовательности кубиков, а второй игрок — минимизировать его. Поэтому, на каждом шагу первый игрок берет максимальный из доступных кубиков, а второй — минимальный.

Сперва научимся проверять, можно ли в текущей ситуации взять некоторый кубик. Его нельзя взять только тогда, когда есть какой-то кубик, который на нем "стоит" (т.е. имеет координаты (x - 1, y + 1), (x, y + 1) или (x + 1, y + 1)), и наш кубик является единственным, на котором он стоит. Это условие можно явно проверить. Из-за больших координат это не получится сделать путем простых обращений к массиву, поэтому придется завести ассоциативный массив, например, в C++ можно воспользоваться set.

Теперь надо научиться находить максимальный/минимальный кубик среди доступных. Просто линейный проход — это слишком долго, поэтому заведем еще одну структуру, в которой будем хранить номера доступных кубиков. Структура должна уметь добавлять, удалять, а также искать максимум/минимум, так что что-нибудь вроде set нам снова подойдет.

После того, как ход сделан, какие-то кубики могли стать доступными или, наоборот, перестать быть доступными. Однако, после каждого хода состояние могло поменяться только для O(1) кубиков: кубики (x ± 1, y) и (x ± 2, y) могли стать недоступными, потому что какой-то из кубиков выше стал опасным (т.е., остался один кубик, на котором он держится), и еще какие-то из кубиков (x - 1, y - 1), (x, y - 1) и (x + 1, y - 1) могли сделаться доступными, потому что единственный опасный кубик, который на них стоял, был удален. В любом случае, для всех них надо просто заново сделать проверку, и про случаи можно особо не думать.

Решение с подходящей структурой работает за .

Challenge (по мотивам вопросов от jk_qq и RetiredAmrMahmoud): пусть теперь кубики выкладываются в ряд справа налево, т.е. от младших разрядов к старшим. Первый игрок все так же хочет максимизировать итоговое число, второй — минимизировать его. Если оставить правила убирания кубиков такими же, в общем случае задача не выглядит решаемой. Попробуйте решить новую задачу в случае, когда кубики выстроены в несколько независимых башен, т.е. кубик можно убрать, если он находится на вершине своей башни.

520E - Сплошные плюсы/521C - Сплошные плюсы

Идея: Endagorion

Подготовка: gchebanov, DPR-pavlin

Рассмотрим какой-нибудь способ расставить плюсы, а также какую-то цифру d_i (цифры пронумеруем с нуля слева направо). Эта цифра дает вклад в сумму чисел, равный d_i·10^l, где l — расстояние до ближайшего плюса справа или до конца строки, если справа нет плюсов. Если просуммировать эти значения по всем цифрам и по всем способам расставить плюсы, получим в точности ответ.

Сколько существует способов расставить плюсы для выбранной цифры d_i и какого-то фиксированного l? Во-первых, рассмотрим случай, когда при разбиении по плюсам часть, содержащая цифру d_i, не является последней, т.е., i + l < n - 1. Всего существует n - 1 позиция, куда можно ставить плюсы; ограничение, связанное с цифрой d_i и расстоянием l, означает, что после цифр d_i, ..., d_{i + l - 1} плюсов не стоит, а после цифры d_i + l плюс стоит. Иными словами, строка выглядит примерно так:

На рисунке точка означает отсутствие плюса, а вопросик значит, что неважно, стоит там плюс или нет. Видно, что из n - 1 возможных позиций для плюсов состояния (l + 1)-ой позиции определены, и среди них использован только один плюс. Это значит, что в остальные (n - 1) - (l + 1) = n - l - 2 надо поставить k - 1 плюс любым из способов; значит, искомое количество способов равно . Рассуждая схожим образом, получим, что если цифра d_i входит в последнюю часть (т.е. i + l = n - 1), количество способов равно .

В итоге получаем, что ответ равен

Преобразуем:

Чтобы посчитать такие суммы, нам надо предпосчитать все степени 10 до n-ой (по модулю 10⁹ + 7), а также биномиальные коэффициенты. Чтобы их посчитать, вспомним, что , поэтому достаточно вычислить все k! для k вплоть до n, а также их обратные значения по модулю. Помимо этого, нам пригодится массив префиксных сумм для цифр d_i, т.е., значения . Осталось просто просуммировать произведения этих величин.

В итоге получили решение за , поскольку стандартные алгоритмы для поиска обратных по модулю (а именно, малая теорема Ферма с бинарным возведением в степень и решение диофантова уравнения при помощи обобщенного алгоритма Евклида) имеют верхнюю оценку сложности . Однако, можно воспользоваться интересным трюком и вычислить все обратные элементы для первых n чисел за линейное время, после чего итоговоая сложность решения становится O(n); почитать про интересный трюк можно в комментарии от Kaban-5 (непонятно, почему он заминусован; может быть, кто-то вспомнит ссылку на более фундаментальный источник для этого метода?).

Challenge: теперь мы хотим посчитать сумму всех выражений, в которых расставлено k плюсов для всех k от a до b; т.е. мы хотим просуммировать ответы для исходной задачи по всем k = a, ..., b. Числа a и b любые, такие что 0 ≤ a ≤ b ≤ n - 1. Решение за O(n²) очевидно: для каждого k посчитаем ответ отдельно. Сможете ли вы придумать решение за линейное время?

521D - Магазин

Идея: Endagorion

Подготовка: gchebanov

Пусть у нас есть только умножения. Тогда нам даже не важно, в каком порядке их применять, надо просто брать несколько апгрейдов с максимальным b_i.

Теперь рассмотрим также прибавления, а про умножения временно забудем. Ясно, что для каждого скилла надо взять несколько максимальных прибавлений (возможно, ни одного). Для каждого скилла отсортируем прибавления по невозрастанию b_i; теперь для каждого скилла надо взять несколько первых апгрейдов. Итак, теперь для выбранного скилла есть невозрастающая последовательность прибавлений b₁, ..., b_l, и начальное значение скилла равно какому-то a. Раз мы решили взять некоторый префикс массива b, это значит, что когда мы берем апгрейд b_i, значение скилла увеличивается с a + b₁ + ... + b_i - 1 до a + b₁ + ... + b_i - 1 + b_i. Иными словами, значение, на которое домножится значение скилла (а значит, и все произвдение значений скиллов), равно дроби . Теперь, когда это отношение однозначно определилось для каждого прибавления, мы можем считать любое прибавление умножением. =) Теперь посчитаем такие отношения для всех прибавлений (т.е., отсортируем b-шки для каждого скилла по отдельности и найдем значения всех дробей), и затем посортируем умножения и прибавления вместе по тому, во сколько раз они увеличивают итоговый ответ. Ясно, что все умножения надо использовать уже после того, как были сделаны все прибавления; иными словами, для определения того, какие апгрейды брать, мы сортируем их все вместе по их отношениям, но реальный порядок применения должен быть таким: сперва все прибавления, а потом все умножения.

Наконец, разберемся с присваиваниями. Очевидно, что для каждого скилла имеет смысл делать не более одного присваивания, и использовать можно только максимальное присваивание для данного скилла. Кроме того, присваивание необходимо делать перед всеми прибавлениями и умножениями. Поэтому, для каждого скилла надо просто определиться, берем мы для него максимальное присваивание или нет. Однако есть проблема с тем, что когда мы сделали присваивание, отношения для прибавлений стали неправильными, поскольку стартовое значение a поменялось.

Представим теперь, что мы уже выбрали, какие прибавления мы сделаем, и теперь решаем, брать присваивание или нет. Если мы берем присваивание, то итоговое значение скилла поменяется с a + b₁ + ... + b_k на b + b₁ + ... + b_k. Иными словами, присваивание работает примерно так же, как и прибавление значения b - a. Единственная разница в том, что присваивание необходимо ставить раньше всех прибавлений.

Итак, переделаем все максимальные присваивания для каждого скилла в прибавления b - a и обработаем их вместе со всеми остальными присваиваниями (которые, как мы знаем, в итоге станут умножениями =)).

В итоге, задача свелась к сортировке отношений для всех апгрейдов. Оценим, какие числа у нас будут стоять в дробях. Отношение для умножения — это целое число до 10⁶; отношение для прибавления — это дробь, которая выглядит как . Поскольку k может быть порядка 10⁵, а b_i — порядка 10⁶, числитель и знаменатель дроби могут быть порядка 10¹¹. Когда мы сравниваем дроби и , мы сравниваем произведения ad и bc, которые по нашим оценкам могут быть порядка 10²². Это, к сожалению, приводит к переполнению встроенных целочисленных типов во многих языках. Чтобы разобраться с этой проблемой, вычтем из всех дробей единицу (очевидно, на порядок сортировки это не повлияет), и теперь отношения для прибавлений выглядят как . Теперь, числитель стал всего лишь порядка 10⁶, произведения будут порядка 10¹⁷, что уже помещается в стандартный 64-битный тип в любом языке.

Challenge: пускай нам надо сравнить две дроби и , где числа a, b, c, d могут быть порядка 10¹⁸. Каким способом вы бы это сделали? Сможете ли вы придумать простое решение, которое не использует длинную арифметику, вещественные числа или волшебные целочисленные типы, такие как __int128 и им подобные (однако, возможно, совершает неконстантное число операций)?

521E - Cycling City

Идея: Endagorion

Подготовка: Endagorion

Нам нужно найти в неориентированном графе две вершины, такие что их можно соединить тремя вершинно и реберно непересекающимися путями. Это легко решалось бы потоком, если бы не большие ограничения.

Во-первых, заметим, что все пути между двумя выбранными вершинами должны проходить внутри одной двусвязной компоненты графа. Действительно, любой простой цикл должен целиком лежать внутри одной двусвязной компоненты, а набор из трех путей можно представить как объединение двух пересекающихся циклов. Поэтому, сперва выделим все двусвязные компоненты графа и попытаемся решить задачу независимо в каждой из них. Двусвязные компонентны можно найти за линейное время; хороший алгоритм, который это делает, можно найти в статье по ссылке выше.

Теперь, у нас есть двусвязная компонента и та же самая задача. Во-первых, найдем любой цикл в этой компоненте обычным DFS'ом; единственный случай, когда цикл не найдется, — это когда компонента состоит из одного ребра, но это неинтересный случай. Теперь, предположим, что ни из какой вершины цикла не исходит ребра, которое бы не лежало в цикле; в этом случае цикл не связан ни с какой другой вершиной компоненты, поэтому компонента сама по себе является этим циклом; очевидно, что в этом случае решения также нет.

В противном случае, возьмем вершину v, из которой исходит ребро e, не лежащее в выбранном цикле (обозначим цикл за c). Если мы сможем найти такой путь p, который начинался бы с ребра e и заканчивался в какой-то вершине из цикла u (отличной от v), мы сможем выделить три непересекающихся пути между u и v: один из них — это p, а два других — половинки исходного цикла. Чтобы найти путь p, запустим DFS, который начинается с ребра e и заканчивается, как только мы приходим в вершину цикла c, отличную от v, а потом восстанавливает все пути для ответа.

Что же делать, если такого пути p не найдется? Обозначим за C компоненту, которую обошел этот DFS. У него не получилось найти пути между вершинами из множества C\ {v} и множества c\ {v}, поэтому любой путь между этими двумя множествами должен проходить через v. Но тогда оказывается, что если удалить v, компонента C\ {v} оказывается отделена от вершин из множества c\ {v}, что противоречит тому, что исходная компонента была двусвязной. Отсюда следует, что тот DFS, который мы запускали из e, всегда найдет подходящий путь p и получит ответ, если наша двусвязная компонента — не цикл и не отдельное ребро.

В итоге мы пришли к тому, что ответа нет в единственном случае, когда все двусвязные компоненты — либо отдельные ребра, либо циклы; другими словами, когда граф является несвязным набором кактусов. В противном случае, за пару запусков DFS'ов мы сможем найти три непересекающихся пути. В итоге получилось решение за время O(n + m); для упрощения можно было бы где-нибудь накрутить парочку логарифмов.

Challenge: сколько существует графов G, таких что в G можно выбрать две вершины, соединенные тремя непересекающимися путями? (Подсказка: мы знаем, что достаточно посчитать количество несвязных объединений кактусов.) Можете ли вы придумать какое-нибудь полиномиальное по времени решение? Решение за время O(n³)? Возможно, еще быстрее?

Привет, Codeforces!

2 марта в 10:00 MSK состоится раунд #295 для участников из обоих дивизионов.

Раунд состоится практически одновременно с олимпиадой Зимней Компьютерной Школы на схожем комплекте задач. Авторы задач — я (Endagorion) и Евгений Савинов (savinov). В подготовке задач принимали участие члены технического комитета Зимней Компьютерной школы: Георгий Чебанов (gchebanov), Филипп Рухович (DPR-pavlin), Александр Машрабов (map), Сергей Киян (sokian), Константин Семенов (zemen), Кинан Альсармини (Sarkin).

Спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский язык, Михаилу Мирзаянову (MikeMirzayanov) за вклад в развитие программирования путем создания систем Codeforces и Polygon.

Разбалловка в обоих дивизионах стандартная: 500-1000-1500-2000-2500.

Обратите внимание, что поскольку олимпиада ЗКШ на похожих задачах заканчивается позже раунда Codeforces, мы просим вас не обсуждать в комментариях задачи и решения до 14:10 MSK сегодняшнего дня. Также до этого времени будет закрыт просмотр кода других участников. Разбор также появится после этого времени.

UPD: все, можно обсуждать. =)

UPD2: наконец появился разбор ( теперь и на русском!).

Также поздравляем победителей в Div.1:

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

Отдельно поздравляем Petr и rng_58, решивших самую сложную задачу E!

К каждой задаче присутствует challenge — бонусная задача на тему, которую можно порешать just for fun и обсудить в комментариях. =)

496A - Минимальная сложность

Переберем все элементы, которые можем выкинуть, пройдем по оставшимся элементам и посчитаем максимальную разность среди соседних. Это решение имеет сложность O(n²). Можно заметить, что при удалении элемента ответ либо не поменялся, либо стал равен разности тех элементов, которые являлись соседями только что удаленного, поэтому ответ можно получить за O(1), а итоговое решение будет иметь сложность O(n). Ограничения позволяли сдать любое из этих решений или даже менее эффективное.

Challenge: пусть мы удаляем не один элемент, а k любых элементов (первый и последний, как и раньше, удалять нельзя). Какую минимальную максимальную разность между соседними элементами мы можем получить? Решите задачу в ограничениях 1 ≤ k ≤ n - 2, n ≤ 10⁵, a_i ≤ 10⁹.

496B - Секретный код

Заметим, что нам неважно, в каком порядке применяются операции: мы можем сперва выполнить все сдвиги, а затем все прибавления. После n сдвигов мы получаем исходную последовательность, поэтому достаточно рассмотреть только варианты, где сдвиги выполняются менее n раз. Аналогично, после десяти прибавлений единицы ко всем цифрам получим исходную последовательность, поэтому рассмотрим только варианты, где прибавления выполняются менее десяти раз. Для каждого из 10n вариантов определим результат применения всех операций; сохраним лучший результат и для каждого из вариантов сравним с лучшим. Сравнения осуществляются за O(n) операций, поэтому итоговое количество элементарных операций имеет порядок 10n². От константы 10 можно избавиться, если заметить, что при фиксированном сдвиге первую цифру всегда выгодно сделать нулем, и это однозначно определяет количество прибавлений; однако, чтобы сдать задачу, эта оптимизация не требовалась.

Challenge: можете ли вы решить задачу за время ? O(n)?

496C - Удаление столбцов/497A - Удаление столбцов

Посмотрим на первый столбец таблицы. Если буквы в нем не упорядочены по алфавиту сверху вниз, его нельзя оставить ни в каком корректном варианте оставить некоторые столбцы. С другой стороны, пусть буквы в первом столбце упорядочены, но в ответ мы его не взяли. Добавим его к ответу; несложно видеть, что в новом варианте оставить столбцы все строки также упорядочены сверху вниз по алфавиту.

Будем рассматривать столбцы слева направо. Если мы попробовали добавить текущий столбец к ответу и лексикографический порядок строк где-то нарушился, мы обязаны его удалить; если же все в порядке, возьмем его в ответ. Рассуждение, аналогичное предыдущему абзацу, показывает, что такой жадный алгоритм приводит к оптимальному (и более того, единственному среди оптимальных) ответу. Итоговая сложность — O(n²).

Challenge: сколько существует таблиц n × m, для которых ответ на эту задачу равен k? Придумайте как можно более оптимальное решение.

496D - Игра в теннис/497B - Игра в теннис

Фиксируем t; теперь мы можем проэмулировать ход партии и убедиться, что запись является корректной, а также определить соответствующее s; выведем все подходящие пары s и t. Такое решение работает за O(n²), попробуем его соптимизировать.

Если после окончания очередного сета мы обработали k розыгрышей, то позицию окончания следующего сета можно определить так: найти t-ую позицию после k-ой, в которой записано 1, аналогично, найдем t-ую позицию, содержащую 2. Если позиция t-ой единицы встретилась раньше, то следующий сет выигрывает первый игрок, и позиция окончания сета совпадает с позицией t-ой единицы; аналогично разбирается случай, если раньше идет t-ая двойка. Если партия еще не кончилась, но в оставшейся части и единиц, и двоек менее t, то запись некорректна. Позицию t-ой единицы или двойки после заданной позиции можно определять за бинпоиском, или за O(1) при помощи предподсчитанного массива позиций.

Теперь заметим, что для данного t партия из n розыгрышей не может содержать больше n / t сетов, поскольку каждый из них содержит как минимум t розыгрышей. Если мы просуммируем количество сетов в партии по всем возможным t, мы получим не более (известная сумма гармонического ряда). В зависимости от способа обработки одного сета итоговая сложность составляет либо ; любой из этих способов с запасом укладывается в ограничение.

Очевидно, что для каждого t существует не более одного варианта s; однако, для данного s может существовать более одного варианта t. Первый тест с таким случаем — претест 12. В условии требуется выводить ответ в лексикографическом порядке пар; здесь легко допустить ошибку и вывести пары с равными s по убыванию t (если в конце просто переворачивать массив).

Challenge: при подготовке этой задачи я столкнулся с тем, что не могу построить тест с большим количеством пар в ответе; в тестах к задаче максимальное количество — 128 = количество делителей числа 83160. Сможете ли вы побить этот рекорд? Хвастайтесь в комментариях, сколько пар вы умеете получать при n ≤ 10⁵; если у вас есть соображения, как оценить максимальное количество пар теоретически, тоже прошу делиться.

496E - Распределение партий/497C - Распределение партий

Отсортируем все партии и всех актеров вместе по возрастанию нижней границы (при равенстве сначала идут все актеры, потом все партии); пойдем в этом порядке по возрастанию нижней границы. Будем поддерживать множество актеров, которые уже <<начались>>, т.е. встретились в этом порядке раньше; если мы встретили актера, добавим его в это множество. Если мы встретили партию (a_j, b_j), из множества допустимых актеров нам нужно выбрать такого, у которого d_i ≥ b_j (требование c_i ≤ a_j гарантируется тем, что i-ый актер встретился раньше, чем j-ая партия); если таких актеров в множестве нет, мы не можем получить ответ. Если таких актеров несколько, нам выгоднее брать того из них, у которого d_i минимально (интуитивно, он нам в дальнейшем меньше пригодится). Сопоставим текущую партию выбранному актеру и уменьшим его k_i на единицу; если теперь k_i = 0, мы больше не можем пользоваться этим актером и должны выкинуть его из множества.

Чтобы уложиться в ограничения, множество текущих актеров приходится поддерживать в эффективной структуре данных (например, std::set или декартово дерево). Сложность итогового решения .

Challenge: пусть каждая песня присутствует в количестве q_j (1 ≤ q_j ≤ 10⁹), и каждой копии надо сопоставить своего актера. можете ли вы решить задачу в тех же ограничениях (поскольку ответ теперь очень большой, достаточно проверить его существование)?

497D - Шестерни

Если в какой-то момент произошло столкновение, это значит, что какая-то вершина одного из многоугольников попала на одну из сторон другого многоугольника. Рассмотрим систему отсчета, в которой многоугольник A неподвижен. В этой системе многоугольник B перемещается параллельно сам себе, и каждая его точка описывает окружность. Если мы пересечем все окружности, которые описывают вершины B, со всеми сторонами A, мы можем проверить, попадает ли какая-то из вершин B на границу A. Аналогично, перейдем в систему отсчета, связанную с B, и проверим, попадает ли вершина A на границу B. Ограничения на координаты позволяют выполнять проверки абсолютно точно.

Другой подход к тому же самому по сути решению: пусть в системе отсчета, связанной с A, произошло столкновение. Тогда выполнено векторное равенство x + y = z, где z — вектор с началом в точке P и концом где-то на границе A, x — вектор с началом в точке Q и концом где-то на границе B, y — вектор с началом в P и концом где-то на окружности с центром в P, проходящей через Q. Если переписать это равенство как y = z - x, можно увидеть, что все возможные значения z - x пробегают сумму Минковского многоугольников A и зеркального отражения B (с точностью до сдвига), y пробегает известную окружность. Сумму Минковского можно представить в виде объединения nm параллелограммов, каждый из которых — сумма двух сторон разных многоугольников; в конечном итоге, пересечем все границы всех параллелограммов с окружностью.

Сложность обоих решений — O(nm). Как указано выше, существует решение в целых числах; однако, маленькие ограничения на координаты не позволяют легко свалить решения с вещественной арифметикой. Также велик был соблазн написать неточное численное решение; мы постарались отсечь все такие решения, и в итоге ни одно из них не зашло. =)

Многие имели проблемы с 8-ым претестом. Он выглядит так (левая спираль вращается вокруг левой точки, правая вокруг правой):

Challenge: пусть мы хотим завалить решение с вещественной арифметикой. Построим тест, в котором многоугольники не сталкиваются, но проходят очень близко друг к другу. Какое минимальное положительное расстояние мы можем получить в заданных ограничениях на количество вершин и координаты?

497E - Подпоследовательности возвращаются

Пусть дана какая-то строка. Как посчитать количество ее различных подпоследовательностей? Будем приписывать символы к концу по одному и считать, сколько новых подпоследовательностей появилось. Пусть к строке s приписали символ c; в строке s + c на символ c заканчивается столько же подпоследовательностей, сколько их было всего в строке s. Если их прибавить к количеству подпоследовательностей s, каждая подпоследовательность s + c учтется по одному разу, кроме тех, которые заканчиваются на c и присутствовали в строке s: они учтутся дважды. Это приводит к следующему решению: будем хранить, сколько последовательностей заканчивается на каждый из возможных символов — cnt_c, тогда при добавлении символа c значение cnt_c надо заменить на сумму всех cnt плюс один (за пустую последовательность); ответ для всей строки равен сумме всех cnt (плюс один, если нам надо учесть пустую последовательность). Например, рассмотрим первые несколько символов строки Туе-Морса:

• ε — (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)

• ...

Легко видеть, что если значения cnt на данном шаге выписать как координаты вектора, и добавить к ним координату, тождественно равную 1, то приписывание одного символа к строке влияет на вектор как умножение на матрицу; естественным образом сопоставим каждой строке описанную матрицу.

Рассмотрим префикс последовательности a_i длины k^m. Если разделить его на k кусков длины k^m - 1, окажется, что i-ый из этих кусков может быть получен из 0-го прибавлением ко всем элементам i по модулю k. Будем насчитывать матрицы для префиксов длины k^m, а также для всех строк, получающихся из префикса прибавлением ко всем его элементам какого-то числа x; обозначим такую матрицу за A_m, x.

Легко видеть, что при m > 0 . Эта формула позволяет нам вычислить A_m, x для всех и x от 0 до k - 1 за время . Теперь, имея все A_m, x, мы легко можем перемножить некоторые из них в нужном порядке, чтобы получить матрицу для префикса a_i длины n.

К сожалению, пока что решение не укладывается в ограничения по времени. Один из способов получить решающее ускорение таков: заметим, что в формуле произведение можно разбить следующим образом: A_{m - 1, x}... A_{m - 1, k - 1} × A_{m - 1, 0}... A_{m - 1, x - 1} (если x = 0, вторая часть произведения пуста). Посчитаем для всех x произведения <<префиксов>> и <<суффиксов>> набора A_m, x: P_m, x = A_m, 0... A_{m, x - 1}, S_m, x = A_m, x... A_{m, k - 1}. Теперь A_m, x = S_{m - 1, x}P_{m - 1, x}. Теперь вычисление A_m, x для всех x при выбранном m сводится к вычислению P_{m - 1, x}, S_{m - 1, x} за O(k) умножений матриц, после чего каждый элемент A_m, x вычисляется за одно перемножение. Таким образом, наше решение теперь работает за , что укладывается в ограничения с запасом.

Challenge: решите задачу при k ≤ 100.

Привет, Codeforces.

Сегодня, 17 декабря в 19:30 MSK состоится очередной, 283-й раунд Codeforces. Автор задач — я, Михаил Тихомиров. Макс Ахмедов (Zlobober) помог мне с обсуждением и подготовкой задач, Мария Белова (Delinur) перевела условия задач на английский, а Георгий Чебанов (gchebanov), Александр Машрабов (map) и Нияз Нигматуллин (niyaznigmatul) заранее прорешали раунд и помогли нам выловить ошибки и неточности; скажем им большое спасибо!

Раунд состоится в обоих дивизионах. Разбалловка будет стандартной (не динамической); распределение баллов следующее:

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

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

Это мой четвертый раунд на Codeforces. Надеюсь, он пройдет не хуже предыдущих трех. =) Желаю всем удачи!

UPD: раунд завершен, всем спасибо за участие!

Поздравляем победителей:

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

Разбор доступен по ссылке.

A new long challenge is up at Al Zimmermann'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, especially if you like TopCoder Marathon Matches or something like that.

UPD: http://azspcs.net link doesn't work now. Here's a message from Al Zimmermann:

As you probably know, the AZsPCs server died on November 13th. Then, during the effort to transfer the site to an external host, the AZsPCs domain names (azspcs.com and azspcs.net) became stuck in registrar hell.

In order to allow the contest to continue I've borrowed a domain name. AZsPCs is now located at http://trdb.org and will remain there until January 17 (which is two weeks after the end of the current contest). As soon thereafter as possible, the site will return to azspcs.com and azspcs.net.

Best regards, Al Zimmermann

Я скоро засабмичу свои решения и положу здесь ссылки.

В некоторых разборах приведены дополнительные челленджи, над которыми можно поломать голову. Делитесь идеями в комментариях. =)

465A - inc ARG

Если прибавить к числу 1, его двоичная запись поведет себя понятным образом: все младшие единицы превратятся в нули, а следующий за ними ноль станет единицей. Найдем длину максимального суффикса из единиц, пусть она равна l. Тогда ответ равен l + 1, кроме случая, когда вся строка состоит из единиц, тогда ответ l.

Забавно, что в задаче div1E тоже приходится думать о том, что будет, если прибавить к числу 1. =)

465B - Входящие (100500)

Наилучшая стратегия такова: для каждого непрерывного отрезка из непрочитанных писем откроем первое письмо, пролистаем до последнего в том же отрезке, если есть еще непрочитанные письма, вернемся к списку.

Легко показать, что лучше мы сделать не сможем: для выбранного отрезка посмотрим на момент, когда мы прочитаем последнее письмо из него. Если мы еще не все прочитали, нам придется либо вернуться в список, либо переместиться в одно из соседних писем, среди которых нет непрочитанных. Таким образом, Для каждого отрезка, кроме одного, мы должны совершить лишнее действие, которое не приводит к прочтению нового письма. Эта же оценка достигается, если действовать по описанному выше методу.

464A - Нет палиндромам!

Если строка s содержит нетривиальную подстроку-палиндром w, то она содержит и подстроку-палиндром длины 2 или 3 (к примеру, это середина строки w). Поэтому строка s является терпимой тогда и только тогда, когда никакие два соседних символа или символа через один не совпадают.

Найдем теперь лексикографически следующую терпимую строку t. Она больше, чем s, поэтому у них есть общий префикс (возможно, нулевой длины), и следующий за ним символ больше в t, чем в s. Кроме того, этот символ должен располагаться как можно правее, чтобы строка t была как можно меньше. Для каждой позиции i мы можем попытаться увеличить s_i и проверить, не совпадает ли он с s_i - 1 или s_i - 2. Если у нас получилось сделать так с каким-то символом, оставшийся суффикс всегда можно корректно дополнить, если выполняется условие p ≥ 3, поскольку при заполнении его слева направо у нас всегда не больше двух запрещенных символов. Каждый символ в суффиксе надо жадно делать как можно меньше, чтобы не создать конфликтов с тем, что уже есть слева. Пишем жадность или умный перебор, они работают за O(n). Случаи p = 1 и 2 разобрать нетрудно, потому что в первом случае подходит только a, а во втором только a, b, ab, ba (впрочем, если жадность правильная, их и разбирать особо не надо).

Это пример общего алгоритма для генерации лексикографически следующего чего угодно: попытаемся увеличить элемент в позиции, расположенной как можно правее, чтобы суффикс можно было добить как-нибудь, после этого добиваем суффикс минимальным способом.

К сожалению, оказалось, что это более простой вариант задачи, которая уже встречалась на одном из старых раундов: 196D - Следующая хорошая строка. Мы не были в курсе этого и приносим за это свои извинения. В счастью, похоже, никто не стал копировать оттуда решения. Если вам понравилась эта задача, можете попытаться решить ее усложненный вариант. =)

464B - Восстановите куб

Для этой задачи есть куча способов решения. Опишем самый лобовой: переберем все перестановки координат для каждой точки, и для всех конфигураций проверим, является ли данное множество точек вершинами куба. Количество различных конфигураций в худшем случае можно достигать (3!)⁸ > 10⁶, поэтому проверка должно работать быстро.

Проверять можно, например, так: найдем минимальное расстояние между всеми парами точек, оно должно быть равно длине ребра куба, обозначим его за l. Для каждой вершины должно найтись ровно три другие вершины на расстоянии l, и ребра, исходящие в эти вершины, должны быть попарно перпендикулярны. Если это выполняется в каждой вершине, наша конфигурация является кубом, поскольку не-куб в таких условиях построить нельзя. Такой способ выполняет примерно 8² простых операций на каждую проверку, что достаточно быстро. Существуют и другие способы проверки, опирающиеся на различные свойства куба.

Такой алгоритм можно по-разному оптимизировать, чтобы наверняка влезть в TL. Можно, например, заметить, что если переставить все координаты каждой вершины куба одинаковым образом, получится снова куб. Отсюда заключаем, что порядок координат любой одной точки можно фиксировать и перебирать только остальные. Эта простая оптимизация ускоряет алгоритм в 6 раз, что сильно облегчает задачу упихивания во время.

Челлендж: судя по всему, работает и такой способ проверки: найдем длину стороны l, и посчитаем количество пар на расстоянии l, , . Куб должен содержать ровно 12 пар первого типа, 12 пар второго типа и 4 пары третьего типа. Можете ли вы доказать, что это необходимое условие является достаточным для того, что конфигурация является кубом? Верно ли это, если координаты могут быть нецелыми? Можете ли вы придумать еще более простой способ проверки на куб?

464C - Замены в числе

Хранить всю строку после каждого запроса тяжело, потому что ее длина растет экспоненциально и запросы меняют ее сложно предсказуемым образом. Иногда помогает мудрая мысль: не можешь решить задачу, попробуй решить с конца. =)

Пусть для последовательности запросов мы знаем для каждой цифры d, в какую строку превратится после выполнения всей последовательности (обозначим ее за t_d). Тогда строка s = d₁... d_n превратится в строку t_d1 + ... + t_dn (+ означает конкатенацию). Обозначим за v(s) числовое значение строки s. Тогда v(s) можно выразить как v(t_dn) + 10^|d_n|(v(t_dn - 1) + 10^{|d_n - 1|}(...)). Поэтому, чтобы найти v(s), достаточно знать m_d = v(t_d) и s_d = 10^|t_d| для всех цифр d. Раз ответ нужен по модулю P = 10⁹ + 7, сохраним все эти числа по модулю P.

Теперь добавим спереди к последовательности новый запрос d_i → t_i. Как поменяются чиселки m_d и s_d? Очевидно, для d ≠ d_i ничего не поменяется, а для d_i их надо пересчитать по формуле выше. Это делается за время O(|t_i|). Когда добавили все запросы, ответ для исходной строки s вычисляется точно так же за время O(|s|). Получили решение за . Код по сути состоит из одной формулы, поэтому реализация получается проще некуда.

Тупые решения, которые просто хранили всю строку и честно выполняли запросы, могли случайно проходить претесты. Очень жаль.

Челлендж: пусть мы хотим выдавать ответ после каждого запроса. Это легко делать off-line за суммарное время O(n²). Можно ли быстрее? Что, если мы обязаны отвечать онлайн?

464D - World of Darkraft - 2

В этой задаче надо было хорошо понимать вероятность, но в остальном все тоже несложно.

Обозначим количество заработанных монет X, а количество монет за продажу только предметов типа i за X_i. Понятно. что X = X₁ + ... + X_k, и EX = EX₁ + ... + EX_k (здесь EX это мат. ожидание X). Поскольку все типы имеют равную вероятность выпадения, все EX_i равны между собой, и EX = kEX₁. Давайте искать EX₁.

Если следить только за предметами одного типа, например, 1, выпадение предметов выглядит так: с вероятностью нам ничего не выпадает, а с вероятностью мы получаем предмет, уровень которого распределен как обычно. Обозначим за d_n, t среднее количество заработанных денег после убийства n монстров, если в начале у нас есть предмет уровня t. Ясно, что d_0, t = 0 (убивать больше некого, и денег мы не заработаем), а , что то же самое, что и = . Ответ находится как EX₁ = d_n, 1. К сожалению, у этой динамики Ω(n²) состояний, что слишком много при .

Можем ли мы поотсекать маловероятные события, которые не сильно влияют на ответ? Мы видим, что вероятность улучшить наш предмет падает с ростом его уровня, поэтому вряд ли он может стать очень большим. Мы знаем, что среднее количество попыток до успешеного выпадения монетки с вероятностью выпадения p равно 1 / p. Поэтому, среднее количество монстров, которых надо убить, чтобы получить предмет уровня T, равно . Поэтому в общем случае уровень нашего предмета будет равен примерно , что в наших ограничениях не превосходит 500. Мы хотим найти такую границу B, что если отсечь все состояния при t > B, ответ изменится не сильно. Это можно сделать, если честно посчитать дисперсию T и применить какое-нибудь неравенство типа Чебышева, или установить опытным путем: если мы увеличили границу, а ответ не поменялся, значит, она уже достаточно хорошая. На практике оказывается, что B ≥ 700 хватает для заданной точности. Получили решение за время (мы опираемся на то, что , и константа C спрятана в О-большом).

Челлендж: пусть мы убиваем монстров и предметы выпадают по тем же правилам, но теперь мы каждый раз можем выбрать, хотим мы продать новый предмет или уже имеющийся того же типа. Мы хотим максимизировать количество монет в конце. Каково мат. ожидание этого количества, если мы действуем оптимально?

Теперь иногда выгодно продавать дорогой и крутой предмет, а иногда выгодно оставить себе. Насколько быстрое решение такой задачи вы сможете придумать?

464E - Классическая задача

Это было бы просто упражнение на графовые алгоритмы, но непонятно, как работать с большими весами ребер, которые надо складывать и сравнивать абсолютно точно.

То, что вес каждого ребра — это степень двойки, подсказывает нам, что можно хранить битовую запись длины пути, поскольку она не сильно меняется при добавлении одного ребра. Но хранить все записи явно для всех вершин нельзя, поскольку суммарное количество единиц в них Ω(nd) (где d — это максимальное значение x_i), что не влезает в память даже с битовой магией.

Хочется воспользоваться какой-нибудь полезной структурой. Хорошо подходит персистентное дерево отрезков, которое хранит битовую запись. Персистентное дерево отличается от обычного тем, что каждый раз, когда мы хотим поменять состояние какой-то вершины, мы вместо этого создаем копию этой вершины и записываем новые значения в нее. Теперь у нас есть что-то вроде <<системы контроля версий>> над деревом: все состояния каждой вершины, и к любой вершине можно делать запросы, поскольку все ее поддерево, достижимое по ссылкам, остается неизменным. В таком дереве все запросы все еще выполняются за времени, но каждый запрос может потребовать создания дополнительных вершин.

Какие запросы к дереву мы хотим делать? Чтобы прибавить к числу 2^x, нужно найти ближайший ноль к x-ой позиции, записать в него единицу и заполнить нулями все позиции от него до x. Это умеет делать дерево с ленивым проталкиванием, которое тоже можно сделать персистентным.

Сравнивать два числа можно так: найдем самый старший бит, где числа отличаются, тогда то число, у которого в этом бите записан 0, меньше; если никакие биты в числах не различаются, они равны. Это можно делать за , если хранить хэши поддеревьев в каждой вершине и параллельно спускаться по обоим деревьям. Ограничения по времени и памяти были очень добрыми, поэтому разных хэшей можно было хранить сколько душе угодно и не бояться коллизии.

На этом общая идея заканчивается. Теперь просто используем такую реализацию чисел как черный ящик внутри Дейкстры. Все операции с числами замедлились в , поэтому наше решение работает за время . Однако, реализовывать его надо было аккуратно.

Главная ошибка, которую можно было сделать — сравнивать числа за дополнительной памяти, поскольку чтобы спускаться по дереву, нам иногда приходится делать проталкивания, и это создает новые вершины. Если так делать, мы съедим памяти, что в ML уже не влезает никак. От этого можно избавляться по-разному; например, если мы приходим в вершину, из которой надо что-то протолкнуть вниз, это значит, что весь отрезок этой вершины состоит из одинаковых чисел, поэтому ответить на запрос о сравнении можно уже сейчас.

Я хочу описать, как мне кажется, самое изящное решение по времени, памяти и простоте кода, которое позволяет совсем избавиться от ленивого проталкивания. Сперва создадим два дерева, полностью заполненных нулями и единицами соответственно. Пусть теперь мы присваиваем что-то на отрезке (пускай, для определенности, ноль), и текущая вершина целиком лежит внутри отрезка из запроса. Теперь вместо того, чтобы создавать копию и/или проставлять какие-то пометки, заменим эту вершину на соответствующую вершину из дерева с нулями. Все, поддерево этой вершины заполнено нулями, как мы и хотели. Если так делать, каждая операция создает новых вершин (с ленивым проталкиванием такого достичь не удастся, придется создавать минимум ), кроме того, вершины хранят в себе меньше информации и занимают меньше памяти. И про проталкивание чего бы то ни было думать не надо. Красота.

К этой задаче челлендж отсутствует, она и так достаточно challenging. =) Эта задача — хорошее упражнение, если вы хотите научиться работать со сложными структурами, поэтому всячески рекомендую ее написать и сдать в дорешку.

Все. Если остались вопросы, не стесняйтесь спрашивать в комментах. Благодарю за внимание.

Всем привет.

В воскресенье, 7 сентября, в 19:30 по московскому времени состоится очередной, 265-ый, раунд Codeforces. Задачи подготовил я, Михаил Тихомиров. Раунд пройдет в обоих дивизионах.

Для раунда будет использована стандартная (не динамическая) разбалловка.

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

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

Хочу поблагодарить Геральда Агапова (Gerald) за помощь в подготовке задач, Филиппа Руховича (DPR-pavlin) и Александра Машрабова (map) за тестирование раунда, Марию Белову (Delinur) за перевод условий на английский и Михаила Мирзаянова (MikeMirzayanov) за создание и поддержку проекта Codeforces.

Это мой третий раунд на Codeforces, и я постарался сделать задачи максимально интересными и разнообразными. Желаю получить удовольствие от раунда. Удачи! =)

UPD: раунд завершен. Всем спасибо за участие, надеюсь, вам понравились задачи.

Поздравляю победителей раунда:

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

Отдельные поздравления simonlindholm, единственному участнику, кто справился с самой сложной задачей Е!

Div. 2:

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

Разбор.

Всем доброе время суток.

Столкнулся я недавно с задачей, в рамках которой надо проверять, что данный граф раскрашиваем в k цветов. Специфика следующая:

• графы довольно большие (до нескольких тысяч вершин), но не очень плотные (средняя степень около 10-20, максимальная степень может быть порядка 50).

• k не слишком большое (до 10 примерно).

• важно, чтобы результат был достоверным (т.е. даже односторонняя ошибка не допускается).

Я нашел либу, которая умеет считать хроматическое число графа (надо сказать, что для таких масштабов она в среднем довольно быстро находит ответ, но на некоторых инстансах все же сильно задумывается). k-раскрашиваемость заведомо проще, чем подсчет хроматического числа, поэтому специализированное решение для раскрашиваемости должно бы работать получше; однако найти готовый код или хотя бы описание хорошего с практической точки зрения алгоритма мне не удалось.

Расскажите, пожалуйста, занимались ли вы этой задачей или чем-то похожим, что вы для этого использовали и какого результата добились? Приветствуются также любые советы, интересные ссылки и комментарии по существу.

Привет, Кодфорсес.

Друзья, а расскажите, пожалуйста, что вы знаете про быстрое нахождение радиуса и/или диаметра невзвешенного неориентированного графа (определения тут) ? Быстрое = быстрее, чем за O(MN) (т.е. обходы в ширину из каждой вершины). Интересуют любые результаты: вероятностные, в среднем, для неплотных графов и т.д. Благодарю.

Формулы генерируются со скрипом, надо обновлять страницу, чтобы они появлялись.

155A - I_love_\%username\%

Надо сделать, что написано: считать массив и посчитать количество элементов, больших или меньших всех предыдущих. Массив для этого можно даже не хранить, а поддерживать текущий минимум и максимум. Сложность — O(N), хотя проходил и квадрат.

155B - Комбинация

Заметим, что мы всегда можем сперва сыграть все карты с b_i > 0, т.к. каждая из них дает хотя бы один дополнительный ход. Количество оставшихся дополнительных ходов после этого не зависит от порядка их отыгрыша. После этого у всех оставшихся карт b_i = 0, и из них надо играть те, у которых максимально a_i. Простой вариант того же решения: отсортировать все карты по убыванию b_i, а при равенстве — по убыванию a_i, а затем идти от начала к концу, моделировать счетчик оставшихся ходов и суммировать очки. При этом надо не вылететь за границу массива, если дополнительных ходов больше, чем карт. Сложность — (или O(n²), если сортировать пузырьком, что тоже проходило).

155C - Домашнее задание

154A - Домашнее задание

Без ограничения на то, что каждая буква входит не более, чем в одну запрещенную пару, задача становится гораздо сложнее, а в таком варианте работает жадность.

Посмотрим на все вхождения букв из какой-либо пары. Они образуют несколько сплошных подстрок, разделенных какими-то другими буквами. В оптимальном решении две соседние подстроки, разделенные чем-то, не могут <<слиться>> в одну, поскольку для этого нам пришлось бы удалить все буквы, стоящие между ними. Но это никогда не выгодно, т.к. из любой подстроки, состоящей из букв одной пары, всегда можно оставить как минимум одну букву. Значит, нам достаточно устранить конфликты в каждой из таких подстрок, независимо от остальных. Для этого в каждой подстроке удаляем все те буквы, которых в этой подстроке меньше (это оптимально, т.к. пока в подстроке есть хотя бы две разные буквы из пары, где-то они будут соседними).

Все это можно посчитать за O(kN) k проходами по строке.

155D - Коллайдеры

154B - Коллайдеры

Здесь тупое решение <<поддерживать список/массив включенных коллайдеров и каждый раз пробегаться и считать все НОДы>> не пройдет по времени, т.к. можно включить в список все простые числа, которых, как известно, .

Заметим, что для каждого числа k, большего единицы, в каждый момент времени включено не более одного коллайдера с номером, который делится на k. Будем хранить массив, i-ый элемент которого содержит 0, если нет включенного коллайдера, номер которого делится на i, либо номер такого коллайдера. При запросе на включение k-ого коллайдера мы можем за перебрать все делители k, большие единицы, и проверить, что во всех элементах, соответствующих делителям, записаны нули. Тогда конфликтов нет, и можно включить коллайдер, а заодно записать во все рассмотренные ячейки число k. Если же хоть один элемент ненулевой, то в нем записан номер коллайдера, с которым мы конфликтуем, и мы можем его вывести (в этом случае включать ничего не нужно). При запросах на выключение надо просто проставить все нули в ячейках, соответствующих делителям.

Все это работает за . Можно решать и быстрее, если для каждого числа сохранить список его простых делителей и поддерживать описанный выше массив только для простых чисел. Суммарный размер списков для чисел от 1 до N — (это следует из оценки на сумму ряда по всем простым, не большим n). Значит, есть решение со сложностью , т.к. количество простых делителей k не превосходит (точная верхняя оценка — ).

155E - Профили-двойники

154C - Профили-двойники

Судя по комментариям, самая нестандартная задача. =)

Нужно в графе посчитать количество пар вершин, у которых совпадают множества соседей с точностью до самих этих вершин. Посчитать количество пар вершин, у которых множества совпадают в точности, можно, захешировав эти множества и посортировав хэши (да, хеши — это авторское решение). Как приспособить этот способ для случая, когда между вершинами есть ребро?

Заметим, что таких пар не больше, чем количество ребер, поэтому если мы знаем, как изменяется хэш при добавлении/удалении одной вершины в множество (например, используя полиномиальный хэш строки матрицы смежности графа), мы можем перебрать все ребра и проверить каждую пару напрямую. Можно и по-другому: посчитаем второй вариант хэша для каждой вершины, считая, что в каждой вершине есть петля. Тогда пара множеств будут совпадать как раз тогда, когда вершины — двойники и между ними есть ребро. После этого считаем количество пар аналогично первому случаю.

Можно было сортировать не хэши, а отсортированные списки смежности для каждой вершины. Из-за того, что их суммарный размер — 2M, это тоже могло проходить, но требовало аккуратной реализации, т.к. ограничения были большие. Сложность решения с хэшами — .

154D - Флатландское фехтование

Заметим, что если первый игрок может <<убить>> второго за один ход, то и второй из того же расположения (если бы был его ход) может убить первого, т.к. варианты ходов симметричны. Тогда, если нам разрешено стоять на месте, можно применить такую тактику: стоять и ждать, пока противник подойдет. Если он захочет нас убить, ему придется перед этим подойти на расстояние своего хода, после чего мы сразу сможем выиграть. Поэтому, если первый игрок не может выиграть в один ход (т.е. игроки изначально находятся вне зоны досягаемости друг друга), то никто не может обеспечить себе победу, т.к. противник может следовать описанной выше тактике, и в этом случае результат — ничья. Мы полностью проанализировали случай, когда a ≤ 0 ≤ b: если первый игрок может выиграть в один ход, то он выигрывает, во всех остальных случаях — ничья.

Пусть a и b одного знака. Тогда, обозначим d = x₂ - x₁. Если a ≤ b < 0, мы можем перейти к ситуации (d, a, b) = ( - d,  - b,  - a), которая аналогична текущей. Поэтому в дальнейшем 0 < a.

Итак, имеем такую игру: есть целые числа d и 0 < a ≤ b. За ход каждый из игроков может отнять от d произвольное целое число из диапазона [a;b]. Тот игрок, после хода которого d = 0, выигрывает. Если в какой-либо момент d < 0, объявляется ничья (т.к. никто уже не сможет выиграть).

Разбираем случай d > 0. Заметим, что если d mod (a + b) = 0, то у второго игрока есть симметричная стратегия: на любой ход x первого игрока он может сделать ход a + b - x, и вернуться в состояние d mod (a + b) = 0. Поскольку d уменьшается, рано или поздно второй игрок выиграет (ситуация аналогична такой же в игре, где можно брать от 1 до k спичек). Итак, если d mod (a + b) = 0, выигрывает второй игрок. Отсюда же, если d mod (a + b) , выигрывает первый игрок, т.к. он может свести игру к предыдущему случаю, предоставив второму игроку ход в проигрышной для него ситуации.

Что можно сказать про все остальные ходы? Оказывается, во всех остальных случаях получается ничья. Докажем это по индукции: пускай d = k(a + b) + l, где . Ситуация l = 0, как мы уже доказали, проигрышная, ситуации — выигрышные. Если , мы не можем сходить в проигрышную ситуацию (пользуемся предположением индукции для меньших k), но совершая ход a, попадаем в ничейную позицию (если k = 0, мы попадаем в отрицательное число, иначе в отрезок [(k - 1)(a + b) + b + 1;k(a + b) - 1], который по предположению ничейный). Аналогично для l = [b + 1;a + b - 1], ничейный ход — b.

154E - Колония на Марсе

Опять последнюю задачу никто не сдал, хотя некоторые участники подходили к этому очень близко.

В задаче требовалось найти площадь пересечения всевозможных кругов, содержащих заданное множество точек (ясно, что как раз у пересечения площадь минимальна, а количество кругов у нас не ограничено). Для начала поймем, как вообще выглядит это пересечение. Границу этой фигуры составляют некоторые из точек выпуклой оболочки, соединенные дугами окружностей радиуса R. Если мы определим, что это за точки, мы сможем за линейное время посчитать ответ, просто просуммировав площадь многоугольника и площади круговых сегментов.

Определить эти точки — как раз самое трудное. Ясно, что если есть хотя бы одно положение круга, содержащего все точки, с какой-то из точек на границе, то она входит в границу, в противном случае она лежит строго внутри пересечения. Если двигать круг в каком-нибудь направлении, рано или поздно он упрется в какую-нибудь точку — значит, одну точку мы находить умеем. Дальше можно пытаться реализовывать что-то вроде <<заворачивания подарка>> — идти по выпуклой оболочке и поддерживать множество <<граничных>> точек, контролируя взаимное расположение дуг. Однако такое решение связано с множеством технических трудностей и не предполагалось для реализации на контесте (хотя и проходит по времени).

Есть более простое решение, основанное на совсем другой идее. Сперва положим R очень большим, так что все точки выпуклой оболочки являются граничными. Когда мы начнем уменьшать R, точки начнут постепенно пропадать из границы фигуры. Как понять, какая точка пропадет первой? Для точки u из выпуклой оболочки обозначим ее соседей справа и слева l(u) и r(u). Из физического смысла процесса ясно, что первой пропадет та точка u, у которой радиус окружности, проходящей через u, l(u) и r(u) максимален (когда R станет равным этому радиусу, в точке u две дуги сольются в одну, а во всех остальных точках еще будут изломы; такой радиус назовем <<критическим>> для u). После этого удалим точку u из оболочки и будем считать вершины соседними, уже не учитывая ее. Процедуру будем повторять, пока максимальный радиус больше R. Оставшиеся точки как раз и будут точками границы.

Осталось придумать, как делать все это быстро. Заметим, что при удалении точки <<критические>> радиусы окружностей изменяются только для двух соседних с удаляемой. Заведем теперь очередь с приоритетом и будем хранить в ней критические радиусы вместе с номерами точек. На каждой итерации мы извлекаем точку с максимальным радиусом, удаляем ее из оболочки, обновляя информацию о соседях, пересчитываем радиусы для бывших соседей удаленной точки и изменяем информацию о них в очереди. Повторять, пока максимальный радиус не станет меньше R. Опять-таки, поскольку мы фактически моделируем происходящие при уменьшении R процессы, все будет работать корректно. Сложность всего процесса — O(n log n), т.к. итераций не более n и на каждой выполняется константное число операций с очередью размера не более n.

Есть один хитрый крайний случай, а именно когда граничными являются только две точки. Тогда при выкидывании последней точки все три радиуса равны, и наш алгоритм может попытаться выкинуть не ту. Но в этом случае треугольник с вершинами в этих точках тупоугольный, т.к. описанную окружность остроугольного треугольника нельзя сжать, это противоречило бы условию о существовании круга. Значит, надо выкинуть ту точку, угол при вершине которой тупой.

Всем привет. Меня зовут Михаил Тихомиров, и сегодня я — автор раунда. При подготовке задач мне очень помогли Геральд Агапов (Gerald) и Артем Рахов (RAD), условия на английский язык перевела Мария Белова (Delinur), за что им от меня огромное спасибо.

Сегодняшний раунд пишут участники из обоих дивизионов. В каждом дивизионе пять задач, задачки будут пересекаться, в общем, все как всегда. Разбалловка задач в каждом дивизионе сегодня также стандартная (500-1000-1500-2000-2500). В общем, самый обыкновенный раунд. Или нет?.. =)

Надеюсь, что задачки будут интересными, тесты — надежными, сервер — быстрым, решения — (в основном) правильными, а раунд — рейтинговым. =) Желаю всем удачного выступления!

Раунд завершился, всем спасибо!

Результаты:

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

Теперь полный разбор здесь.

С подачи e-maxx подзагрузился доказательством факта d(n) = o(n^ε). Факт, вроде бы, не очень известный и весьма содержательный с теоретической точки зрения (но не с практической, как будет видно дальше).

Ниже вы можете ознакомиться с моим вариантом доказательства. За комментарии и (тьфу-тьфу) указания ошибок буду благодарен. Если что-то непонятно, готов объяснить.

У меня при просмотре из Firefox 10 наблюдается такой спецэффект: при отображении записи рендерятся не все формулы, причем если обновлять страницу, то рендерится другое подмножество формул. =) Надеюсь, это поправят, а пока дочитав до места, где должна быть формула, надо обновлять, пока она не появится. =)

Итак, что же мы хотим доказать? Для любого ε > 0 верно, что , где d(n) — число делителей числа n.

Сперва заметим, что достаточно доказать, что d(n) = O(n^ε), т.е. существует положительное C, зависящее от ε, такое что d(n) ≤ Cn^ε. Действительно, пускай это так. Тогда d(n) ≤ Cn^ε / 2 = o(n^ε).

Приступим к доказательству d(n) = O(n^ε). Далее ε считаем фиксированным.

Пусть n = p₁^b₁... p_k^b_k, где все p_i — различные простые числа и все b_i натуральные (т.е. это каноническое разложение числа на степени простых). Тогда известно, что d(n) = (b₁ + 1)... (b_k + 1). Поделим d(n) на n^ε:

Мы доказываем, что это отношение не превосходит некоторого C.

Рассмотрим вспомогательную функцию , где k — некоторое положительное число, а ε ровно тот, что мы фиксировали (вид этой функции очень похож на вид одного множителя из последнего произведения). По ее виду сразу понятно, что если x стремится к 0 или к  + ∞, то f_k(x) стремится к 0. Значит, в некоторой положительной точке она достигает максимума (таких точек может быть несколько), и в ней производная равна нулю. Для удобства мы будем дифференцировать логарифм f_k(x), поскольку у него точка (или точки) максимума там же, где и у f_k(x):

В точке максимума производная равна нулю, т.е. — глобальный максимум (т.к. других нулей у производной нет).

В любой другой точке x

Теперь применим доказанное к нашему отношению:

Из последней формулы видно, что если p_j больше e^2 / eε, то соответствующий член произведения будет меньше 1, поэтому, исходя из того, что все p_j различны:

, где C зависит только от ε.

UPD: А вот еще прикол с этим доказательством, сам только что случайно наткнулся. Можно в качестве функции f_k(x) взять как раз элемент произведения . Тогда при применении того же метода построения верхней оценки получится, что , что стремится к бесконечности с ростом k, и потому не годится для оценки произведения. Каково? =)

139A - Петя и книга

139B - Ремонт

Что подразумевалось в условии:

Каждый рулон можно резать только на полоски, длина которых совпадает с высотой комнаты (потому что нельзя делать горизонтальные стыки, и расположение должно быть строго вертикальным). В каждой комнате можно клеить только один тип обоев (в разных комнатах клеить одинаковые типы можно). Для каждой комнаты надо всего лишь определить оптимальный по цене тип обоев.

Ясно, что количество рулонов данного типа, нужных для обклейки выбранной комнаты, есть периметр стен комнаты, деленный на суммарную ширину полосок, получаемых из одного рулона, с округлением вверх. Количество полосок есть длина рулона, деленная на высоту комнаты, с округлением вниз.

Для каждой комнаты перебираем типы обоев и выбираем минимальный по суммарной цене. Сложность - O(mn)

139C - Урок литературы

138A - Урок литературы

Техническая задача. Основная сложность - проверить, рифмуются две строчки или нет.

По условию, чтобы это проверить, надо было отрезать суффиксы, которые начинаются в k-ых с конца гласных и сравнить их. Если в строчке меньше, чем k гласных она не может участвовать в рифмах в принципе (даже с такой же строчкой).

Здесь можно было использовать два указателя, либо пользоваться функцией взятия подстроки (в C++ s.substr(...)). Кроме того, надо было аккуратно разобрать случаи, когда k-ая с конца гласная - первая в строке, когда гласных меньше k, и проч.

Теперь будем поддерживать три логические переменные: aabb, abab и abba, в которых храним, верно ли, что все встреченные нами четверостишия можно отнести к соответствующему типу. Для каждого нового четверостишия их легко обновить - надо сравнить нужные пары строк на рифмуемость.

Если в конце все три переменные - TRUE, то ответ - aaaa. Если все - FALSE, ответ - NO. Иначе выставлена только одна из них, она и является ответом.

Сложность - O(S), где S - сумма длин строк.

139D - Перестановки цифр

138B - Перестановки цифр

Эта задача, кажется, многих сбила с толку в самом начале контеста, хотя мне она казалась простой.

На сколько нулей заканчивается сумма двух произвольных чисел? Для того, чтобы это посчитать, надо сначала пропустить все разряды с конца, где у обоих чисел стоят нули, для следующего проверить, дают ли цифры в нем сумму 10, а потом идти дальше, пока сумма цифр равна 9 (это все просто из сложения столбиком).

Пускай мы фиксировали число общих нулей в конце для двух перестановок. Переберем варианты цифр, дающие в сумме 10. При выборе этих цифр для определения количества нулей достаточно знать, сколько каких цифр осталось свободными в каждом числе. Если в одном числе осталось a₀, ..., a₉ цифр, а в другом b₀, ..., b₉, то количество нулей, которые дают оставшиеся цифры равно min(a₀, b₉) + min(a₁, b₈) + ... + min(a₉, b₀). Если изначально сохранить количество вхождений каждой цифры в число, посчитать ответ становится просто.

Теперь надо перебрать количество общих нулей и цифры, дающие в сумме 10, и для каждого варианта посчитать указанную выше функцию (при этом надо не забыть вычесть уже использованные цифры), а после этого правильно восстановить ответ для максимального значения. Сложность - O(10 * 10 * N) = O(N).

Основная подлость, на которую можно было напороться - решить, что надо всегда ставить все нули в конец обоих чисел, а потом подбирать остальные цифры. Это опровергает 4 претест - 1099. Легко проверить, что все варианты с нулями в конце проигрывают 1909 + 1091.

Были и другие баги, например, не учитывать вариант, когда общие нули есть, но следующие цифры не дают в сумме 10.

139E - Грибные гномы - 2

138C - Грибные гномы - 2

Первое, что здесь надо понять - ответ является суммой вероятностей для всех грибов, что каждый из них по отдельности не будет раздавлен (свойство матожидания - линейность, даже при зависимых величинах). Указанная вероятность для каждого гриба равна произведению для всех деревьев, которые могут накрыть этот гриб, что они НЕ упадут в сторону гриба.

Таким образом, мы можем рассмотреть семейство отрезков, соответствующих вариантам того, как могут падать деревья, с соответствующими вероятностями. После этого для каждого гриба перемножаем вероятности отрезков, которые его покрывают, и суммируем произведения.

Способов посчитать это быстро много:

1) Сканирующая прямая. Будем идти слева направо и рассматривать события "отрезок начался", "отрезок кончился", "нашелся гриб" и поддерживать произведение вероятностей отрезков, покрывающих текущую точку. Находим гриб - прибавляем к ответу текущую вероятность.

Чтобы это реализовать, надо сохранить все события в массив (с указанием типа), а потом отсортировать по координате.

У этого решения есть недостаток - если много отрезков пересекаются в одной точке, у нас будут получаться крайне маленькие числа, которые из-за машинной точности будут сохраняться как нули, что испортит нам весь ответ (после выхода из всех отрезков и деления должна получиться единица, а не ноль, как у нас).

Это можно побороть в рамках решения:

а) Воспользоваться тем, что различных значений вероятности всего 101, и хранить массив, сколько отрезков с каждой вероятностью встретилось. При обработке гриба проходится по массиву и за ~100 операций вычислять ответ. Описанной проблемы не будет, потому что ошибка не накапливается.

б) Хранить, например, set из встреченных отрезков с вероятностями. При обработке гриба надо пройтись по сету, что делается за линейное время. При этом если перемножении элементов сета число стало очень маленьким (< 1e-10), можно дальше не перемножать и считать ответ нулем. Эта оптимизация отсекает "глубокие" перемножения, поскольку максимальное число, которое надо хранить в сете - 0.99.

в) Прологарифмируем все вероятности и будем складывать логарифмы вместо перемножения, когда надо вычислить вероятность, возводим e в степень суммы. Это, очевидно, решает проблему с точностью.

2) Дерево интервалов.

Отсортируем грибы по координате. Каждый отрезок покрывает некий сплошной кусок массива грибов (его концы находятся бинпоиском). Это позволяет построить на массиве грибов дерево интервалов по умножению и выполнить для каждого отрезка запрос "умножить числа на интервале массива на x". Здесь тоже никаких проблем с точностью нет, поскольку нет деления.

Все вышеуказанные методы работают за O((m + n)log(m + n)), что удовлетворяет ограничениям.

По поводу странных баллов и претеста - проблема с точностью была обнаружена довольно поздно, поэтому борьба с точностью стала дополнительным этапом задачи, и сложность была повышена. Заметить это во время контеста предполагалось крайне сложным, поэтому про претест было написано в условии.

138D - World of Darkraft

Заметим, что для "четных" и "нечетных" клеток (т.е. клеток с четной и нечетной суммой координат) игра происходит независимо: игрок делает ход в одной из них на выбор. Это позволяет применить теорию Шпрага-Гранди для определения выигрышности всей игры.

Далее будем рассматривать, например, только четные клетки. Рассмотрим границу произвольного связного куска после некоторого количества ходов. В нее входят границы поля и диагонали, оставшиеся от предыдуших ходов. Ясно, что каждый кусок выпуклый, поэтому кусок задается четырьмя диагоналями, которые его ограничивают с четырех сторон (для любого куска и любой стороны всегда можно подобрать такой номер, что диагональ с этим номером хотя бы касается куска). Для подсчета функции Гранди этого куска, надо перебрать все клетки нужной четности, которые в нем лежат, и воспользоваться функциями Гранди для получающихся кусков. Так как получающиеся куски меньше исходного, функцию для всевозможных кусков можно посчитать динамических программированием.

После этого надо сравнить функции, соответствующие множеству всех четных клеток и множеству всех нечетных. Если они равны, то ответ - "LOSE", если нет - "WIN" (по свойствам функции Гранди).

Удобнее всего организовать вычисления, заведя четырехмерный массив, где каждое измерение - номер диагонали, ограничивающей кусок с очередной стороны. Перебирать клетки внутри куска теперь удобно по диагоналям, на которых лежит клетка. По номерам диагоналей вычисляются координаты клетки, после чего надо проверить, что она лежит внутри поля и рассмотреть соответствующий ход.

Сложность - O((n + m)⁴ (количество кусков) mn (количество ходов внутри куска).

138E - Адские ограничения

Пусть у нас есть набор ограничений указанного вида и некоторая строка. Пусть для каждой позиции в строке посчитано количество ограничений, которым удовлетворяет суффикс строки, заканчивающийся в этой позиции.

Припишем к строке справа новый символ (при этом к массиву добавится еще один элемент). Предположим, что он не задействован ни в одном из ограничений. Тогда легко видеть, что старая часть массива не изменится.

Пусть новый символ участвует в ограничении "c l r". Количество символов c в каждом суффиксе увеличилось на 1, поэтому можно понять, для каких позиций количество ограничений изменилось:

с[. . -1 . . .с]. . . . . с[ . +1. .c] . . c

r + 2. . . r + 1 . . . l + 1. . . . l. . . .1 - номер вхождения c, считая с конца

(Квадратными скобками обозначен участок строки, на котором произошло изменение.)

Алгоритм таков: будем приписывать к строке по одному символу и поддерживать количество чисел в массиве ограничений, удовлеторяющих L ≤ x ≤ R. При добавлении символа новый элемент массива можно посчитать за O(k). Для каждого из ограничений, содержащих новый символ, найдем отрезок, на котором будет происходить изменения (на этом этапе имеет смысл разделить верхнее и нижнее ограничение на два с весами +1 и -1). Пройдемся по отрезку и изменим значения массива, поддерживая значение счетчика чисел, удовлевторяющих ограничению L ≤ x ≤ R. Теперь значение счетчика - количество подстрок, заканчивающихся в текущем символе и удовлетворяющих ограничениям задачи. Будем прибавлять этот счетчик к ответу после обработки каждого символа. Ясно, что ответ правильный.

Рассмотрим одно ограничение. Видно, что при добавлении каждого нового символа полуинтервал, в котором изменяется состояние этого ограничения, смещается вправо и не пересекается с предыдущим. Поэтому суммарное количество изменений, которые придется проделать для данного ограничения, не превышает n, а суммарное количество изменений по всем ограничениям - nk.

Осталось научиться быстро находить концы соответствующего отрезка изменения. Это легко сделать, если пронумеровать все вхождения каждого символа в строку, или если поддерживать конец предыдущего отрезка изменения для каждого ограничения.

Суммарная сложность - O(nk).

Привет.

Сегодняшний раунд подготовил я. Меня зовут Михаил Тихомиров, я студент 4 курса мехмата МГУ, помимо этого работаю в Яндексе разработчиком-исследователем.

Хочется сказать спасибо Артему Рахову (RAD) за значительную помощь и грамотную координацию, Марии Беловой (Delinur) за традиционно качественный перевод условий, а также MikeMirzayanov за то, что все мы здесь сегодня собрались. =)

Раунд будет для обоих дивизионов. В каждом дивизионе, как и всегда, будет по пять задач, некоторые из которых будут общими, но не все.

Разбалловка:

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

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

Сегодняшний раунд - последний в 2011 году. Я хочу поблагодарить команду Codeforces, всех, кто придумывал, готовил или помогал готовить задачи в этом или прошлых годах, а также тех, кто способствует развитию проекта. Codeforces давно перестал быть просто платформой для соревнований по программированию, сейчас это - место, где каждому есть чему научиться у других, каждый может почерпнуть частичку опыта у более опытных товарищей при непосредственном общении, повысить свой уровень на контестах и тренировках, или просто получить удовольствие от красивых и оригинальных задач.

Пожалаем проекту удачного развития в следующем году и долгих лет существования.

Всем удачи. Желаю получить максимум удовольствия от сегодняшнего раунда и выступить на уровне.

И да, всех с наступающим! =)

UPD:

Раунд окончен. Всем спасибо за участие! Надеюсь, вам понравилось.

Победители.

Div1:

1. ivan.popelyshev

2. al13n

3. WJMZBMR

4. yeputons

5. romanandreev

6. dolphinigle

7. wata

8. Shef

9. shangjingbo

10. azizkhan

Div2:

1. s-quark

2. wayne-ho

3. emrevarol

4. agh

5. lzqxh

В конце раунда по техническим причинам несколько минут был недоступен сервер. К сожалению, мы не имеем возможности принять решения, которые вы не смогли из-за этого сдать. Из двух неприятных вариантов: делать раунд нерейтинговым и оставить все, как есть, мы решили выбрать второй, поскольку это затрагивает меньше участников. Мы приносим извинения тем участникам, на которых влияет это решение.

UPD2: разбор из ап.