meret's blog

By meret, 9 years ago, In English

A. Ice Skating

Notice that the existence of a snow drift at the point (x, y) implies that "if I'm on the horizontal line at y then I am certainly able to get to the vertical line at x, and vice versa". Thus, the snow drifts are the edges of a bipartite graph between x- and y- coordinates. The number of snow drifts that need to be added to make this (as well as the original) graph connected is the number of its connected components reduced by one.

B. Blackboard Fibonacci

If you look at the described process backwards, it resembles the Euclidean algorithm a lot. Indeed, if you rewinded a recording of Bajtek's actions, he always takes the larger out of two numbers (say

Unable to parse markup [type=CF_TEX]

) and replaces them by a - b, b. Since we know one of the final numbers (r) we can simply check all numbers between 1 and r and run a faster version of Euclid's algorithm (one that replaces a, b by ) for all possibilities for a total runtime of . This was one of the expected solutions.

However, with some insight, it can be seen that this optimization is in fact not neccessary — we can simply simulate the reverse process as described (replacing a, b by a - b, b) for all candidates between 1 and r and the total runtime of our algorithm will remain . The proof of this fact is left to the reader.

C. Formurosa

One of the major difficulties in this problem is finding an easily formulated condition for when Formurosa can be used to distinguish the bacteria. Let Formurosa's digestive process be a function F(s) that maps binary sequences of length m to elements of {0, 1}. It turns out that the condition we seek for can be stated as follows:

We can distinguish all the bacteria if and only if there exists a sequence s of length m for which F(s) ≠ F( - s), where  - s is the negation of s.

First, not that if no such sequence exists, then there is no way to distinguish between zero and one. If such a sequence exists, we can pick any two bacteria a and b and try both ways to substitute them for 0 and 1 in the expression. If the two expressions evaluate to different values, we will determine the exact types of both bacteria. Otherwise, we will be certain that the bacteria are of the same type. Repeating the process for all pairs of bacteria will let us identify all the types (since it is guaranteed that not all bacteria are of the same type).

To determine whether such a sequence s exists, dynamic programming over the expression tree of Formurosa can be applied. The model solution keeps track for each subtree G of the expression which of the following sequences can be found:

  • a sequence s such that G(s) = G( - s) = 0
  • a sequence s such that G(s) = G( - s) = 1
  • a sequence s such that G(s) ≠ G( - s)

D. Bitonix' Patrol

Observation 1.

Fuel tanks for which capacity gives the same remainder are equivalent for Bitonix's purposes. Moreover, fuel tanks for which the capacities' remainders sum to D are also equivalent. Out of every group of equivalent tanks, the agency can only leave at most one.

Observation 2.

If more than six tanks remain, Bitonix can certainly complete his patrol. Indeed, let us assume that 7 tanks were left undestroyed by the agency. Out of the 128 possible subsets of those tanks, at least two distinct ones, say A and B, sum up to the same remainders modulo D. Thus, if Bitonix moves forward with tanks from A - B and backwards with tanks from B - A, he will finish at some station after an actual journey.

Because of observations 1 and 2, it turns out that a simple recursive search suffices to solve the problem. However, because of the large constraints, it may prove necessary to use some optimizations, such as using bitmasks for keeping track of what distances Bitonix can cover.

E. Alien DNA

Note that it is easy to determine, looking at only the last mutation, how many letters it adds to the final result. Indeed, if we need to print out the first k letters of the sequence, and the last mutation is [l, r], it suffices to find out the length of the overlap of segments [1, k] and [r + 1, 2r - l + 1]. Say that it is x. Then, after the next to last mutation, we are only interested in the first k - x letters of the result — the rest is irrelevant, as it will become "pushed out" by the elements added in the last mutation. Repeating this reasoning going backwards, we shall find out that we can spend linear time adding letters to the result after every mutation, which turns out to be the main idea needed to solve the problem.

For a neat O(n2 + k) implementation of this idea you can check out ACRush's solution: 2029369.

The only other contestant to solve the problem during the competition, panyuchao, used a slightly different approach, based in part on the same idea. Check out his ingenious, astonishingly short solution here: 2028007.

Read more »

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

By meret, 9 years ago, In English

Welcome to Codeforces Round #134!

After over two years, it is again my great pleasure to be the main problemsetter of a contest on Codeforces. Thanks a lot to Gerald for helping me organize the round. I hope you will enjoy solving the problems as much as we enjoyed preparing them for you.

Dynamic scoring will be used, but the problems will be ordered by their expected difficulty, from easiest to hardest. Are our predictions correct? I am eager to see. :-)

Good luck!

Update: The contest is over! Here are the results:

First division:

  1. rng_58

  2. panyuchao

    pieguy

  3. tourist

  4. Petr

  5. ACRush

  6. Zhukov_Dmitry

All contestants from the top seven solved three problems. Note that there was a tie for second place. :-)

Second division

  1. dsbuaa

  2. hqztrue

  3. Gullesnuffs

In second division, seventeen contestants solved four problems. Nobody managed to crack E; it was also present in the first division as problem C, and proved tricky even for the experienced competitors.

Congratulations to the winners!

Read more »

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

By meret, 11 years ago, In English
Let me warmly welcome you to Codeforces Beta Round #11. I am the main problemsetter for this contest. I hope you'll have fun solving the prepared tasks :-)

Thanks to Mike Mirzayanov for making this possible and to Ania Piekarska for testing the problems.

Good luck,
Jakub Pachocki

Read more »

Announcement of Codeforces Beta Round #11
 
 
 
 
  • Vote: I like it
  • +30
  • Vote: I do not like it