Home » Interview coding problems/challenges

How to overcome TLE in competitive programming?

TLE in competitive programming: Here, we are going to learn how to overcome TLE in competitive programming?
Submitted by Debasis Jana, on September 14, 2019

What is TLE?

TLE means "Time Limit Exceed". So, in competitive programming, there are some constraints with a specific time limit (normally for each input 1 sec) and your task is to write your code in such a way that all test cases are passed within that time limit for each input.

If it does not, then obviously you will get TLE (if there is no compiler or runtime error).

The main problem in TLE is, you will not be able to know whether your code is generating the right output or not.

Because they first check your compiler error (if any) then runtime error (if any), then TLE (if any) and at last right or wrong answer your code is generating.

Why TLE comes?

There might be various reasons behind it that your TLE is coming. Some of the important reasons are:

1) Online Judge:

This is the main reason you can say. An online judge ( like codechef, hackerrank , hackerearth, etc) gives TLE on a question because there are some restrictions in each input with a specific time limit. If your program exceeds that time limit you will get TLE.

2) Reading input and output slowly:

Sometimes your code takes input slowly ( though you are responsible for that:). However, if you use Fast Input-Output method (FastIO) your program always runs faster.

To add fast IO in your code you have to write the following lines in main() in your code:

C / C++

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

Python

    import psyco
    psyco.full()

Java Do not use Scanner class, use BufferedReader instead.

3) Server Configuration

Sometimes, the server takes time to run your code. So, it might depend on their CPU, OS, etc. For this reason, the different platform gives you TLE in different cases.

4) Bound of loops

This is one of the main reason for competitive programming for getting TLE.

Suppose you are given a time limit of 1 sec for a value N. So you can run a loop at max range 10^7. Below table defines the complexity and value of N what should be for a time limit of 1 sec:

Max value of N	Suggested Max Complexity to overcome TLE
10^2	O(N^3)
10^3	O(N^2)
10^5	O(N * log (N))
10^6	O(N) [Perfectly accepted]
10^7	O(N) [ Use FastIO]
10^8	O(N) [ Border case ]
10^9	log (N) or sqrt(N)

Please Note that, a loop value (N) cannot be greater than 10^9 if N is an integer. Because an integer can take up to 10^9.

So, if you get TLE in any question always refer to the above table and try to optimize your solution. A program can be done in various ways and using various algorithms. Also always use FastIO for each problem you are solving.