Блог пользователя vatsal

Optimizations for Competitive Programming
Автор vatsal, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится -57 Проголосовать: не нравится

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.

→ Ответить
»
8 лет назад, # |
← Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить