Hey, folks!

I am not a fan of sport-programming t-shirts, but surely know that some of you would like to have one. If you wanna get a t-shirt, just add yourself in Google Form. After a couple of days I will pick a person randomly from the list, and contact him/her for contacts.

Also, I didn't decide how to calculate a random seed fair enough. So, feel free to propose something :)

Cheers!

Edit 1: Guys, please, don't mess around with the doc. Now you cannot edit the doc, please, add a comment with your handle.

Edit 2: Ok, you forced me to delete Google Doc, and spend more time, thanks :) Please, add you handle again in Google Form. Pay attention, you can only add your handle once. Make sure you wrote it correctly. Also to prevent cheating, I will chose among people who participated in at least 2 competitions.

Edit 3: Seems that everybody who wanted to participate in this put nickname in form. So, we can start the lottery.

I was super lazy, so I decided not to do anything complicated. I wrote python script:

#!/usr/bin/python                                                                                                                                                              
import random

filename = "input.txt"
times = 20

with open(filename) as f:
  lines = f.readlines()
  random.seed(314159265)
  for i in xrange(times):
    index = random.randint(0, len(lines) - 1)
    name = lines[index]
    print index, name[:len(name)-1]

Firstly, I picked 20 nicknames:

• 202 TooSchoolForCool
• 179 Hdz_78
• 202 TooSchoolForCool
• 259 LouisCK
• 18 serghov
• 324 krismaz
• 290 dutzul
• 188 Swift
• 86 Elk-cloner
• 233 TahaMahmoud
• 251 bnick
• 179 Hdz_78
• 168 muratt
• 107 heaton
• 6 zeulb
• 53 Prestige
• 157 bayram
• 242 Mohammad_Mohsin_COU
• 120 sampriti
• 199 gridnevvvit

Interesting that Mohammad_Mohsin_COU wrote his nickname in a wrong way, but I fixed it :)

Then I ran the same program with another filename and times=1. And the winner is: muratt. Congratulations to him!

Good evening!

The final contest of Coder-Strike 2014 will be started tomorrow at 16:00 MSK. The problems (as in previous Coder-Strike 2014 rounds) are prepared by: Gerald, HolkinPV, Igor_Kudryashov.

And we have good news for you. There are two rated online rounds related to the contest: one round for the first division participants and the other for the second division participants. Of course, we've added simple problems in the second division contest (and also deleted hard problems).

The registration for the contest will start at 4:00 MSK, as usual registration ends 5 minutes before the contest start. The first division participants should register on "Coder-Strike 2014 — Finals (online edition, Div. 1)", the second division participants should register on "Coder-Strike 2014 — Finals (online edition, Div. 2)".

Hope the problems will be nice for you, we are really tried our best to prepare them.

Good luck!

UPD. Due to the holding the onsite competition of Coder-Strike 2014, we have to restrict access to the site after the contest. Approximately, the site will be unavailable for 15-30 minutes after the end of the contest.

The editorial is now available.

Good day!

Coder-Strike 2014: Round 2 will start tomorrow at Russian morning. If you want to participate, please register for the contest on the page.

In much the same way as the first round, all users can take part in the competition. But this round will be usual rated round only for the second division participants. The first division participants can take part too, but for them the round will be unrated. Please, do not get upset, the next Coder-Strike round (finals) will be rated round for the first division participants.

If you have any additional questions, please, ask at comments.

Good luck, and see you on the contest!

UPD 1. Sorry for delay, the score distribution is standard.

UPD 2. The contest is over, congratulations to the winners, hope you like the problems!

Good Day!

Coder-Strike 2014: Round 1 will start very soon. If you want to participate, please register for the contest on page. The round was prepared by me, HolkinPV and Igor_Kudryashov. And we tried our best to make it really awesome.

The round will be usual rated round for the second division participants. The first division participants can take part too, but for them the round will be unrated.

If you have any additional questions, please, ask at comments.

Hope you enjoy the problems! Good luck!

UPD 1. Score distribution will be standard: 500-1000-1500-2000-2500.

UPD 2. The competition was delayed by 10 minutes. :]

UPD 3. Because of unusual room assignment Div.1 and Div.2 participants will be in the same rooms this round.

UPD 4. The contest has ended, hope you like the problems. Rating for Div.2 participants will be updated a bit later.

411A - Password Check

In the first problem you should correctly implement what was written in statement. It could be done like this:

string s;
cin >> s;
bool upper = false, lower = false, digit = false;
for(int i= 0; i < s.size(); ++i){
    if(isupper(s[i]))
        upper = true;
    if(islower(s[i]))
        lower = true;
    if(isdigit(s[i]))
        digit = true;
}
puts((upper && lower && digit && s.size() >= 5) ? "Correct" : "Too weak");

411B - Multi-core Processor

In this problem you should read the statement carefully, consider some principal cases and implement them in your program. The author's solution is:

1. We will store array$blockedCell[]$ (value in cell i equals 1 if this cell is blocked, 0 otherwise), blockedCore[]$ (value in cell i equals 0, if this core is not blocked and the number cycle when this core is blocked otherwise).
2. Consider all cycles from the first to the last. Consider the cycle number k.
3. Consider all processors and calc what cells will blocked on the cycle k. Set values one to corresponding cells of array blockedCell[]
4. Then for each core i if conditions blockedCore[i] = 0 and blockedCell[x[i][k]] = 1 meet then core i is blocked on cycle k. Set blockedCore[i] = k.

411C - Kicker

To solve this problem you should use logic (mathematic logic) :] Logic says:

1. If for some arrangement of the first team there is no arrangement to have even a draw then the first team is guaranteed to win.
2. If for any arrangement of the first team there is some arrangement for the second team when the second team wins then the second team is guaranteed to win.
3. Otherwise nobody is guaranteed to win. The answer is Draw.

This logic should be implemented in your program. I could be done considering each arrangement of every team.

Good day!

Codeforces will hold competition Coder-Strike 2014 for Moscow school children. Qualification Round of the competition will start soon. The round will be unrated for all participants.

As usually, anyone can enjoy the problems! If you aren't a Moscow school child you can take part in the round unofficially.

Hope you will enjoy our problems, good luck!

Testing Round #7 will start tomorrow on 28th of June 2013 at 00:00. Our goal is to test the platform after recent improvements. Recently, there have been many improvements / innovations. In particular, a large part of Codeforces was moved to another server.

I invite you to take part. It will be Div.2 + unofficials from Div.1. It will contain three obsolescent problems. But I think it will be interesting for many of you. I ask not to compete those who have been on a winter school in Kharkov this year — perhaps, you can know the problems. The problems contain very weak pretests to force more hacks. Of course, the round will not affect the rating.

Thanks to all who take part!

Upd. Round has finished successfully, great thanks to all participants!

Good Day!

The next Codeforces round will start soon. It will be held by usual Codeforces round rules.

The author of today's round is Mykhailo Granik (Fcdkbear), he is listening the lecture at the Winter Kharkiv Programming School now. Great thank him for this contest!

The score distribution will be standart: 500-1000-1500-2000-2500.

Good luck to all!

Good day!

For technical reasons, we've decided to move the start time of the online version of the round. Online version will be held as separate competition CROC-MBTU 2012, Final Round (Online version, Div. 2). Please register for this competition.

This round will be usual rating round for the Div. 2 participants.

UPD. The online version of the round will come soon. Let me remind you that this contest will hold by usual Codeforces rules. The score distribution is 500-1000-1500-1500-2000.

Enjoy contest!

Good day!

Elimination round of the CROC Collegiate Programming Competition for the MSTU Bauman students is going to be here soon. The official championship participants will take part in the competition, all others will be out of the competition in the table of results.

The contest is held by the well-known rules ACM-ICPC. Competition duration is 2:00 hours. Supported programming languages are C/C++, Pascal, Java, C#, Python, Ruby, PHP, Haskell, Scala, OCaml, and D.

This Round will be the rated for the Div-2 participants, regardless of whether one is the competition championship party or not. For Div-1 participants this round is unrated.

Please note that the official participants of the competition are not need to register for this competition they will be registered automatically (with advance registration at website).

Good luck to everyone!

UPD. Competition is completed, thank you very much for your participation! I hope that the problems with the queue is not much to spoil your impression of the contest. The results of elimination round for official participants will be announced tomorrow. Rating will be update soon.

Good day, Codeforces!

Please note that there have been significant changes in the schedule of competition! Competition Codeforces Round #148 rescheduled for Sunday, also added new competition Bayan 2012/13 Elimination Round.

The latter is an elimination for the BAYAN 2012/13, as it is sure to be a rated round for participants from Div1. The issue of rating for participants from Div2 currently being addressed. Do not pass by, registration starts now!

Please note that the competition Bayan 2012/13 Elimination Round will held by the ACM ICPC rules, and the statements of this competition will be available in English only.

Gain your strength before the upcoming competition! Good luck to all!

Good day, Codeforces!

I can't wait to give you a good news that a new competition for div1 participants is appeared in the list of events. This competition is a broadcast of the Saratov Team Olympiad on Programming and therefore will be held by the ACM-ICPC rules. Especially for div1 participants, we complicate this school competition a bit, so that everyone was interested to solve the problems.

This Competition is individual, it will be rated for both divisions.

Please note that the start time of the competition is different from the usual. Also note the unusual length of the competition.

See you at Codeforces Round #145! I hope that everyone will find the time to participate in the competition.

UPD. The competition finished, the editorial will come soon.

Good Morning, Codeforces!

Analyzing the task C (Div1), E (div2) I came to the conclusion that the author's solution is wrong, so I bring to you all a huge apology.

However it turned out all pretests were correct and there are only a few number of incorrect hacks (only 3). After discussing the situation with MikeMirzayanov we made ​​this decision:

• Problem E almost do not effect on contest results for Div2 participants (there are only a few number of submits and no hacks), so the contest will be rated for Div2 participants.

• The contest will be rated for Div1 participants, only if this problem have right and fast solution. I wasted all todays night (or morning) finding this solution. Therefore I propose to solve this problem by the community (if it's possible). If during the day, i.e. 24 hours after publishing this post, one cannot find solution, Div1 competition will be considered unrated.

Once again I bring you my apologies for this mistake. I hope that we will be able to master this problem together. Feel free to write all your ideas in this post, even some wrong idea may hint at the right solution. We would be very grateful to everyone who will take part in solving of that problem.

Note that this problem appeared in problemset. All tests are correct and you may try to solve it.

UPD: 24 hours have passed. Unfortunately, no one has written the correct solution, or close to it. Div1 round is declared unrated. Many thanks to all those who put their efforts and tried to solve this problem.

Best regards, Gerald Agapov.

Good Day, Codeforces!

Remember, that at 17:15 the final of the Open Moscow Programming Championship By CROC will start.

As usual anyone wishing to participate in this round can compete in it out of competition. But as this competition is quite complex, it will be rated only for participants from Div.1.

Note that this competition is closely connected with onsite competition in Moscow. So the starting time can be shifted. Watch closely for changes in the schedule.

Good day, Codeforces!

Today at 19:00 the Round 1 of the Open Moscow Programming Championship By CROC will start.

This is usual two-hour Codeforces round with hacks and decreasing values of problems. Everybody, who passed Qualification Round and registered for today’s round, has advanced to Round 1. The remain participants are allowed to participate in this Round out of competition. Round will be rated for everyone as usual. Contestants who gain a score equal to the 300-th place finisher score or greater will advance to the Round 2 (also you need to gain positive score).

You will find a few problems, roughly ordered by the increasing complexity. Score distribution is standard (500-1000-1500-2000-2500). During the Round the problems are judged only on pretests and system testing will take place after the end of the Round. The pretests do not cover all possible cases of input data, test your programs carefully!

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 2. When the Round is over, you can discuss the problems and solutions.

It seems that this Round could be a bit hard for Div2 participants. Don’t forget that rating will be calculated only for participants, who make at least one submit.

In today’s round preparation take part: Ripatti, havaliza, haas, RAD, Gerald, MikeMirzayanov, Delinur. A huge thank you to all of them for their work!

Good round to everybody!

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, friends!

UPD: Problem analysis

Hello everybody! My name is Gerald Agapov. I study at Saratov State University. Today I present you the set of, I hope interesting, problems. Good luck to all!