Hello Readers, I have seen that many people don't use scanf or cin or cout or printf but their own input output functions . I have heard that some people were able to pass "naive" algorithm under time limit with the help of optimizations. I would love if everyone here would share their optimization codes and explain meaning of every line so that "everyone" would get it in C++. I only know ios_base::sync_with_stdio(false); cin.tie(0); Also I don't understand the meaning of these lines. Thanks for your efforts. :)
I/O optimizations will NEVER make a TLE solution get an AC. the sort of solutions you are talking about mostly consist of some other optimizations in the algorithm itself like including break statements at appropriate locations in the code.
Well, it does when the input is huge. I have experienced this many times especially with problems that have multiple test cases in one file.
he's asking if a naive algorithm will pass with I/O optimizations.
really are there situations where an O(n^2) or something worse could pass with I/O optimizations when the expected complexity is O(n) or better? could you please link some problems.
It's hard for the O(N^2) vs O(N) case, but SPOJ is full of problems with O(N) intended solution where you can squeeze in an O(NLogN) solution with fast input. Some people even used to make a fast input template especially for these kind of problems.
i was unaware of such problems. sorry for my first comment.
No worries it's fine, no need to apologize at all :D .
adelnobel: Thanks for your kind reply. Could you share some optimization techniques?
Yeah sure,
For C
http://codeforces.net/blog/entry/8080?#comment-138179
http://abhisharlives.blogspot.com.eg/2012/06/really-fast-io-methods-for-programming.html
For Java
http://neerc.ifmo.ru/trains/information/Template.java
And you can also find one in Egor's template in any of his submissions. 17328614
Thanks!
No, you are wrong! A year ago, I was solving 1329 Galactic history from Timus. I didn't ACed it. Yesterday I saw my old code, and noticed that the input was HUGE, and that I had used cin/cout. So, I replaced them with scanf/printf, and it went from TLE (limit was 1 sec) to AC in 0.124 sec, and the code for solving the problem remained the same.
Using scanf/printf isn't an optimization, it's a common sense.
Go away and code in assembler.
(Let the shitstorm begin)
XD
Not sure if this is what you were looking for, as the criteria was a bit vague.
General:
C++:
<bitset>
instead ofbool
arrayPython3: (For Python2, just replace input with raw_input)
\n
this will read):Java:
BufferedReader
This is all I have