undef's blog

Codeforces Round #115
By undef, 13 years ago, translation, In English

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
  • Vote: I like it
  • +71
  • Vote: I do not like it

»
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What is the meaning of private contest?

I mean who can participate in that contest?

→ Reply
»
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Will the problems be ordered by expected difficulty?

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Yes.

    UPD: Sorry, my initial comment was not true. The decision has not been made yet.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      I think its time to make a decision.

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, the problems are ordered by difficulty.

        → Reply
»
13 years ago, # |
  Vote: I like it -62 Vote: I do not like it

It will be rated round?

→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I cannot DECODE the statement of problem B...

→ Reply
»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What's the idea behind problem C?

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Just use greedy approach:)

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        UPD: You need choose just the least thing by cost.

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 )

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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) ;)

    → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"Don't be a slowpoke" round :),

btw I liked it.

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Btw, I hated it :). On an ordinary round there wouldn't be such a huge difference between our places.

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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.

    → Reply
»
13 years ago, # |
  Vote: I like it +12 Vote: I do not like it

There is a bug in standings. I can't view them in each division separately.

→ Reply
»
13 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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.

→ Reply
»
13 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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.

→ Reply
»
13 years ago, # |
  Vote: I like it +50 Vote: I do not like it

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 :)

→ Reply
»
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it

(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?

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Anyway how do you hack someone’s solution if the behavior of some function is undefined?

    There is "Custom test" tab

    → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
13 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Are there any editorials for this round?

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    See this for why this can happen: http://www.parashift.com/c++-faq/floating-point-arith2.html

    → Reply