### undef's blog

By undef, 7 years ago, translation, ,

Hello everyone!

I am glad to invite You to take part in round #115 which is rated for participants of both divisions. As in last year, in this round You will help gamer Vasya to find himself in the virtual world of computer games: brag to his friends about his achievements, determine who is a "noob" and who is a "hardcore" player, destroy the Main Evil, play several rounds of the Plane of Tanks and get rid of the crowd of very bad gnomes. Generally, get a lot of fun!

The round authors are Gerald Agapov (Gerald), Evgeny Lazarev (undef) and Alexey Shmelev (ashmelev). Vladislav Epifanov (vepifanov) and Maria Belova (Delinur) helped us with the round preparation.

In this round You will be given 6 problems, instead of usual 5, also the round duration is increased from 2 to 3 hours.

P.S. Probably You have noticed the contest with strange name "RazMERiq 2012 (Private Contest)". Onsite contest based on Codeforces platform (big thanks to Mike Mirzayanov for the provided opportunity) and problems of this round will be held simultaneously in Nizhny Novgorod. Please, do not register on that contest:)

UPD: dynamic problem max scores will be used in this round.

UPD2: because of a mistake in problem 175B - Plane of Tanks: Pro and changed problem statement, please write a message to Gerald if your solution failed on test 4 because of the problem statement change. Please, specify the submit id in the message.

UPD3: Editorial.

Announcement of Codeforces Round #115
Announcement of Codeforces Round #115

•
• +71
•

 » 7 years ago, # |   +5 What is the meaning of private contest? I mean who can participate in that contest?
•  » » 7 years ago, # ^ |   +5 It is for onsite participants. You should register on Codeforces Round #115, it will contain exactly the same problemset.
 » 7 years ago, # |   +5 Will the problems be ordered by expected difficulty?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 Yes.UPD: Sorry, my initial comment was not true. The decision has not been made yet.
•  » » » 7 years ago, # ^ |   +27 I think its time to make a decision.
•  » » » » 7 years ago, # ^ |   0 Yes, the problems are ordered by difficulty.
 » 7 years ago, # |   -62 It will be rated round?
•  » » 7 years ago, # ^ |   0 Yes.
•  » » 7 years ago, # ^ |   +3 I am glad to invite You to take part in round #115 which is rated for participants of both divisions.
•  » » 7 years ago, # ^ |   0 It is explicitly written in the post.
 » 7 years ago, # |   0 I cannot DECODE the statement of problem B...
 » 7 years ago, # |   +1 What's the idea behind problem C?
•  » » 7 years ago, # ^ |   +5 Just use greedy approach:)
•  » » » 7 years ago, # ^ |   0 I tried always picking the figure that would give me the smallest number of points if I take only a number of them that would take me to the next p_i. This failed.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 UPD: You need choose just the least thing by cost.
•  » » » » » 7 years ago, # ^ |   0 Thanks! That was my first thought too, but then sent a solution with that idea and failed. Turns out that I understood the statement wrong: I thought that if p_1 = 1 and p_2 = 2 and I destroy 1 figure then I need another 2 figures to reach p_3. But yeah, they are cumulative.
 » 7 years ago, # |   0 What is the solution to problem F? I tried to solve it, but i got TLE on pretest 7( I used dijkstra algorithm for every query )
•  » » 7 years ago, # ^ |   0 That's way too slow. You'd need something around O(n log n) or O(n log^2 n) or O(n sqrt(n)), not O(n^2 log n) ;)
 » 7 years ago, # |   0 "Don't be a slowpoke" round :), btw I liked it.
•  » » 7 years ago, # ^ |   +18 Btw, I hated it :). On an ordinary round there wouldn't be such a huge difference between our places.
•  » » 7 years ago, # ^ |   +23 There probably should be a medium problem (between C and D in difficulty). Otherwise, for the people who solve ABC, it boils down only to speed.
 » 7 years ago, # |   +12 There is a bug in standings. I can't view them in each division separately.
 » 7 years ago, # |   +22 I'm not looking for excuses, but the statements are really hard to understand sometimes. Examples:Problem A: "In the first example the best result, obtained by artem is ..." (This would make you think that artem obtained the best result) They probably meant "In the first example, the best result obtained by artem is ...". (For me, that comma makes a difference)Problem C: "The number of figures of type ki and figure cost ci is known for each figure type" (I first thought that ki was a type.) I think it should have said "The number of figures of type i is ki and they all have the cost ci"Or maybe it's just me and in that case I apologise.
 » 7 years ago, # |   +17 Really love problem E: Tower Defence. I think people who have played it before may figure out the solution very soon -- at least true for me.
•  » » 7 years ago, # ^ |   +8 Warcraft III rules! :)
 » 7 years ago, # |   +50 One of the unluckiest contests for me happened like this:Problem D: I did a DP solution plus binary search. Got Wrong Answer for forgetting '<' should be '<='. Even worse, after fixing that, this code got TLE and adding inline optimizations saved the day.Problem E was even more unfortunate. When I was reading this problem, the Internet connection in my room went down. After trying in 10 minutes but no avail and 3 unsuccessful attempts in finding a wifi connection, I hurried to my university (it is about 500 meters far from my room). Finally, it was 30 seconds too late before I was able to submit my solution (quite close to the expected solution, although it was wrong anyway).Now I see how difficult it is to reach Grandmaster Level (or red) in Codeforces. Not only do algorithmic skill and coding ability are required, your physical condition must be good as well :)Anyway, I really like this contest (15 rating loss is not a big deal) because it brought me a memorable day :)
 » 7 years ago, # |   +5 (http://www.codeforces.com/contest/175/submission/1533074) A bit unlucky. In problem A I used atoi to convert string to number and check if it is greater than 1000000 like this atoi(a.c_str()) > 1000000. The problem is if the number is out of range atoi returns INT_MAX or INT_MIN. In my system it was returning INT_MAX, so it passes all test cases, but in codeforces i think it returned INT_MIN and someone hacked my solution. Anyway how do you hack someone's solution if the behavior of some function is undefined?
•  » » 7 years ago, # ^ |   0 Anyway how do you hack someone’s solution if the behavior of some function is undefined? There is "Custom test" tab
 » 7 years ago, # |   0 For problem c, my submission is giving the wrong answer for the first test case. But in ideone and my system, it's giving the correct answer. What the problem? (http://www.codeforces.com/contest/175/submission/1535400) (http://ideone.com/dUFwZ)
•  » » 7 years ago, # ^ |   0 I'm using Dev C++, and my system also have an incorrect output for that code. It seems that after the second loop, when the p is 6 and the nFigures is 2, the value of i is 1 (i++). Now, i>=SZ(v), but since we're still in the while(p>0) loop, and p is still greater than zero (value of p is still p-nFigures = 4), it won't break the while(t--) loop. So, in would access the value of v[1], which doesn't exist.
 » 7 years ago, # |   +11 Are there any editorials for this round?
•  » » 7 years ago, # ^ |   +7 Editorial for problems A-E.
•  » » » 7 years ago, # ^ |   0 Thanks very much. :)
 » 5 years ago, # |   0 Having a weird behavior with C++0x over here in problem B.I have submitted those 2 codes: 6314097 & 6314111, one of which got a WA and the other got accepted, the only difference was the line cerr << better << " " << least << endl;, which should not affect the output, not the variables. I tried to know why that might happen, but seems to hit a dead end. Any clue to what I might be missing over here.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +4 That's probably precision issues. 1.0 / 10.0 != 0.1, at least, you shouldn't assume that and always compare doubles assuming that each number can be stored with some small error only. For example: const double eps = 1e-8; // if (a == b) if (fabs(a - b) < eps) // if (a < b) if (a < b - eps) // if (a <= b) if (a <= b + eps) UPD: usually (un)commenting debug output affects optimizer, which can easily affect precision of floating-point operations.
•  » » 5 years ago, # ^ |   +1 See this for why this can happen: http://www.parashift.com/c++-faq/floating-point-arith2.html