Overcoming TLE in Competitive Programming

The main problem with TLE (Time Limit exceeded) is that it does not allow you to know whether your algorithm gives a correct answer or not.

Why TLE occurs?

Mainly TLE occurs due to the following reasons:

  • Online Judge Restrictions: TLE restrictions comes because the online judge does not allow the programs to run for more than some time (~1 second). You can estimate the time limit will occur or not by the input size.

Max value of N                                                        Time Complexity

10^8                                                                         O(N) Broader Case

10^7                                                                           O(N) Maybe

10^6                                                                            O(N) Perfect

10^5                                                                            O(N * logN)

10^3                                                                            O(N ^ 2)

10^2                                                                            O(N ^ 3)

10^9                                                                            O(logN)

  •   The method of input or output is slow.

 

Overcoming TLE

  • Change input/output methods: Use proper input-output methods and data structures for optimization. For example, in C/C++ use printf and scanf instead of cin and cout. In Java, use BufferedReader instead of Scanner.
  • Optimize your algorithms: This goes without saying. The problems are designed such that you will be able to clear all the test cases only if you choose the best possible algorithm.
  • Look for suggestions: Alhtough this should be your last step, you should try and look for comments written by other programmers as they often contain hints regarding how the problem can be solved in a more efficient way.

 

Happy coding.

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s