Hello!

Welcom to the todays round! Note that this is last possibility to training before VK Cup on Codeforces — don't miss your chance! I hope, everybody will find interesting problems for him, you will not have misunderstanding with statements and there will have a harmony beteen your your solutions and our tests.

I'm an author of todays round. My name is Valeriy Samoylov, a graduated student of SPb SU. I want to thank Artem Rakhov (RAD) and Gerald Agapov (Gerald) for great help in investigation of problems.

And so I want to thank Maria Belova for translation of the statements and Alexanber Kouprin (Alex_KPR) for the statement prereading and the picture =)

Please, pay attantion to unusual problems cost in the first division:

500 — 1000 — 1500 — 2500 — 2500

And without surprise in the second division:

500 — 1000 — 1500 — 2000 — 2500

Good luck for all!

Round is postponed to 30 minutes by technically reasons. Registration is ending in 21:25.

Overview

The VK Cup Championship is an open computer programming competition that is held by VK, Codeforces and Saratov State University. VK is the largest European social network with more than a 100 million active users. The Championship Final Round will be held in July in St. Petersburg. Top 50 contestants of the Round 3 will be invited to the Finals, with trip expenses covered by the organizing committee.

Eligibility

You are young and you like to solve programming problems? Then this championship is for you! Anyone meeting the following criteria is eligible to compete in the VK Cup:

• must be at least 14 years and at most 23 complete years of age (by the moment of registration);
• current employees of VK and/or members of organizing committee/jury are ineligible to participate in the VK Cup;
• must be eligible for participation in Codeforces contests.

Thus, the intended audience of the championship are mainly high school and university students. To participate in the championship, you have to register beforehand.

Only individuals are allowed to take part in the Championship. No teams, no joint discussions and etc.

Anybody feels like sharing the thoughts about Challenge24 online round? Like who was in which team and who solved what? I miss the detailed information — participants' countries and total points earned is too little :-)

Here is the list of teams known so far:

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. YuukaKazami
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!

Here goes a review of the problems. I tried to set them so that each of them shows a certain aspect of the language — a commonly used verb or a specific feature. Once it was recognized and found, the solution should become evident.

153A - A + B

Let me note right away that the sample code provided in the blog post does work both in Custom test and in ideone (as well as locally), as long as the numbers are written one per line and (attention!) each of them, including the last one, is followed by the end-of-line character. The last '\n' is not shown in the tests, but it is there, and COBOL minds it. All test cases at Codeforces are generated with this in mind, so there should be no problems like this when the code is submitted.

The most evident COBOL feature is storing numbers in decimal notation, with width set by the programmer. In this case we focused on the fact that by default the number is printed in a fixed-width way, padded with leading zeros if needed. These zeros where what you needed to get rid of.

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!