vatsal's blog

Optimizations for Competitive Programming
By vatsal, history, 8 years ago, In English

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. :)

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

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

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.

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

    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.

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

    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.

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

      Using scanf/printf isn't an optimization, it's a common sense.

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

Not sure if this is what you were looking for, as the criteria was a bit vague.

General:

  • Use bit shifting operations instead of normal math operators
  • Iterative instead of recursive solution
  • If you must do recursive, this test indicates passing unwrapped arguments is slower than passing in a struct by value, which is itself slower than passing in a struct by reference, at least in C++.
  • 1D arrays versus 2D or higher-dimension arrays (only for very, very dense arrays — generally not an issue)

C++:

  • <bitset> instead of bool array

Python3: (For Python2, just replace input with raw_input)

  • Use the following for input (watch out for the extra \n this will read):
from sys import stdin
input = stdin.readline

Java:

  • Best to read from BufferedReader

This is all I have

→ Reply