Endagorion's blog

By Endagorion, history, 9 days ago, translation, In English,

Sorry for the wait! We'll be glad to answer your questions in the commens.

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

 
 
 
 
  • Vote: I like it  
  • +146
  • Vote: I do not like it  

By Endagorion, history, 8 months ago, In English,

I hope you've enjoyed the problems! Please ask your questions and report flaws in the comments.

Problem A

First insight is that two spells are always enough. Why? Let's freeze all leftbound penguins at point 10 - 9 and all rightbound penguins at point 109.

So the only problem is to determine when only one spell is enough. If that holds, there should exist a point which all penguins will cross at some moment. Let's put this point at x + ~--- rightmost point among penguins' coordinates which run to the right. Now all rightbound penguins will cross this point. If there is a leftbound penguin which doesn't cross x +  then its coordinate x -  must be less than x + . But in this case there are two penguins running away from each other~--- clearly one spell will not suffice.

So, the easiest and most effective solution is to find x + ~--- the location of rightmost rightbound penguin, and x - ~--- the location of leftmost leftbound penguin, and check if x -  < x + . If that holds, the answer is 2, otherwise it's 1. This can be easily done in O(n). Other approaches include checking for all pairs of penguins if they run away from each other in O(n2), or more effeciently using sorts in .

Problem B

Let's divide all configurations by leftmost turned-on bulb. Suppose the leftmost turned-in bulb is i-th. If i + k - 1 ≤ n, then the bulbs i + 1, \ldots i + k - 1 can be turned on or off in any combinations, so the number of such configurations is 2k - 1. If i + k - 1 > n, then the ``free'' bulbs are limited by the end of the line, and the number of configurations is 2n - i. There is also one combination when all bulbs are off.

These quantities can be summed up in if one uses binary modulo exponentation of 2, or in O(n) if the powers of 2 are precomputed with DP. It can also be shown (by summing the geometric progression which you can try to do yourself) that the answer is always equal to (n - k + 2)2k - 1, this number can be computed in .

Problem C

Let's come up with a straightforward solution first. We will just simulate the battles and keep the current value of M. How many iterations we will have to make? And more importantly, how can we tell if the answer is  - 1 or we just didn't do enough battles yet?

To answer that, let's keep track of values of M before all battles with the first opponent. If some value of M repeats twice, then the whole process is looped and the answer is  - 1. On the other hand, if M > A (the largest possible value of ai, that is, 106) we will surely win all battles. So the maximal number of iterations is n(A + 1) (since no value of M ≤ A can repeat twice).

This is still too much for straightforward simulation ( battles). How can we optimize that? Let us find f(M)~--- the number of first lost battle for each value of M at the start that does not exceed A. This can be done in O(A) for all M's at the same time using the fact that f(M) does not decrease. Indeed, suppose we know f(M) and also g(M)~--- our power before battling the last opponent. If the starting power were M + 1, at this point our power would be g(M) + 1. If this is still not enough to win opponent f(M), then f(M + 1) = f(M), g(M + 1) = g(M) + 1. Otherwise, we proceed to following opponents updating f(M + 1) and g(M + 1) accordingly until we lose or win them all. Notice that the total number of increases of f(M) is at exactly n, thus the complexity is O(n).

Using values f(M) we can emulate the battles much more quickly: for given M find the first lost battle, add f(M) to the total number of battles, update M with max(0, g(M) - aM), proceed until we win everyone or M repeats. This optimization leads to O(n + A) solution.

There is another tempting idea for this problem which turns out to be wrong. If you have trouble with WA3, consider this case:

4 2
0 5 0
6 0 3
7 0 6
8 0 4

Problem D

Let's call a position x \emph{interesting} if color(x) ≠ color(x - 1). If we find two interesting positions x < y so that color(x) = ... = color(y - 1), then the answer is equal y - x.

How can we find a single interesting position? Suppose we have two arbitrary positions a < b and color(a) ≠ color(b). Then we can find an interesting position x with a < x ≤ b using binary search: let . If color(a) ≠ color(c) update a with c, otherwise update b with c. At some point b - a = 1 and we're done. Denote this resulting position as f(a, b).

Okay, how to find two positions of different colors first? Let M be the maximal possible value of L. Consider a segment of length, say, 2M. The colors inside this segment have to be distributed \emph{almost evenly}, so after trying several random cells we will find two different colors with high probability.

There are several possible options what to do after we have obtained two interesting positions x and y. We can use the fact that either the segment x, \ldots, y - 1 is same-colored, or it has at least 1 / 3 of the cells with color! = color(x), so we can try random cells until we find z with color(z) ≠ color(x), and then we can shrink the segment to either x, f(x, z) or f(z, y), y, whichever's shorter. Length of the segment shrinks at least two times after each iteration (in fact, it shrinks even faster).

Another approach is to note that L divides y - x for all interesting positions x and y. Thus we can obtain several interesting positions f(a, b) for random values of a and b, and find G~--- GCD of their differences. Clearly, . It can also be shown that G = L with high probability is the number of positions is, say, at least 50; it is a bit harder to analyze though, but the general idea is that while it's hard to determine the exact distribution of f(a, b), it is \emph{not that bad}, so it is improbable for many values of f(a, b) to be, say, multiples of 2L apart.

I want to describe another, much simpler solution by Chmel_Tolstiy. Let's find the smallest k such that color(2k) ≠ color(0). It is easy to prove that there is exactly one change color between these two positions, so its position can be found with binary search as before. Do the same way in negative direction and find another closest color change, output the difference. This solution turned out to be most popular among contestants (but less popular among the testers).

Problem E

Let's find out how to check if the answer is at most D and binary search on D.

Let's make an arbitrary vertex the root of the tree. Note that if the subtree of any vertex v contains even number of outposts then no paths can come out of the subtree (since their number must be even, but at most one path can pass through an edge). Similarly, if there is an odd number of outposts then one path must come out of the subtree. Consider all children of v: each of their subtrees will either yield a single path or nothing. We have to match the resulting paths between each other and choose at most one of them to yield to the parent. Naturally, our intention is to make the unmatched path as short as possible while making suring that in each pair of matched paths their total length does not exceed D. We can also note that the answer is never  - 1 since we can always match the paths if we ignore their lengths.

Consider the case when we have to match an even number of paths. Let's say we have an array of even length a1, \ldots, a2k, and want to make pairs of its elements such that sum in each pair does not exceed D. It can be shown that the optimal way is to sort the array and then match a1 + a2k, a2 + a2k - 1, and so on. Indeed, consider that a1 is not matched with a2k but with ax, and a2k is matched with ay. Let's rematch them as a1 + a2k and ax + ay. Since the array is sorted, a1 + a2k, ax + ay ≤ ay + a2k and the maximum sum won't increase after rematching. Drop the elements a1 and a2k and proceed until we obtain the matching a1 + a2k, a2 + a2k - 1, \ldots.

Now we want to match an odd number of paths while minimizing the unmatched path length. This can be done with binary search on unmatched length and checking if the rest of the paths can be matched using previous approach. Another approach is greedy: take the maximal element x, find maximal element y such that x + y ≤ D, erase them both. If there is no such y, then x must be unmatched. Finally, check if there is at most one unmatched element. All these approaches take time for a vertex with d children, but the real time depends hugely on the actual approach (say, using std::set or TreeSet is much slower than sorts and binary searches).

The total complexity is , where A is maximal possible answer value.

Problem F

Consider all possible values of a and b such that . Let's arrange them in a table, roughly like this (second sample, O stands for possible value, . for impossible):

  0 1 2
0 O O .
1 O . .
2 . . .

When can one determine the numbers? Consider the position (0, 1): the person with number 2 knows that the only possible pair is (0, 1), so he can answer it. In general, once there is only one possible value in some row or some column this value is removed on this day since one person can deduce the other number. So, after day 1, the table becomes (X stands for no longer possible value):

  0 1 2
0 O X .
1 X . .
2 . . .

Now position (0, 0) can be solved on day 2 according to our rule. One can see that in the third sample the only solvable positions are (0, 2) and (2, 0).

It is tempting to look for a simple formula, but behaviour of how positions are resolved turns out to be complex (for example, try X = {5, 13, 20}). We should look for a way to simulate the process efficiently.

First, note that there will be at most 2(A + 1) resolved positions, where A is the maximal element of X. Indeed, each resolved position leaves a new empty row or a column. Thus, the process will terminate quite quickly, but the total number of possible initial positions is too large to choose resolved positions straightforwardly.

There are few possible optimization. For one, suppose we have the data structure with following operations: initialize with a set of numbers, remove a single number, once there is a single number in the set, find it. Let's store this kind of structure for each row and column, now the process can be simulated easily. The simplest way to implement this structure is to store a pair (sum of numbers, count of numbers). Moreover, all the structures can be initialized at once in O(A) time using prefix sums and prefix counts.

Another idea: if there are three consecutive numbers xi, xi + 1, xi + 2 with xi + 2 ≤ xi + xi + 1 + 1, then all positions with a + b < xi will be unsolvable. If we drop all xj < xi, the sum of the rest elements of X will be O(A), which allows for a simple simulation.

Read more »

 
 
 
 
  • Vote: I like it  
  • +41
  • Vote: I do not like it  

By Endagorion, history, 8 months ago, translation, In English,

Cheers everyone.

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

Best of luck!

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

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

Editorial here

Read more »

 
 
 
 
  • Vote: I like it  
  • +76
  • Vote: I do not like it  

By Endagorion, history, 13 months ago, In English,

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 kx for non-negative integers x that lie with the range [l;r]. A simple cycle works: start with 1 = k0, 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 = 1018, k = 109, the powers will be 1, 109, 1018, and the next power is 1027, 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 10t 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 π (R2 - r2).

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  ≥ arrindex.

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, arrindex + ⌊ 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, MF2000, 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 dx, 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(n2) 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(n2) 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.)

Read more »

 
 
 
 
  • Vote: I like it  
  • +74
  • Vote: I do not like it  

By Endagorion, history, 21 month(s) ago, In Russian,

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 pt ≤ n for every prime p ≤ n; there should be a number in [n + 1;m] that divides pt 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 Ll, r (Rl, r) the largest distance from a vertex of (l, r)-haven to the merged vertex l (r), Sl, r the largest distance between any two vertices of (l, r)-haven, and Dl, r the distance between l and r (after merging each of them). All these numbers can be computed in O(n3) for all pairs (l, r) (use two pointers to compute Sl, 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 + D1 + ... + Dk + R, where L is the distance from u to the closest merged vertex, D1, ..., Dk 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 dpi, 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 dpi, j is the largest value of L + D1 + ... + Dk such that the last merged vertex of Dk is the merged vertex i. Initialize dpi, 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 Sl, r and all the rest using the DP value. Finally, to find the answer use such dpi, k that the last two-paths haven does not have its vertices too far apart, and also dpi, k + taili ≤ x, where taili is the largest distance from i to any of the ends. That makes for an solution, also probably a highly optimized O(n4) might pass.

Read more »

 
 
 
 
  • Vote: I like it  
  • +48
  • Vote: I do not like it  

By Endagorion, 21 month(s) ago, In Russian,

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 lt and walls lw (note that they can be equal); reserve two planks of chosen lengths for each. If there are ai planks of length li left, there should at least (be careful not to divide by zero of lw = 1!) departments of width li. 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(n3) 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(n2).

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(n3) solutions pass, but it seems I failed even at that. =(

C — Solitaire Simplified

There is a straightforward O(n4) DP solution which basically stores all the interesting info about the state of the game; it can be probably optimized to O(n3). 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 pi, numbers qi are determined by qpi = 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 q2 > q1 or q2 > q3 > ... > qn; 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(n3), 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 1018. 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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +77
  • Vote: I do not like it  

By Endagorion, 22 months ago, In English,

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(n2) or O(n3) 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|2) time? In O(n + |t|) time? Maybe even faster? =)

538B - Quasi Binary

n is up to 106. We may note that there are only 26 + 1 = 65 quasi-binary numbers not exceeding 106, 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 ≤ 1018.

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 di and di + 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 d1 and after dn, 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 di = 0 and di + 1 = t (they may be increased of decreased simultaneously without changing the answer), and hdi = a, hdi + 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 |hi - hi + 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 hi ≤ a + i and hi ≤ b + (t - i) hold. Let hi = min(a + i, b + (t - i)) on the [0; t] segment; clearly, every hi accomodates the largest possible value, therefore the value of maximum is also the largest possible. It suffices to show that these hi satisfy the difference condition. Basically, two cases should be considered: if for hi = a + i and hi + 1 = a + i + 1, or hi = b + (t - i) and hi + 1 = b + (t - i - 1), the statement is obvious. Else, hi = a + i but hi < b + (t - i) = hi + 1 + 1, and hi + 1 = b - (t - i - 1) but hi + 1 < a + (i + 1) = hi + 1. Thus, |hi - hi + 1| < 1, and hi = hi + 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 hdi for a sequence hi), determine how many (modulo a prime number) integer sequences of length n with the property |hi - hi + 1| ≤ 1 agree with the subsequence and have global maximum equal to H? Can you solve the problem in O(n2) 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 (x1, y1) containing a piece, and a field (x2, y2) not containing a piece and not being attacked, clearly a move (x2 - x1, y2 - y1) 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(n4) 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 u1, ..., uk, 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(ui) maximal numbers (that is, w(v) - w(ui) + 1, ..., w(v)) in the subtree of w(ui), we must also arrange them optimally; this task is basically the same as arranging the numbers from 1 to w(ui) in the subtree of w(ui), 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 n1, 1, ..., n1, w(ui) to the leaves of the subtree of ui in some order; the numbers in the subtree of ui will be arranged so that the result is maximal when the maximizing player starts in ui. Suppose that numbers ni, j are sorted by increasing of j for every i; the minimizing player will then choose the subtree ui 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 ni, j for should also be greater than r; but there are numbers ni, 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 ni, j with , and r as, say, n1, dpmax(u1); the first player will have to move to u1 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 ui contains dpmax(ui) numbers, the minimizing player can go to ui and grab the current result. It follows that we may safely put dpmax(ui) - 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 dpmax(root) = a and dpmin(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 av is the element . One can show that there are only different elements that can be the parent of av 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 av and ap); 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 ck 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 ck (for a given k) in time? Can you find all ck (for 1 ≤ k ≤ n - 1) at once in O(n2) 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(n2)? 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 xi + yi and xi - yi 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 xi and ti 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 si the number of 1's among the first i commands, and s = sl for simplicity. Evidently, an equation holds, because the full cycle is executed ti / 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 sl = s. In any correct program si ≤ si + 1 ≤ si + 1, but not all values of si are known to us. When is it possible to fill out the rest of si to match a correct program? If sa and sb are adjacent entries that are fixed (that is, every sc under a < c < b is not fixed), the inequality 0 ≤ sb - sa ≤ 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 sb - sa 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 sa come! Sort them by non-decreasing of a. All fixed sa can be expressed as linear functions of s; if we substitute these expressions in the 0 ≤ sb - sa ≤ 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 (n1, n2). Provided this distribution, in what cases a pair of conflicting teachers can be arranged correctly? If the teachers' segments are [l1, r1] and [l2, r2], either l1 ≤ n1 ≤ r1 and l2 ≤ n2 ≤ r2, or l2 ≤ n1 ≤ r2 and l1 ≤ n2 ≤ r1 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 = x1 and x = x2 respectively. The intersection of subsegments for UOTRs obtained after the first event will stay the same while x1 ≤ x < x2. Suppose the y's subsegmen intersection is equal to [l;r]. If we stay within x1 ≤ x < x2, for a satisfying pair of (x, y) the minimal value of x + y is equal to x1 + l, and the maximal value is x2 + 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 zi, j which correspond to the event 'ni 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 ≤ n1 + n2 ≤ 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, zi, j for j < 0 clearly must be considered automatically false, and zi, 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 wj 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: n1 and n2 are maximal so that z1, n1 and z2, n2 hold, and the teachers are distributed unequivocally by values of wj. 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 n1 and n2 may be reduced to 0, t, li, t - li, ri, t - ri. We can prove that by starting from any valid values of n1 and n2 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!

Read more »

Tutorial of Codeforces Round #300
 
 
 
 
  • Vote: I like it  
  • +312
  • Vote: I do not like it  

By Endagorion, 22 months ago, In English,

Hello, Codeforces!

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

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

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

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

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

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

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

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


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

UPD3: Thanks for participating!

The winners are:

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

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

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

Read more »

Announcement of Codeforces Round #300
 
 
 
 
  • Vote: I like it  
  • +1212
  • Vote: I do not like it  

By Endagorion, 23 months ago, In Russian,

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(n2) substrings, which is a reasonable amount in the given limitations. However, iterating over all symbols in the substring yields O(n3) 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 qc — the probability that current substring consists only of characters c. If we append one symbol from the right, qc changes in a simple way: if the symbol is a letter x, then all qc with c ≠ x become zeros, while qx does not change; else, if the symbol is question mark, every qc gets multiplies by pc. So, we process all substrings with fixed beginning in O(mn) (where m is the number of different symbols), for a O(mn2) 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(n2) 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 s1 and s2 are present. Consider vertices that lie on the path connecting s1 and s2 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 s1 or s2 (WLOG, assume it's s1), the second-to-last will be either s2 or the neighbour of s1 in the path, etc. The observation is that at any moment there is a consecutive subsegment of the s1-s2 path which is covered.

Count dpl, 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 ordl is the number of topological orderings of the subtree of l-th vertex (which can be calculated as described above), tl is the size of this subtree, and Tl, 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; dpl, r is simply the sum of those two quantities. The base of DP is clearly dpl, l = ordl.

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +74
  • Vote: I do not like it  

By Endagorion, 2 years ago, In English,

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

Make sure to comment if you find any mistakes.

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

520A - Pangram

Idea: Endagorion

Preparation: Endagorion

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

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

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

520B - Two Buttons

Idea: Endagorion

Preparation: Endagorion

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

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

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

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

520C - DNA Alignment/521A - DNA Alignment

Idea: Endagorion

Preparation: Endagorion

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

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

520D - Cubes/521B - Cubes

Idea: savinov

Preparation: savinov, sokian, zemen

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

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

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

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

This solution is if using the appropriate data structure.

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

520E - Pluses everywhere/521C - Pluses everywhere

Idea: Endagorion

Preparation: gchebanov, DPR-pavlin

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

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

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

To sum up, the total answer is equal to

Let us transform the sum:

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

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

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

521D - Shop

Idea: Endagorion

Preparation: gchebanov

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

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

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

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

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

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

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

521E - Cycling City

Idea: Endagorion

Preparation: Endagorion

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

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

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

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +151
  • Vote: I do not like it  

By Endagorion, 2 years ago, translation, In English,

Hello, Codeforces!

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

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

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

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

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

UPD: you are free to discuss the problems now.

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

Also, grats to our Div.1 winners:

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +468
  • Vote: I do not like it  

By Endagorion, 2 years ago, translation, In English,

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

496A - Minimum Difficulty

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

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

496B - Secret Combination

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

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

496C - Removing Columns/497A - Removing Columns

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

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

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

496D - Tennis Game/497B - Tennis Game

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

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

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

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

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

496E - Distributing Parts /497C - Distributing Parts

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

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

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

497D - Gears

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

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

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

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

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

497E - Subsequences Return

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

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

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

  • ε — (0, 0)

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

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

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

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

  • ...

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

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

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

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

Challenge: solve the problem for k ≤ 100.

Read more »

 
 
 
 
  • Vote: I like it  
  • +336
  • Vote: I do not like it  

By Endagorion, 2 years ago, translation, In English,

Hi, Codeforces.

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

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

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

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

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

UPD: the round is over, thanks for participating!

Grats to the winners:

Div. 1:

  1. Baz93

  2. Petr

  3. rowdark

  4. anta

  5. marcin_smu

  6. Merkurev

  7. qwer

  8. Ra16bit

  9. kuviman

  10. Um_nik

Div. 2:

  1. SergeyMelnikov

  2. sepehr103

  3. StarCuriosity

  4. Sern

  5. husheyn

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +595
  • Vote: I do not like it  

By Endagorion, 2 years ago, translation, In English,

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +62
  • Vote: I do not like it  

By Endagorion, 2 years ago, In English,

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

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

465A - inc ARG

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

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

465B - Inbox (100500)

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

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

464A - No to Palindromes!

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

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

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

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

464B - Restore Cube

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

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

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

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

464C - Substitutes in Number

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

Suppose we know for some sequence of queries that digit d will turn into string td for every digit. Then string s = d1... dn will turn into td1 + ... + tdn (+ for concatenation). Denote v(s) numeric value of s. Then v(s) can be expressed as v(tdn) + 10|dn|(v(tdn - 1) + 10|dn - 1|(...)). So v(s) can be computed if we know md = v(td) and sd = 10|td| for all d. As we need answer modulo P = 109 + 7 we can store these numbers modulo P.

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

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

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

464D - World of Darkraft - 2

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

Denote number of earned coins as X, and number of earned coins from selling items of type i as Xi. Clearly X = X1 + ... + Xk, and EX = EX1 + ... + EXk (here EX is expectation of X). As all types have equal probability of appearance, all Xi are equal, so EX = kEX1. Now to find EX1.

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

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

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

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

464E - The Classic Problem

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

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

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

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

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

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

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +172
  • Vote: I do not like it  

By Endagorion, 2 years ago, translation, In English,

Hi all.

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

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

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

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

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

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

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

Grats to all the winners:

Div. 1:

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

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

Div. 2:

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

Editorial is here.

Read more »

 
 
 
 
  • Vote: I like it  
  • +604
  • Vote: I do not like it  

By Endagorion, 4 years ago, translation, In English,

Hello everyone.

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

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

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +43
  • Vote: I do not like it  

By Endagorion, 5 years ago, translation, In English,

Hi, Codeforces.

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +30
  • Vote: I do not like it  

By Endagorion, 5 years ago, translation, In English,

155A - I_love_\%username\%

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

155B - Combination

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

155C - Hometask

154A - Hometask

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

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

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

155D - Colliders

154B - Colliders

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

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

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

155E - Double Profiles

154C - Double Profiles

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

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

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

154D - Flatland Fencing

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

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

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

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

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

154E - Martian Colony

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

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +43
  • Vote: I do not like it  

By Endagorion, 5 years ago, translation, In English,

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

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

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

Round finished, thank you all for participating!

Results:

div1:

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

div2:

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

Editorial is finally up!

Read more »

 
 
 
 
  • Vote: I like it  
  • +321
  • Vote: I do not like it  

By Endagorion, 5 years ago, In Russian,

С подачи 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 = p1b1... pkbk, где все pi — различные простые числа и все bi натуральные (т.е. это каноническое разложение числа на степени простых). Тогда известно, что d(n) = (b1 + 1)... (bk + 1). Поделим d(n) на nε:

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

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

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

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

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +67
  • Vote: I do not like it  

By Endagorion, 5 years ago, translation, In English,

139A - Petr and Book

If the total number of pages doesn't exceed the number of pages for Monday, the answer is Monday. Otherwise we can substract the Monday number from total and go on to Tuesday. If Tuesday isn't enough, we subtract and continue to Wednesday, and so on. We are sure that no more than N weeks will pass, as at least one page is read every week. Complexity - O(N).

139B - Wallpaper

Unluckily, the translated statement was quite tough even tougher to understand than the original statement.

Say we fixed the roll type and the room. The only possible way to cut the roll is to cut it into vertical stripes with length equal to room's height (though it was said we can cut it any way we want, there were some conditions to fulfill, namely there could be no joints other than vertical). So we find the total width of stripes we can cut our roll into as the (length of the roll / height of the room) (rounded down) * (width of the roll). If the roll length is smaller than room height, we obviously can not use this type of rolls (though the statement said there must exist at least one type we can use). The number of rolls is (perimeter of the wall rooms) / (total stripes width) (rounded up).

Then we just try all types for every room and sum the minimal costs. Complexity - O(MN).

139C - Literature Lesson

138A - Literature Lesson

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

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

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

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

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

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

139D - Digits Permutations

138B - Digits Permutations

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

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

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

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

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

139E - Mushroom Gnomes - 2

138C - Mushroom Gnomes - 2

First of all - the answer is the sum for all mushrooms of the probabilities of not being destroyed multiplied by that mushroom's power. That is a simple property of random variables' means.

So we come to the equivalent statement: we still have mushrooms, but now instead of trees we have a family of segments with probabilities arranged to them. Every segment "exists" with this probability, otherwise it doesn't, and all these events are independent. We want to count the sum of probabilities (with weights) for each mushroom not to lie in any "existing" segment. (Note that we can reformulate the statement this way because any segments containing any fixed point are truly independent: they can't belong to the same tree. Thus the probability to survive for any point in this statement is equal to the probability for this point in the original statement).

Now, how do we count this? There are several ways:

1) "Scanning line". If we go from left to right, we can meet three kinds of events: "the segment i started", "the segment i finished", "the mushroom j found". We can easily support the probability of current point being covered by "existing" segment if we multiply it by segment's probability when we find its beginning and divide by it if we find its end. If we find a mushroom by the way, we can add the known probability to answer (multiplied by its power). To perform the above trick we just sort the array of events by x-coordinate and iterate over it.

This solution is good in theory, but in practice it has a flaw: if the number of segments is large, after multiplying lots of real numbers less then 1 we can exceed the negative explonent of the real type used, and thus get a 0 in a variable instead of desired value. And after any number of divisions it still would be 0, so we couldn't get any sane answer anymore.

This trouble can be resolved in several ways (without changing the solution much):

a) We can have no more than 101 distinct values of probabilities for segments. So, if we store an array for quantities of segments containing current point and having a corresponding probability, we just add and substract 1's from array's elements. When we find a mushroom we find the product of degrees with exponents stored in array, spending ~100 operations.

b) We can store a set of segments containing current point. Every operation with set works in O(log N) time, and iterating over the whole set works in O(N) time. So, upon meeting mushroom we iterate over set and multiply the probabilities for all segments in it.
The next thing that helps us is that we can drop the answer for current mushroom if it's too small. If we don't store the segments with probability 1, the most number of segments which probabilities' product more than 1e-8 is about 2000 (since 0.99 ^ 2000 < 1e-8). So we can count everything in time.

c) If we use logs of probabilities instead of themselves, we have to add and substract them instead of multiplying and dividing. This way we won't encounter any precision troubles.

2) Segment tree.

Let's sort the mushrooms by their coordinates. Let's also assume we have some set of segments and already counted the desired probabilities. And now we want to add a new segment to the set. What will change? The probabilities of mushrooms lying in this segment (and thus forming a segment in the array) will multiply by segment's probability.
Now it's clear we can use multiplication segment tree (or simple addition segment tree if we use logs again) to perform the queries for all segments and then sum up the elements in the end.

About the strange score and pretest: we discovered the trouble with precision quite late, and realized that it makes the problem way harder ('cause it's hard to predict during writing and submission phases). What's worse, it won't show itself on the small tests. So we decided to "show up" the test and let the contestants solve this additional problem, for additional score. (However, not all solutions from above list do actually deal with this problem. Unfortunately, we didn't came up with them beforehand.)

138D - World of Darkraft

Notice that the game can be separated into two independent: for only even and only odd coordinate sum cells. The player chooses the game he would like to make a move in. Thus, if we find a Grundy function for each of this games we can find the whole game result.

Now let's observe only even cells, for instance. We can prove that every diagonally connected piece formed during the game is constructed as the intersection of the field rectangle with some diagonally oriented semi-planes, with exactly one semi-plane for every orientation. Let's enumerate every possible edges of semi-planes, which obviously are some diagonals of the grid. Now we have an enumeration of all possible pieces - by four diagonals being "edges" of this piece.

Now we want to count the Grundy function for some piece. To do this we iterate over all cells in this piece and find XORs of all Grundy functions of pieces formed by making a move in each cell, then find a minimal exclused non-negative number of this set (see the page on the Sprague-Grundy theorem above). All these pieces are smaller than current, so we can use the DP to count the functions. To easily iterate over cells in the piece we can iterate over numbers of two diagonals the cell lies on (going right-and-upwards and right-and-downwards), as we have exactly the bounds on their numbers as the parameters of the piece. For each case of diagonals we also have to check if the piece is inside the field.

So we have counted the Grundy functions for even- and odd-numbered cells separately. If they are equal, the answer is "LOSE", otherwise it's a "WIN" (see the theorem again).

Complexity - O((n + m)4 (number of pieces) mn (number of pieces inside one piece and counting MEX)).

138E - Hellish Constraints

The most interesting problem. =)

Let's start with the case when we have only one constriction - "c l r". For a string s let's count an array A with a length equal to s's. A[i] = 1 if the suffix of s starting at position i satisfies the condition, and A[i] = 0 otherwise.

So, we have s and already counted A. What happens if we write another symbol c' at the of s? Let s' = s + c', A' = A(s').

If c' ≠ c, than the part of A' corresponding to everything beside the last symbol does not change. The last element is 1 or 0 depending on the condition (it's easy to count).

If c' = c, some elements of A might change. Let's denote the i-th occurence of c in s' counting from the end as pi(c) (symbols and occurences are enumerated from 1). If there are less then i occurences, pi(c) = 0.

It's easy to see that elements from A'[pl + 1(c) + 1..pl(c)] are incremented by 1, and elements from A'[pr + 2(c) + 1..pr + 1(c)] are decremented by 1. It's also clear that as we add the symbols these invervals won't intersect for l and r separately (that is, every A[i] will be incremented and decremented not more than one time each).

Now we can have more then one constriction. We count B[i] as the number of constrictions the suffix starting at i-th position satisfies. Clearly, B[i] is the sum of A[i]'s for all constrictions. Also, we support the variable C - number of i-s that satisfy L ≤ B[i] ≤ R.

Similarly, we add symbols one after another and change B[i]. To do that, we must consider all the constrictions concerning new symbols and change the numbers in the intervals mentioned above. Changing the numbers is just iterating over symbols in the mentioned intervals and incrementing/decrementing B[i]'s (this procedure also lets us to support C effectively). As the intervals for each constriction do not intersect, we will not change any B[i] more than twice for each constriction, so the number of operations concerning any constriction is O(n), giving total number of operations O(nk). To get the answer, we just sum up C's states after adding every symbol (as every substring will be a suffix of some prefix exactly one time).

To find borders of every interval used (in which the B[i]'s are changed) we can enumerate all occurences of every symbols and count the borders easily, knowing how many times every symbol occured. The other way to do that is to keep two pointers for each constriction, showing where last intervals ended. On the next occurence we move these pointers to next occurences of corresponding symbol (however, we need to handle the case when not enough symbols have occured to changed B).

Read more »

 
 
 
 
  • Vote: I like it  
  • +68
  • Vote: I do not like it  

By Endagorion, 5 years ago, translation, In English,

Hello.

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

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

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

Score distribution:

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

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

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

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

Wish you luck. Have fun during the contest and show your best.
Happy new year! =)

UPD:
Round finished. Thanks everybody! Hope you enjoyed it.
Winners:
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

Due to some techinical problems, server was unavailable for few minutes before the end of the contest. Out of two unpleasant options: make the round unrated or stay as it is, we choose the second one as it affects the less number of contestants. We apologize to those participants who are affected by this.

UPD2: Editorial is finally translated.

Read more »

 
 
 
 
  • Vote: I like it  
  • +227
  • Vote: I do not like it