The round is over, I hope you have enjoyed it. Here is the editorial.

The language of this round is COBOL (dialect COBOL85), one of the oldest programming languages (date of “birth”: 1959, so it’s twice older than I am). Despite being so old, it’s still in active use, though not in programming competitions, so I think it should be enough of a surprise for you :-)

The problem "A+B" (numbers A and B given in separate lines) can be solved in a following way:

       IDENTIFICATION DIVISION.
       PROGRAM-ID. SOLUTION.

       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01 A        PIC 9(10)   VALUE ZEROES.
       01 B        PIC 9(10)   VALUE ZEROES.
       01 STR      PIC X(10).

       PROCEDURE DIVISION.
         ACCEPT STR
         MOVE STR TO A
         ACCEPT STR
         MOVE STR TO B
         ADD A TO B
         DISPLAY B
         STOP RUN.

152A - Marks

In this problem you should do exactly what is written in the statement. Here is rough code of solution:

for (int i = 0; i < n; ++i){   
    bool wasBest = false;
    for(int j = 0; j < m; ++j){
        bool isBest = true;
        for(int k = 0; k < n; ++k)
            if(a[k][j] > a[i][j])
                isBest = false;
        if(isBest)        
            wasBest = true;
    }
    if(wasBest)
        ans++;
}      

152B - Steps

Let's find a formula for the position (x, y) and vector (dx, dy), how many steps to stop the boy can do. You should use "almost" binary search, for example, see the code written by RAD.

for (long long cof = 1100000000; cof; cof /= 2)
    while (onField(xc + cof * dx, yc + cof * dy)) {
        xc = xc + cof * dx;
        yc = yc + cof * dy;
        ans += cof;
    }      

152C - Pocket Book

In this task, it was necessary to understand that in position 1 Vasya can get any name of a special form. More exactly, it's the name of form s = s₁ s₂ s₃ s₄ ... s_m, where s₁ — the first letter of any of the names, s₂ — the second letter of any of the names, ... s_m — m-th letter of any of the names. Then the answer to the problem is the product of cnt_i (1 ≤ i ≤ m), where cnt_i is a number of different letters in the names placed in position i.

152D - Frames

It was necessary to understand if there are two borders or not.

Let's distinguish those x — and y-coordinates, in which there are at least 3 consecutive symbols '#', becouse the length of each border is no less then 3. It is clear that the coordinates of the corners of borders should be chosen only from those selected x and y. In general, the various selected x no more then 4 and various selected y no more then 4.

Except that case when the height or width of the first border is 3, and length of the second side of this border is more than 3, and one side of the second border fills a part of the inside first at least.

For example:

#######
#######
#######
#.....#
#######

The first border:

#######
#.....#
#######
.......
.......

The second border:

.......
#######
#.....#
#.....#
#######

There are 7 different y-coordinates in the example.

Carefully processed these cases separately, it is quite simple. (Let's choose 4 y-coordinates: minimum, maximum, second minimum and second maximum).

Otherwise, if the amount selected x — and y-coordinates no more then 4, then let's choose opposite corners of the first and second borders and verify that the selected borders — the correct borders and there are no other characters '#'. Checking is carried out at O(n + m) or O(1) (using partial sums).

152E - Garden

The solution of this problem is based on dynamic programming. dp[mask][v] — the value of the minimum correct concrete cover, if we consider as important elements only elements of the mask mask, and there are additionally covered the vertex v = (i, j) of the field.

There are two types of transfers.

First of all we can, as if to cut coverage on the vertex v. Then you need to go through subpattern of vertex submask, which will go to the left coverage and make an optimizing transfer. Update dp[mask][v] with the value dp[submask][v] + dp[mask ^ submask][v] - cost(v).

Second, perhaps in the vertex v in the optimal coverage mask mask, which covers the vertex v, you can not make the cut separating the set of vertices. In this case, this vertex forms something a kind of <>. And there a vertex u exists, on which we can make the cut, with the whole shortest path from a vertex u to v belongs to the optimal coverage. Let's precalculate the shortest paths between all pairs of cells. Now to make this transition, we should count the value of dynamics dp[mask][v] for all vertices v only on the basis of the first transition. Now you can make the second transition. For all u, dp[mask][v], update the value of dp[mask][u] + dist(v, u) - cost(u).

Let's process separately state in which exactly one bit in the mask, and the vertex which corresponding to this bit is equal to v. In this case the answer is equal to cost(v), of course.

Thus, each solution is obtained for the O(min(3^k·n·m, 2^k·(n·m)²)).

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!