“I have implemented everything perfectly. Then why am I getting TLE?” is the question that comes to most programmers who are new to competitive programming. Let me tell you guys once and for all that declaring variables inside loops or writing a lengthy code has nothing to do with it. Variable declaration takes negligible time and the number of lines in the code does not affect the execution time of a program. If you are getting TLE, it is because the logic that you have devised to solve the problem is taking up a lot of time when run on large inputs. Lets take a simple example.
Suppose that we have to write a program to find the sum of all natural numbers from a till b. ( a and b are natural numbers too )
One possible approach (in C/C++) to this simple problem is
int i,sum=0; for(i=a;i<=b;i++) sum+=i;
Now, if examined in terms of correctness, this code has nothing wrong with it. It finds the correct answer. But the code is not efficient with respect to time. If the difference between ‘a’ and ‘b’ is very large (say, a=1 and b=10^15), this code would take forever to run because the for loop will have to iterate from 1 till 10^15.
There’s another way to find the solution. We know that the sum of the first n natural numbers is ( n * (n+1) ) /2. By using this formula we may write the following code:
int high= (b * ( b + 1 )) /2; int low= ((a-1) * a) /2; int sum=high-low;
The variable ‘high’ contains the sum of first b natural numbers. And the variable ‘low’ contains the sum of first (a-1) natural numbers. So, obviously the sum of natural numbers from a to b will be (high – low).
The second approach will always take constant time to run. The execution time will be the same no matter how far apart a and b are. And it gives the same answer as the first method.
Now you see, this is the reason the first solution was not correct even though it was giving the correct output. Remember that if you are getting TLE, it may be because of the following reasons:
1. The logic of your program is not fast enough (as demonstrated above).
2. Your program is going into an infinite loop somewhere.
3. Rarely, VERY rarely because you are not using an efficient way to take input.
The problem setters usually set the time limit such that a participant never gets a TLE due to the 3rd reason. A note for C++ users: if a problem is such that large amount of numbers have to taken as input, it is better to use scanf() instead of the cin stream. The cin stream is slower than scanf().
(See the documentation for your language to find the best way to take input.)
When comparing two algorithms, we use a method known as the ‘Big O Notation’. In a nutshell, the Big O notation tells us what the execution time of a program is directly proportional to.
This notation is used very frequently to comment on the efficiency of the algorithms and its very important that you get familiar to it. I’ll write about it in my next post (which will be very soon!).