Endagorion's blog

By Endagorion, 4 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, 5 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, 5 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, 5 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, 5 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, 5 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, 6 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, 7 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, 7 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, 7 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, 8 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, 8 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, 8 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