I was doing a problem in Codechef and when I submit my solution it shows “Time Limit Exceed”, I am wondering if my solution is correct and I just have to optimise it OR it could be wrong?
It could be wrong.
Not necessarily. TLE means your code couldn’t provide an output in the specified time limit. After you optimize your code and manage to produce an output within the given time limit then only Chef can match your answer with his output file to check whether your answer is correct or not.
I answered this long time ago here - http://discuss.codechef.com/questions/1224/how-to-tell-solution-is-slow-or-wrong-when-time-limit-exceeds/1239 please also read the forum…
I had the same question, does TLE solution gives correct answer? Then I looked for it at best website to get essays and to get answer to it. It showed that their solution varies with different tasks, great post.
It could be wrong. You have no guatantee on the outcome, after optimization, you can have a good answer, a wrong answer, or even a runtime error.
It is possible that your solution to the problem was right,or it could be wrong but surely it was not acceptable because its time complexity or the time taken to run the code was more than the time limit specified by the problem setter. If TLE is coming that means , you have to come up with an alternative solution, you have to think in a different manner than you were thinking previously. Thinking in a step by step manner will increase your deductive skills. I hope it helps.
TLE simply reflects that your code is not optimised enough as per requirement, it can be correct but time constraint is not being fulfilled.
No, TLE (Time Limit Exceeded) doesn’t necessarily give the correct answer. It just states that your program execution has exceeded the time limit specified in the question, after which neither Codechef nor any Online Judge bother to check whether your solution is correct or not.
Online judges follow the ‘AND’ condition when they run the program. This means that even if one of the conditions they mean to check is false, they terminate the execution without checking the next condition. The order is something like this:-
1)Check compilation (Compilation Error)
2)Check whether there are any runtime errors (NZEC)
3)Check whether the program has given an output within the time limit (TLE)
And if your program successfully passes these tests,
4)Check whether the output(s) obtained matches with the output(s) in their list or not (AC/WA)
The only way to check whether your program is effecive (but not efficient) is to run and test it on any IDE(offline) or [http://ideone.com/] (online) for random inputs.
Obviously, your program won’t work for large inputs, as they were the cause of the TLE.
I hope it helped
It is not necessary.
TLE just means that your code ran out of time before it can completely execute.