NALP's blog

By NALP, 6 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.Leonidas

2.CarlyPlus

3.Dakurels

4.ytqiaqia

5.SuccessfulHackingAttempt

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

»
6 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 ! :)

»
6 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.

»
6 years ago, # |
  Vote: I like it -52 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it -62 Vote: I do not like it

Nice, waiting for tutorial :)

»
6 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

»
6 years ago, # |
  Vote: I like it -68 Vote: I do not like it

happy new year and good luck :) :*

»
6 years ago, # |
  Vote: I like it -43 Vote: I do not like it

C-C-C-COMBO BREAKER!

»
6 years ago, # |
  Vote: I like it -39 Vote: I do not like it

Good luck to all CodeForcers :) Let's hope in a good and fun one!

»
6 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.

»
6 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.

  • »
    »
    6 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!!

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

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

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

how amazing testing system

»
6 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.

  • »
    »
    6 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.

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

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

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

    I get AC using atan2(),,

  • »
    »
    6 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.

»
6 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

  • »
    »
    6 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.

  • »
    »
    6 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.

»
6 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

  • »
    »
    6 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.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Hi,

      Yep indeed, your judging system has no problems, the problem lies with my solution.

      I've tried to simplify my code, in order to familiarise myself with how putchar() and printing characters with printf("%c",...) works — see 2902859

      However, even though the following works on my local machine, and the custom test function on your website, it fails to pass the test 1 for the reason you've quoted. Could you enlighten me as to why this might be the case?

      putchar('+');putchar('-');putchar('-');putchar('+');

      I'm basically testing by hardcoding the answer to test 1, I've also tried alternatives like including the trailing null termination character '\0', and a newline '\n' thereafter, but it does not help at all.

      I can't reproduce the problem on my local machine nor on your custom test section, so I'm absolutely clueless as to what exactly is going on.

      Please please help.

      Many thanks, Lee Wei

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

      Hi again,

      I've narrowed it down to the culprit for my WA to this line vector<char> b;

      2902976 fails, but 2902986 succeeds.

      So my next question is: since my final answer is guaranteed to be exactly n characters long, why can't i initialise with vector<char> b(n);? which means 'give me a vector of chars called b which will have a max size of n'...

      Thanks.

    • »
      »
      »
      6 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++)

      • »
        »
        »
        »
        6 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".

»
6 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.

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

    maybe try running it in the "Custom test" option on this contest website and see if the correct output is generated as expected?

  • »
    »
    6 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 .

    • »
      »
      »
      6 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.

      • »
        »
        »
        »
        6 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"

    • »
      »
      »
      6 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.

»
6 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. :(((

»
6 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.

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

    if(sum+(k-i-1)>=m), are you sure that you want 'i' there?

  • »
    »
    6 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.

    • »
      »
      »
      6 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.

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

        I had same issue before! I had following statement

        bool checked[n];

        Where my assumption was the default values are false. Locally it was working but in CF it's not guaranted that default values are false and you have to initialize them manually :)

»
6 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

  • »
    »
    6 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.

    • »
      »
      »
      6 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.

      • »
        »
        »
        »
        6 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.

        • »
          »
          »
          »
          »
          6 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.

»
6 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?

  • »
    »
    6 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!

    • »
      »
      »
      6 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)

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

        Well the idea is to solve the case n = m, which is simply petya = n — 1, vasya = m. Now is easy to adapt it for the general case by adding the assolute difference between n and m to petya and thats it.

»
6 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!)

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

  • »
    »
    6 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.

    • »
      »
      »
      6 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.

»
6 years ago, # |
Rev. 3   Vote: I like it -7 Vote: I do not like it

edited ..

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the editorial be published in English, and a link updated on this blog post please?

»
6 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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What about the English editorial?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a tutorial?

»
20 months 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.