Good day!

We are glad to introduce you regular Codeforces round for Div.2 participants. Everyone can traditionally participate in it.

Problems are prepared by Kholkin Pavel (HolkinPV), Rakhov Artem (RAD) and Nikolay Kuznetsov (NALP). Also thanks to Michael Mirzayanov (MikeMirzayanov) for perfect system, Mary Belova (Delinur) for translating problems and Agapov Gerald (Gerald) and Alexander Kouprin (Alex_KPR) for their help.

We decide to tell you some secret about todays problems. To solve them, you wiil propably use sort algorithm)

Score distribution is standard: 500, 1000, 1500, 2000, 2500.

We wish you success and high rating!

UPD: The contest is over, the tutorial will be here soon.

UPD2: Thanks everyone for participation. We hope you enjoy your problems. Congratulations to the winners:

1. Touma_Kazusa
2. ZJUT_AA
3. wwhd
4. jikwao425
5. wtiger9999
6. Jolin
7. anmtcel
8. marspeople
9. ztxz16
10. CrazyRabbit

Special congratulation to Touma_Kazusa, who solves all problems of the round.

Hi everybody!

Let me remind you that on the 3rd of March, at 20:00 the first qualification round of the VK Cup 2012 championship will start.

You need to participate in at least one qualification round to make it to Round 1. Contestants who gain a score equal to the 800-th place finisher score or greater will advance to the Round 1. If you won't participate in the Qualification Round 1 or if you failed to advance to Round 1 by its results, than that's not a problem — you can have a try at the Qualification Round 2 on March, 9.

At each qualification round you will find a few simple problems, roughly ordered by the increasing complexity. During the qualification rounds the problems are judged only on pretests and system testing will take place after the end of the qualification round (round continues for 24 hours). The pretests do not cover all possible cases of input data, test your programs carefully! The qualification rounds have no hacks or decreasing values of the problems.

The round will last for 24 hours, but it does not mean that we encourage you to spend all this time solving of problems. We hope that most participants will cope with the problems (or with most problems) in a shorter period of time. This duration of the round is chosen so that each participant could find a convenient time to participate.

Before the end of the round it is strictly forbidden to publish the problem statements/solutions/any thoughts and ideas about them elsewhere. It is forbidden to talk about the problems, discuss the statements and so on. Be honest and let the best men make it into Round 1. When the Qualification Round is over, you can discuss the problems and solutions.

You can register for the round at any time up to its end. Yes, we had a false start with registration of the qualification. We haven't switched on the Championship participant registration check function. If someone managed to register to the round on the 2nd of March, please do it again.

The results of the round will not affect the rating, non-competitive participation in the round is not allowed. However, all tasks will go to the archive after the end of the round.

Best of luck and enjoy solving the problems!

UPD: The round is over. 12907 submissions to be judged on system tests!

UPD 2: System testing completed, the final results are available.

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.