Time Limit Exceeded
"Why is the time limit of code exceeding?" This is a question which every competitive programmer has, it doesn’t matter whichever platform (Hackerrank, Hackerearth, CodeChef, Codeleet or any other) they are using , some or the other day they face this “Time limit exceeded” problem. To clear your doubts regarding this, read this article, we assure you, you will have a solution to the “Time limit exceeded” pop-up next time.
First
of all, we need to understand something about compiling of code in competitive programming
In
competitive programming, your code is tested by
a code-checker automatically, not by a human being, and you have to write your code
accordingly.
For each problem, there will be one or
more input files, each according to the specifications mentioned in the problem
statement, and corresponding correct output files. Your program is run on each
of the input files by redirecting the standard input stream to an input file,
and the standard output stream to another file. The output generated by your
program must match the correct output exactly in order to be judged correct.
Note that your program
must read from stdin and print to stdout. This means using scanf/printf in C,
cin/cout in C++ and similarly in other languages.
To
understand more about “Time Limit Exceeded(TLE)”, understanding how the online
checker works will help. The online judge allocates resources like memory and
CPU for evaluating every submission.
However,
to ensure that your submission does not keep running for an infinite time, the
online judge has to stop your submission from running after a particular time
period. This time period is actually decided by the problem setter and is given
as one of the inputs to the online judge. Once the submission program runs for
time period the judge system issues a system kill command to the program
execution and assigns TLE result to the submission.
The
most common reason that you would get a TLE is because your program is too
slow. If a problem tells you that N <= 100000, and your program has nested
loops each which go up to N, your program will never be fast enough. Read the
bounds in the input section carefully before writing your program, and try to
figure out which inputs will cause your program to run the slowest.
The second most common cause of TLE is that your method of reading input and writing output is too slow.
In Java, do
not use a Scanner; use a BufferReader instead. In C++, do not use cin/cout -
use scanf and printf instead.
In Python, you could try speeding up your solutions
by adding the following two lines to the start of your file:
import psyco
psyco.full()
To
see if your method of reading input is fast enough, try solving the Enormous
Input Test problem. If you get time limit exceeded, try another method of
reading input.
Finally,
you may have tested your code on all sorts of large inputs and are sure your
code will run inside the time limit. However, online judge may be slower than
your computer. It is common for a program to take 2-3 times longer on online platform
as it does on your computer. The time limits are all attainable (tested by our
problem tester), so you will just need to come up with a way of making your
algorithm.
If you still have any doubt on this topic then do come to us via email "sophomoretechs@gmail.com" or via instagram "@coding.winds".
We also have an article on space complexity and time complexity , do give them a read.
