Good day!

We have got over two weeks of our new term. And we are glad to see you on our regular rating Codeforces round for Div.2 participants. And all who wants can take part in this competition.

This round has been prepared by a team of three people: Gerald, NALP and Polichka. We are grateful for their help in preparation and translation to Artem Rakhov(RAD), Mike Mirzayanov (MikeMirzayanov) and Maria Belova(Delinur).

Today Peter entangled in the tables:-( And you can help him! It's rather easy!

Score distribution: 500-1000-1500-2500-2500

Easy solutions and high rating to all!

UPD:

Thanks all for participation!

You can read the tutorial on this link: Tutorial.

150E - Freezing with Style

1. If there exists a path with the median  ≥ k, for some k, then there exists a path with the median  ≥ q, for each q ≤ k. That means we can use binary search to calculate the answer. So now the task is: is there any path with the median greater or equal to Mid ?

2. We will calc the edge as  + 1 if it's wight  ≥ Mid, or as  - 1 in other case. Now we only need to check if there exists a path with legal length and the sum greater than or equal to zero.

3. Let's denote some node V as a root.

4. All paths can be divided into two types: that contains v, and that do not. Now we are to process all first-type paths and run the algorithm on all subtrees. That is so-called divide-and-conquer strategy.

5. We can trivially show that it is always possible to choose such vertex v that all it's subtrees will have size less than or equal to the size of the whole tree. That means that each node will be proccessed in LogN trees max.

6. So, if we solve the task for one level of recursion in O(F(N)), we'll solve it in time O(F(N) * log²(N)) on the whole.

7. First, lets get O(N * Log(N)). For each node we shall calc it's deepness, cost of the path to the root ans the first edge (the number of the root's subtree). It will be better now to use 2 and 0 as the edges costs, instead of -1 and 1. Now we shall process root's subtrees one by one. For each node we want to know if there exists a node u in any other subtree such that the

   Unable to parse markup [type=CF_TEX]

   and cost[v] - deep[v] + cost[u] - deep[u] ≥ 0. To do that we need to know the maximum of the function (cost[u] - deep[u]) with the deep values between max(0, L - deep[v]) and R - deep[v] inclusive. To achieve O(N * log(N)) you need only to use segment tree.

8. To achieve an AC contestants were to write all code optimally, or to think of one more idea. It is possible to have O(N) on one level of recursion and O(N * log²(N)) in total if you sort roots subtrees in non-decreasing order and use any structure that can answer getmax query on all segments of length (R - L + 1) and all prefixes and suffixes.

Best of luck to you in upsolving this problem!

150D - Mission Impassable

In this problem you have to use dynamic programming. For our convenience we will calulate three type of values:

Best[l][r] — best result player can achieve on the segment [l, r].

Full[l][r] — best result player can achieve on the segment from [l, r] if he fully destroys it.

T[l][r][Len] — best result player can achieve on the segment from [l, r] and remain the palindrome of length len and only it.

Now solution:

1. Full[l][r]. Let's look which move will be the last. This will be removing the palindrome of length len and c[len] ≥ 0. What is the best result we can achieve? c[len] + T[l][r][len].

2. Best[l][r]. Either we will destroy all subtring from l to r, either there exists a letter which we did not touch. That means that all our moves lies fully to the left or fully to the rigth to that position. So Best[l][r] = Full[l][r] or Best[l][r] = Best[l][m] + Best[m + 1][r] for some m, l ≤ m < r.

3. T[l][r][len]. len = 0, len = 1 — two special cases, which is easy to solve without any dynamic. In other case, let's take a look on the left-most position. It either will lie in the result string or not. If not, then let's find the first position which does. Denote it as m (l < m ≤ r). Everything what lies to the left need to be fully deleted. So the answer is Full[l][m - 1] + T[m][r][len] (for l < m ≤ r). Similarly, for the right-most letters. If it does not lies in the result string we remove everything to the right and our result is T[l][m][len] + Full[m + 1][r] (for l ≤ m < r). The last option: both left-most and rigth-most letters lies in the result string. It is possible only if s[l] = s[r]. So our result is T[l + 1][r - 1][len - 2] (only if s[l] =  = s[r]).

150C - Smart Cheater

1. First lets use the linearity of expected value and solve task independently for each passanger.

2. For each path segment (route between neighboring stations) we calculate expected value of profit in case we do not sell a ticket for this segment. In case we sell it the expectation of profit is 0.

3. Now we only need to find the subsegment of segment [a, b] of maximal sum for each passanger.

4. That's easy to do by the segment tree, we only need to calc four values for each node:

best — the maximal sum of elements on some subsegment

max_left — the maximal sum on prefix

max_right — the maximal sum on suffix

sum — the sum of all elements

150B - Quantity of Strings

We can offer you two solitions:

1. You can build a graph with positions in sting as a nodes and equality in any substring of length k as edges. Lets denote e the number of components in the graph. The answer is m^e.

2. Analyze four cases:

   • k = 1 or к > n, the answer is mⁿ.
   • k = n, the answer is m^{(n + 1) / 2}.
   • k mod 2 = 1, any string like abababab... is ok, so the answer is m².
   • k mod 2 = 0, all symbols coincide and the answer is m.

150A - Win or Freeze

• if Q is prime or Q = 1 than it's victory.

• We loose if: Q = p * q or Q = p², where p and q are prime.

• It is quite obvious that it is always possible to move in bad position in any other case. That means all other numbers grants us the victory.

We only have to check if Q has a divisor of the loose type. We can easily do it in O(sqrt(Q)) time.

151B - Phone Numbers

In this task you were to implement the described selection of the maximum elements.

151A - Soft Drinking

Soda will be enough for gas = (K * L) / (N * l) toasts.

Limes will last for laim = (C * D) / N toasts.

Salt is enough for sol = P / (p * N) toasts.

Total result: res = min(gas, laim, sol).

Hello everybody!

Today's round will be held by SergeiFedorov and me. We have done our best to make it diverse (different task complexity and themes) and rated (we know it's important). Your questions, wishes and constructive criticism (destructive we already can do :-)) leave in comments.

The contestants will plunge into the cold February of Nvodske and will be to help one's friends to survive the cold. Just imagine all responsibility!)

On this occasion I would like to thank all Codeforces team for the great job, they are doing, Artem Rakhov (RAD) for his help in task preparations, Maria Belova (Delinur) for problems translation, my mom, my dad, our soundman and Tuscany winemakers, for us didn't fall ill while preparing this round.

Distribution will be something like:

div. 1: 500-500-1000-1500-3000 (yeah, it really costs 3000)

div. 2: 500-1000-1500-1500-3000

Good luck & have fun!

149A - Business trip

First, it is clear that if the sum of all numbers a_i is less than k, then Peter in any case will not be able to grow a flower to the desired height, and you should output <<-1>>.

Secondly, it is easy to see that if we want to choose a one month of two, in which we watered the flower, it is better to choose one where the number of a_i is more. Thus, the solution is very simple: let's take months in descending order of numbers a_i and in these months water flowers. As soon as the sum of the accumulated a_i becomes greater than or equal to k — should stop the process, the answer is found.

149B - Martian Clock

In this task required only the ability to work with different numeral systems. Let's try to go through numeral bases, each base to check whether it is permissible, as well as convert hours and minutes to the decimal system and compared with 24 and 60, respectively.

What is maximal base, that we need to check? In fact, it is enough to 60, because 60 — upper limit on the allowable number. It follows from the fact that if the number in an unknown number system consists of one digit, then its value in decimal not ever change, otherwise its value is not less than the base.

It is also worth to consider the case with the response <<-1>>, for this example, you can check a big base, such as 100, and even if the time for him correct, then for all large, it is also correct and the answer is <<-1>>.

149C - Division into Teams

Sort all the boys on playing skill. Then, if we send in the first team all the boys standing in a sorted array for odd places, and the second — even standing on the ground, then all requirements for division executed.

The first two requirements are obviously satisfied.

To prove the third we consider the geometric representation: Let each child designated point on the X axis with a value equal his playing skill. Connect the points with segments numbered 1 and 2, 3 and 4, and so on. If n is odd, then join the last point with the nearest the previous one.

Obviously, all these segments don't intersect in pairs, except at the points, and their total length is equal to the difference amounts to play boys' skills contained into the first team and second team. It is also clear that all of these segments completely contained in the interval [0, max(a_i)], as well as the pairs are a length of zero crossing, the third requirement is satisfied, which we proved.

149D - Coloring Brackets

We introduce the notation of colors: 0 — black, 1 — red, 2 — blue. Note that a single pair of brackets has 4 different coloring: 0-1, 1-0, 0-2, 2-0.

Consider the dynamic programming, where the state is (l, r, c_l, c_r), where the pair (l, r) defines a pair of brackets, and c_l and c_r denote a fixed color for them. The value of the dynamic is a number of ways to paint all the parenthesis brackets inside the interval (l, r) in compliance with all conditions.

We write down all the pairs of brackets that are directly placed into a pair of (l, r), let k of their pieces. Moreover, we consider only the first level of nesting, it is directly attached.

In order to calculate the value of the dynamics for the state, within this state shall calculate the another dynamic, where the state is a pair (i, c) which means the number of correct colorings of the first i directly nested parentheses, and all inside them, if the latter closing bracket has a color c. Calcing the values of this dynamic is very simple, let's try to paint a (i + 1)-th parenthesis in one of four variants, but you should keep in mind possible conflicts. In such dynamics the initial state is a pair (0, c_l), and the final result is sum over the states of the form (k, c), where c must not conflict with the c_r.

The answer to the whole problem may be calced as the internal dynamic. Time of solution — O(n²) by a factor of about 12.

149E - Martian Strings

We will solve the problem separately for each m strings. Thus, suppose we have a string p, its length is l, and we need to check whether the Martian be seen.

We introduce additional arrays: let pref[i] is minimal position in the s of the begin of occurrence p with length exactly i, and let suff[j] is the maximum position in the s of the end of occurrence p with length exactly j

It is easy to understand that a Martian could see the p, if there exists an i, that suff[l - i] ≥ pref[i] + l - 1.

How to calculate the arrays? For pref array is sufficient to find Z-function p#s, but for an array of suff — Z-function r(p)#r(s), where r(t) means the reversed string t. Using an array of Z-functions calcing of arrays suff and pref is trivial.

Hello everybody!

Today Codeforces Round # 106 for Div2 participants will be. And all who wants can take part in this competition. You will have the opportunity to break from parents with Peter, to learn some interesting facts about the Martians and to solve, of course, interesting problems for you as we hope.

This round has been prepared by a team of three people: Gerald, NALP и Polichka. We express our gratitude for their help to Artem Rakhov (RAD), Mike Mirzayanov (MikeMirzayanov) and Maria Belova (Delinur) .

Score distribution: 500-1000-1500-2500-2500.

Good luck and high rating to all!

A couple of days ago I was asked to answer the question "What is it like to be a problem writer for programming competitions?" at Quora web-site. My first idea of the answer had only one word, but then I've thought of a more detailed one, and then of a story I must include, hmm, and I should definitely mention this... Around the second page I realized that this is becoming more than an answer, and at the third one I decided to share this article with a qualified audience — that would be you.

So, what is it like to be a problem writer for programming competitions?

In one word (the one I've thought of at first), it's "awesome". In a bit more detail, "hard, sometimes unrewarding, but anyways fascinating job". In even more detail...

So, here goes the editorial. I'll tell you right away that nobody guessed MikeMirzayanov's problem (nice disguise, er?) — it was problem C about the picky princess. Actually, this was the first problem of the round, the rest of problems I invented to keep up the lovely topic.

148A - Insomnia cure

The number of dragons D can be quite small, so the problem can be solved in a straightforward way, by iterating over dragons 1 through D and checking each dragon individually. Time complexity of such solution is O(D).

Hello,

Codeforces Round #105 will take place on February 2nd, 20:00 Moscow time.

This is a themed round, based on the fairy tales I write in Russian.

In this round we decided to conduct an experiment on smoothing the effects of problem setters misestimating the complexities of the problems: all problems have point values of 1000. We tried to order the problems by increasing difficulty, but this is a subjective opinion, so surprises are possible.

Thanks to MikeMirzayanov for the problem contributed to the round (who can guess which one of the five is not mine?) and to RAD for his help in preparing the problems.

Good luck at the round!

Hi there. I invite you to participate in my contest. It will take place in Codeforces::Gym at 15:00 (Moscow timezone — UTC+4) (Time in other regions).

Problems are rather easy, so it will be more interesting for div2 participants.

** Warning: I have only russian statements. This contest is only for those who can understand russian statements.**

Good luck

Alexey freopen Zolotov

Since almost every member of the community Codeforces know how to write programs, we decided to abandon the wysiwyg HTML editor, and introduce a geek method. Of course, technical texts will gain much more convenient, and text will look uniform.

Now we use modified Markdown as a markup language for blog posts and comments. Since we use an additional extensions, we called markup simply Codeforces Markup. Codeforces custom tags are available in the editor, I will publish a description of the rest here a little later. In a few words it looks like simplified previous version — double square brackets are replaced by single square bracket.

In addition, we improved typography posts and comments.

See description Markdown using the links:

• http://en.wikipedia.org/wiki/Markdown
• http://daringfireball.net/projects/markdown/syntax
• http://bywordapp.com/markdown/syntax.html

Here's a short list of features:

1. insert user handle (use ~tourist);
2. italic and bold;
3. inline code — return a == 0 ? b : gcd(b % a, a); (place it between `);
4. numerated, unnumerated and nested lists;
5. headers;
6. autocorrection hyphens with dashes;
7. smart URL detection (makes them to be links) http://codeforces.com/;
8. tables and images;
9. source code highlighting;
10. "smart" quotes;
11. separate paragraphs with a blank lines;
12. special Codeforces tags;
13. insert photos like [photoalbum:PicasaPublicAlbumURL];
14. and much more!

I recall that on Codeforces implement preview, so you do not need crazy experiments on the Markdown in comments:)

MikeMirzayanov