Competitive Programming

2 min read

Time and Space Complexity

NOTE: Usually in the online judges, given a time limit of say 1 second, the score is same for a runtime of 0.2 seconds as well as 0.8 seconds. Same for memory limits as well. This motivates a trade-off between the choice of algorithm and runtime or memory constraints.

Tips for I/O on online judge

In competitive programming, most problems are batch problems, where all the input is received at the start and all the output read at the end, with no interaction with the grader. In these kinds of problem, the recommended approach for I/O is to use std::cin to read input and std::cout to output information, using \n instead of endl, as it is faster.

At the top of the main() function, it is recommended to add these two lines1, as they will speed up execution significantly in batch problems:

 ios::sync_with_stdio(false);
 cin.tie(NULL);

Another useful tip is to use the following loop when a problem has t test cases, decrementing and checking for the breaking condition in one step:

int t;
cin >> t;
while (t--) {
    // solve the problem here
}

When the problem does not specify the number of test cases and you have to ask the grader for input until there is no input left, the following loop is helpful:

int n; // substitute this for the input specified in the constraints
while (cin >> n) {
    // solve the problem here
}

Footnotes

  1. How does this work? Why does this speed up execution? ↩

Graph View