Time Limit Exceeded- How To Avoid TLE ? | Trick To Pass All Test Cases In Competitive Programming

Aug 15, 2023

Time Limit Exceeded- How To Avoid TLE ? | Trick To Pass All Test Cases In Competitive Programming

Time Limit Exceeded (TLE) Time Out Error mainly occurs when either program is not able to exit gracefully or some of the test cases are left for validation in a given time constraint for that problem.
This video explains how to overcome TLE by choosing the right algorithm and
This trick is used by the competitive programmer to approach problems in competitive programming contests.

🔴 DONT CLICK THIS: https://bit.ly/2G4cEuc

👍 Like us on Facebook: https://www.facebook.com/HackerRankSo…

💎Share this video with a friend: • Time Limit Exceeded- How To Avoid TLE…

✚ Join our community ►

👉 Coding interview preparation group: https://www.facebook.com/groups/codingip
👉 Telegram link for algorithmic tutorial: https://t.me/javaaid
👉 Telegram link for hackerrank solutions: https://t.me/hackerranksolutions

✅ Recommended playlists ►

👉 All hackerrank solutions: • How To Master In Data Structures And …

👋 Let’s Connect ►

Git Hub: https://github.com/kanahaiya
Twitter: https://twitter.com/Kanahaiyagupta
Linked in: https://www.linkedin.com/in/kanahaiya…
Facebook: https://www.facebook.com/coolkanahaiya
Instagram: https://www.instagram.com/coolkanahaiya

#JAVAAID #TLE #timelimitexceeded #competitiveprogramming #HackerRankSolutions #HackerRankTutorials #implementation #prefixsum #HackerRank #JavaAidTutorials #Programming #DataStructures #algorithms #coding #competitiveprogramming #JavaAidTutorials #Java #codinginterview #problemsolving #KanahaiyaGupta #hackerrankchallenges

Content

0.21 -> Hey everyone, Today I am going to share a competitive programming

4.27 -> secret with you.

6.36 -> If you're a competitive programmer, then this video is very important for you.

12.1 -> in today's video, I am going to cover What is TLE?

16.76 -> Why TLE occurs? and How to overcome TLE?

21.38 -> And we are going to start right there.

23.8 -> What is TLE?

25.5 -> TLE stands for time limit exceeded which is also referred by time out error in common language.

33.3 -> Why TLE occurs?

35.42 -> Whenever you submit your solution, it will go to the server, and their online judge will

40.36 -> execute your program and try to validate your program output, against pre-defined test cases,

47.52 -> in a given time frame, which is set by the problem setter for a particular problem.

53.64 -> If your program is unable to finish within a given time frame, or it’s in middle of

59.14 -> executing the test cases, in that case judge will issue kill command to your program, and

65.4 -> throw TLE for some or all the test cases, which are not yet validated by the online judge

72.86 -> Here, your program was compiled successfully, but it didn't stop before the time limit.

79.12 -> This may be because either algorithm is badly designed (too slow), or it contains a bug.

85.48 -> example- it goes into an infinite loop, or hangs up, expecting some input data.

91.4 -> I hope you have got the idea by now why TLE occurs.

96.22 -> Let’s move on to next point

98.64 -> How to overcome TLE?

100.96 -> In today's word, the computer can easily solve 10 ^ 8 operations in a second in the worst case

109.48 -> And we are also going to use the same fact to get rid of TLE.

114.52 -> Now we know the online judge is also a program, which is running on a server or computer,

120.54 -> and it has at most one second time for our program to validate.

125.56 -> So, our intention will be to write the program in such a way, so that it will not take more

131.02 -> than 1 second to complete for given constraints.

135.3 -> There are two things which highly impact your program performance in contests.

141.14 -> 1. Algorithm

142.9 -> 2. Input Output

145.16 -> Let's talk about algorithm first-

147.9 -> How to Choose the right algorithm-

150.12 -> Look for the constraints given in a problem statement, and come up with an algorithm which

155.18 -> can pass all test cases in a second.

158.88 -> Here is the cheat sheet which will help you to understand well in more detail.

164.34 -> If the input size is less than equal to 10^18, then log n algorithm will solve the

171.7 -> problem within a second.

174.36 -> example- binary search.

177.09 -> If the input size is less than equal to 10^8, then you have to come up with an algorithm

184.27 -> which is less than or equal to O(n) to solve the problem in a second.

190.19 -> example- linear search.

192.35 -> If the input size is less than equal to 10^6, then at max O (n log n) algorithm can

200.41 -> be applied to solve the problem in a second.

204.51 -> example- Merge Sort, building Segment Tree.

207.93 -> If the input size is less than equal to 10^4, then O (n 2) algorithm will require

215.62 -> solve the problem.

217.78 -> example- Bubble sort, Selection sort, Insertion sort, 2 nested for loop.

224.8 -> If the input size is less than equal to 2000, then at max O (n2 log n) algorithm can be

232.2 -> used to solve the problem.

234.76 -> example-2-nested loops and a tree-related DS.

239.32 -> and so, on etc.

241.18 -> there is one more sheet which will show a different perspective of the same.

245.52 -> here you can see, based on input how much operation an algorithm has to perform, and

251.01 -> highlighted the maximum operation which can be performed by the specific algorithm in a second

257.92 -> If the input is 10, O (log n) algorithm has to perform 3.3 operation or instruction.

265.78 -> but O(n) algorithm will have to process 10 operation for the same.

271.04 -> and O (nlog n) algorithm will have to process 33 operations and so on.

277.72 -> The cell highlighted in green depicts the maximum instructions or operations that can

283.34 -> be process by the CPU, for that particular algorithm against given input.

290.2 -> Let's do some exercise: Here is the

292.9 -> problem statement- write your own sorting algorithm to sort an

296.699 -> array of n integers in ascending order (without using any library).

302.27 -> input format- The first line contains integer n, the size

306.42 -> of the array.

308.22 -> The second line contains n space-separated integers describing (the unsorted array)

315.06 -> Constraints- 1

321.82 -> Output Format- Print the array as a space-separated integer

325.66 -> in ascending order.

328.03 -> Sample Input 5,

329.5 -> 5 3 6 8 9 Sample Output

333.169 -> 3 5 6 8 9

336.639 -> Algorithm 1 If you use bubble sort you are bound to get

339.77 -> TLE because bubble sort algorithm complexity is O (n^2)

345.27 -> and as we know the computer can perform 10^8 operation in a second

351.56 -> so, O (n 2) algorithm, need to process 10^12 operation which will take 1 second * 10^4

361.68 -> which is equal to 2.77hours.

366.569 -> Algorithm 2 if you use merge sort your algorithm will

369.68 -> run within a second because merge sort complexity is O (nlog n)

375.08 -> if you simplify this it will approx.

378.5 -> 10^6 * (log (10^6)) =2 *10^7.

391.46 -> 2 *10^7 which is less than 10^8.

398.1 -> operations which can be easily performed within a second by the computer.

402.88 -> So, merge sort is the right choice here.

406.16 -> this is how we should come up with the right algorithm before implementing it to save our

410.82 -> time and effort.

413.1 -> Input Output - Sometimes input output can also be a bottleneck

417.48 -> which will cause TLE. you should always use fast input output in

422.31 -> coding contest like in C C++ we have scanf, printf, fast

427.82 -> I o, and in Java we have buffered reader, in other programming languages also will have

433.66 -> some alternatives which will help you to read fast.

437.44 -> Note* constraints on the time limit also depends on the language on which you are coding.

443.86 -> every programming language may have different execution time which is set by the problem setter.

449.64 -> if CC++ program takes 1 second, java might

454.6 -> take 2 second and python might take 4 second.

458.88 -> Because python is a slow language and CC++ are relatively fast because they are being

465.46 -> closer to the hardware.

467.94 -> but the concept will remain the same to analyse and come up with the correct algorithm which

473.22 -> can pass all test cases.

476.12 -> I hope, you have enjoyed this video, if you want more video like this in future, please

481.9 -> like, comment and share this video with your friends.

485.84 -> and do not forget to subscribe this channel.

Source: https://www.youtube.com/watch?v=S8V444xdNvM