samiemad's blog

THIS IS VERY UNFAIR!!!
By samiemad, history, 8 years ago, In English

Today I participated in Codeforces Round 348 (VK Cup 2016 Round 2, Div. 2 Edition), I managed to solve the first three problems in a very good time.

I started with problem D. didn't take long to figure out the idea (I like it very much BTW :). I submitted and got TLE on pretest 11. I knew it was because of huge input so I added 

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

I know that with these three lines cin/cout becomes almost as fast as scanf/printf. so I resubmitted the problem and got pretests passed. I have about 40 minutes left so I move to the last problem.

So the system test finishes, and I am shocked that my solution for D got TLE on test 29!!! Although it runs in O(n) complexity!!!

After five long hours of waiting till I can submit again -_- ... I just changed cin/cout to printf/scanf and get ACCEPTED!

problem link: 669D - Little Artem and Dance

TL submission: 17493329

AC submission: 17500406

I don't think there is another unwanted solution with a close running time to this one!! (I believe O(n log n) solution would be fairly slower than O(n) )...

So I wonder why did they use this huge input and this very tight Time Limit??

I DON'T LIKE SCANF/PRINTF AND YOU SHOULDN'T MAKE ME USE THEM!!!

This is not the first time I see this issue, and I am not saying this for the ~200 places I lost for it. but I think problem setters should take extra care when setting the TL to deliver a fair and happy competition to all the users :)

I am wondering if anyone else ever had the same problem? this time or in another round??

I know I did but not in an official round so it didn't matter much!

My suggestions:

  • either stretch the TL so both solutions pass

  • or make the input a bit smaller so it won't have this HUGE impact on running time

  • or write a note at the end of the problem to use scanf/printf

  • or send an announcement that cin/cout will not be accepted

  • Vote: I like it
  • -46
  • Vote: I do not like it

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

You are competing. So, you should take care about all the details, including the tight time limits. I had the same issue during the competition, my solution passed pretests running in ~ 1.9s. Then, I changed to scanf and printf and it passed in 655ms. Just take it easy and learn about it for the next contests.

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

This is a valid concern, but should be expressed A LOT calmer to be actually useful.

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

    Noted :D

    I'm sorry. You're right but I got really upset about it...

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

      Using cin/cout gets TLE on a lot of problems even when you have the required complexity. I personally just copy/paste this to the beginning of any problem where IO is a concern (which is most problems with sub-quadratic complexity).

      #ifndef _WIN32
#define getchar getchar_unlocked
#endif
inline int ri()
{
    register bool sgn=0;
    register char c;
    while(1)
    {
        c=getchar();
        if(c=='-')
        {
            sgn=1;
            c=getchar();
            break;
        }
        if(c>='0' && c<='9')break;
    }
    register int x=0;
    while(1)
    {
        x=x*10+c-48;
        c=getchar();
        if(c<'0' || c>'9')return sgn?-x:x;
    }
}

      This is even faster than scanf. The problem with increasing TL for these types of problems is that often an O(NlogN) solution with getchar_unlocked will run faster than an O(N) solution with cin/cout.

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

Auto comment: topic has been updated by samiemad (previous revision, new revision, compare).

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

All caps never solve anything.

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

Not liking faster IO is not a good practice. Actually there is noting to like or dislike in a syntax. Its not your choice. You have to comply to the standards of the programming language of your choice. Or change the language where the faster IO are to your liking.

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

    I don't know where to begin...

    First of all I do like to comply to the standards of a modern language, C++, with its simple and effective iostreams. Not to an old language like C. After all I am writing in C++11 not C.

    Why don't you keep using c-pointers and arrays instead of vectors and maps because they are faster??

    I complained about not having stated clearly that faster I/O is required

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

      Though introduced early, it is clearly the faster way to do IO. Writing faster solutions is a critical aspect of programming competitions. So its not a good practice to dislike/ignore something which might be the deciding factor for executing the solution within time limits. Its not a big deal to write a small reusable function wrapping scanf so that you can use it the way you like.

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

        You have a very good point. But I still believe that the key in competitive programming is about the correct algoritgm with a good complexity not how fast can you read/write i/o.

        And if it was hard to find a good time limit seperating the two methods, I think a note about a strict TL would be a nice idea.

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

Why all the downvotes guys??! Do you think it's right to judge solutions solely on the input functions they are using???

This is racist.. (or I/O-ist maybe :D)

Solutions demand freedom and equality for all :D

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

"I DON'T LIKE SCANF/PRINTF AND YOU SHOULDN'T MAKE ME USE THEM!!!"

Really? It doesn't matter what you like or not. The author solution runs fast enough and the author chose a tight time limit. All the information you need is given to you — the problem and the limits. That's the beauty of programming problems — you don't get someone telling you "hey you did it this way, but the author thinks that other way is better so we'll give you half points even though it's probably correct". The whole point is that if you pass the limits — you're good to go. How you do that is your own problem. Same thing goes for asymptotic complexity. For example, while in theory O(N * log3N) is better than , in practice that is rarely the case, it doesn't mean that the time limit has to be so loose as to let solutions with the former complexity to pass if the author solution used the latter one.

P.S.

I know it sucks to have details such as input to make the difference, but you just can't blame anyone for that. It is even scanf/printf which is very very common. I've seen problems that require you to speed up your input much more than scanf/printf with very uncomfortable tricks in order to squeeze in the time limit.

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

    I know, But I still hate the idea of having to think about input functions during an "algorithms" contest!

    that's exactly why I stopped solving on spoj and moved to codeforces.. I hate to see this happen again with codeforces :(

    → Reply