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
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.
This is a valid concern, but should be expressed A LOT calmer to be actually useful.
Noted :D
I'm sorry. You're right but I got really upset about 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).
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.
Auto comment: topic has been updated by samiemad (previous revision, new revision, compare).
All caps never solve anything.
*solves
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.
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
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.
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.
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
I/Oist
I/Oist in deed :D
"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.
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 :(