×

# Getting TLE in COOK82C

 0 https://www.codechef.com/viewsolution/13885561 Why my solution is showing TLE even if i've tested all the edge cases of problem constraints in my system. refer to the problem: https://www.codechef.com/problems/COOK82C asked 29 May '17, 12:51 2★sm1dash 10●2 accept rate: 0% 15.5k●1●20●66

 1 The problem is with the time complexity of your solution it is in the order of O(n^2)..try optimising on the solution , i am not that good my self but i think that problem can be solved with the help of segmented trees or mo's algorithm. answered 29 May '17, 17:29 94●4 accept rate: 0%
 0 As @phantomhive said,you have time limit problems. Your code is too slow. In each step you perform max(hst), which is O(n). Also hst.remove(val), which is also O(n). Try running the the program with a list of 1e6 large numbers and 1e6 large queries. I'll bet your program won't finish on your system, even if you let your computer run for a week. You can solve the problem using a queue (collections.deque). After each division by 2, push the result to the queue. Additionally you sort the array first. Then you can perform a a step in O(1) instead of in O(n). The current maximum will be either at the end of the array, or it is on top of the queue. answered 30 May '17, 03:02 591●5 accept rate: 22%
 0 @afaxnranrer I think I did the array version of what you said.. Still i have TLE. Pls review my solution: https://www.codechef.com/viewsolution/13787279 answered 30 May '17, 11:45 614●1●9 accept rate: 12%
 0 @dishant_18: Sorry If I haven't been clear. You need to sort the array, but you are only allowed to do it once at the start. Sorting an array with a million elements once is fine, but sorting them a million times will obviously be to slow. You need to find a way to compute the maximum in O(1) time (not in O(n*log(n))). A queue is the perfect data structure for this task, since you can easily use it in a way, so that the queue is always sorted. (By popping the max values from one side and pushing the halved values on the other side). I don't see a way to solve the problem without a queue. All the other solutions I've seen so far also use a queue. answered 30 May '17, 13:22 591●5 accept rate: 22%
 0 @afaxnrarer thnx for the help.. Sorry for such irritating question but m a newbie to coding! answered 30 May '17, 14:30 614●1●9 accept rate: 12%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,739
×729
×183
×11

question asked: 29 May '17, 12:51

question was seen: 458 times

last updated: 01 Jun '17, 17:55