NALP's blog

Codeforces Round #159 (Div. 2)
By NALP, 11 years ago, translation, In English

Hi to all!

A few hours later you're lucky to participate in Codeforces Round #159 for Div.2 participants, but traditionally the others can take part out of the competition. It has been prepared by me (NALP), Ivan Fefer (Fefer_Ivan), Pavel Holkin (HolkinPV), Vitaly Aksenov (Aksenov239) and Gerald Agapov (Gerald). Also we express thanks to Mary Belova (Delinur) and Mike Mirzayanov (MikeMirzayanov).

Traditionally I wish good luck, accepted solutions and successful hacking attempts for you!

UPD: Today it is decided to use dynamic scoring system. But the problems will be sorted from low difficulty to high by authors' opinion!

UPD: The contest finishes, congratulations to the winners!

1.GreatEagle

2.CarlyPlus

3.Dakurels

4.ytqiaqia

5.SuccessfulHackingAttempt

  • Vote: I like it
  • +86
  • Vote: I do not like it

Comments Comments (57)
| Write comment?
»
11 years ago, # |
  Vote: I like it -49 Vote: I do not like it

Thank You ! We Were Waiting for The First Contest in This Year ! :)

→ Reply
»
11 years ago, # |
← Rev. 4   Vote: I like it -53 Vote: I do not like it

Correction Required :It is obvious, but traditionally it is Round #159.

In Indian culture, it is considered good to make minor mistakes when you do something good (like a small typo in the wedding card). So hope this NEW YEAR CONTEST is good for all.

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

I can't wait to do it >_< thank u very much

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

Nice, waiting for tutorial :)

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

wow it seems all the comments here get negative votes. so here i am! :d

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

happy new year and good luck :) :*

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

C-C-C-COMBO BREAKER!

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

Problem A description was so hard to interpret. It took me more than 15 minutes to get what the problem was asking.

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it

In problem A , I was really getting confused through a lot of words like supply line filters , devices , sockets , electric sockets. I was really changing the symbols through and forth.

I could not even understand the meaning of the problem :(. I need to improve my English.

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

    Its not about how good your English is! The problem statement was the worst ever!!

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

      humm...really, I've not understood too... :(

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

how amazing testing system

→ Reply
»
11 years ago, # |
← Rev. 5   Vote: I like it +6 Vote: I do not like it

About Problem C

Why atan2() have error, but acos() is ok?

PS: Oh,atan2() is ok. The error occur because cout and printf have some diff.

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

    Got AC with atan2 (after contest). Here 2893071.

    UPD: I know who are downvoting to these comments. People who had no fun in this contest.

    THOSE WHO USE RUSSIAN-CF ARE LUCKY THIS ROUND.

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

    atan2() works. May be just careful boundary crossing angles handling.

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

    I get AC using atan2(),,

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

    I used atan2, no trouble whatsoever. But you can just check your solution with the test data you get the error at, and find the bug.

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

This is Contest or english lessons?,problem A is so hard who does not know english,Fuck english

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

    Let me rephrase your question: are the problem setters foreign language experts? English is the main scientific language, too bad.

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

    It's okay. On ICPC we were calling such problems English problems. Sometimes they were two A4 papers long. But we were able to dedicate time for that, concentrate, read and sometimes solve.

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

Hi,

I believe there is a problem with the solution judging system for Problem D: Sum.

My corrected submission after the round (now registered for practice) can be found at the following link: @ http://codeforces.com/contest/257/submission/2893122

For test 1, which is: 4 1 2 3 5

My solution output: +--+, which works, because this translates into 1-2-3+5 = 1, whereas my solution was judged WA, because the system was expecting "+++-" instead.

The problem statement clearly states "If there are multiple solutions, you are allowed to print any of them."

Could someone please verify this/provide me some clarification please?

Thanks, Lee Wei

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

    Hi, your solution outputs extra symbols (it seems with code 0) after the answer. So, problem's checker reads token <<+--+__>> (symbol _ for clarity only) and considers this token not a valid answer.

    I think everything is ok.

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

      Hi,

      I've done further tests to narrow down the issue. It seems that if i only print a single character up to n times, instead of traversing the whole vector (which I've initialised to be max size n), i break when a counter i inserted hits n, then the solution is ACC — see 2903009.

      is my STL container traversal macro correct? #define TR(c,itr) for (typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)

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

        Yes, it seems correct. Could you show a working and a failing solution that differ not so much, or elaborate on what is wrong?

        By the way, vector<char> b(n); creates a vector of actual size n, not of "max size n".

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

Can someone tell me why long double doesn't work, but same code with double gives AC? here are submits :

WA : http://codeforces.com/contest/257/submission/2893123

AC : http://codeforces.com/contest/257/submission/2893207 (in this code shorten "ld" is for double, not for long double...). When I execute same TP with long double on my computer, it outputs correct result for me. And if I use cout, it truncate the last 6 digits, so I get WA again.

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

    You must not print long double with printf("%lf", d); because %lf reads double but not long double.

    To print long double you should write like this: printf("%.10lf", (double)d);. Or you can use cout like this:

    cout.precision(10);
cout << fixed;

cout << d << endl;

    After cout.precision(10) and cout << fixed program will always output real numbers with exactly 10 digits after the .

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

      I know %lf is for double, but I have used in code %llf, and it worked fine on my computer. I have tried Custom test and I have found few things. $llf and %Lf doesn't work with gnu C++ 4.7 compiler, but If I switch compiler to Microsoft Visual C++ 2010, I get correct answer no matter do I use %llf or %Lf for long double. I have submitted WA code from previous post, with different compiler, and I got AC. :( so sad I didn't realized this before. Thanks anyway on answers. I hope this mistake will not recur.

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

        in Microsoft Visual C++ long double == double.
        sizeof(double) == sizeof(long double) == 8
        in GNU C++ long double != double.
        sizeof(double) == 8
        sizeof(long double) == 12
        That's why Visual C++'s printf works with "long double"

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

      http://codeforces.com/contest/257/submission/2890819

      check out this solution. I know the solution is incorrect, but the reason why I got WA is really surprising.

      I did exactly what all u told, I set the precision as 12 digits after the '.' Still answers didn't match.

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

Does anyone have any idea that how I can get TLE with GNU C++ 4.7 and AC with Microsoft Visual 2010 with the same code on both??!!!! I'm stuck on this problem for 90 mins in contest and almost missed other problems. :(((

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

Div 2 — Problem A:

My solution is giving correct output for the testcase: 5 50 6 2 1 3 1 3

with output -1 on my computer and ideone:http://ideone.com/hM20Vq but giving a different answer on custom test here and hence judged wrong. Please do something about it.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 4   Vote: I like it +8 Vote: I do not like it 
    REP(i,0,k)

    If k > n, then this loop goes outside the array, so the variable sum is added an undefined value of a[n]. You can use customtest to debug directly on CF.

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

      Changing it to min(n,k) gets ACC. Thanks alot for pointing this out.

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

my solution is producing correct output for all the test cases,but my code is failed during the system testing on case 17,although it gives correct output -1. can anyone answer why this happened ? my solution can be viewed here

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

    I tried it locally, it gives incorrect output 6. The issue is in your code.

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

      sir,I have checked on custum test indivisually only for that case. It gives output -1.

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

        The bug is in line 15: for(i=0;i<=k;i++)

        Here must be no k, it must be n.

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

          ohhh...thanks. Its my fault.I got it. sorry for troubling you all.

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

I wrote a solution about problem B long 3 lines in O(1) time. Looking among the submitted solution almost everyone has solved the problem in O(n) in more complicated way. I wanted to ask why, is there any case where my idea fails?

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

    Some of my friends solved it with 1 liner solution O(1) and their solutions passed the system test!

    I don't know how or why till now!

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

      The optimal strategy is the simplest one: as long as you have a choice, use the cube that gives you a point. I don't have a solid proof for this, but it's sort of the obvious way (especially given it's just problem B and those rarely involve more than brute force/greedy).

      How will the situation look, then? Suppose there are A cubes of the color which the first player chooses as the first cube, and B of the other, on the input. Then the adding of the cubes only gives 1 point to the player making the move, until there are no more cubes of the desired color; then, each turn only gives a point to pl. 1.

      From this, it's easy to see that the sooner there's only 1 color left, the more points pl. 1 gets, so A <= B. And it's just simple math from here on out.

      (This is just my opinion on the solution. I used the greedy approach, though, since I code faster than think so logically :D)

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

Okay, here is my comment on this contest.

This was the worst contest I ever played on codeforces! The problem statement of the first problem was the worst ever! More than 15 minutes of reading and I couldn't figure out what the problem is talking about!!

For the second problem, it was not clear as well! Many people submitted O(1) solutions which passed the system test for non obvious reasons (at least for me!)

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

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

    Contests aren't just about thinking/coding, but also about being able to efficiently understand the prob. description (and other stuff).

    For my opinion on the solution of prob. B, read above.

    I actually liked this contest, because there weren't crazy jumps in difficulty.

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

      But still the statement of task A was unecessarly overloaded of test.

      → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it -7 Vote: I do not like it

edited ..

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

editorial in Russian published here @ http://codeforces.com/blog/entry/6357, use google translate pls, at least until a translation (will it come?) arrives.

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

What about the English editorial?

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

Is there a tutorial?

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

Still no tutorial?

BTW can you update the tag for problem 1 it can also be solved using binary search approach.

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

Can't find the editorial..

→ Reply