You are not logged in. Please login at to post your questions!


Getting TLE in COOK82C

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:

asked 29 May '17, 12:51

sm1dash's gravatar image

accept rate: 0%

edited 29 May '17, 13:46

vijju123's gravatar image

5★vijju123 ♦♦

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

phantomhive's gravatar image

accept rate: 0%

edited 29 May '17, 17:36

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

afaxnraner's gravatar image

accept rate: 22%

@afaxnranrer I think I did the array version of what you said.. Still i have TLE. Pls review my solution:


answered 30 May '17, 11:45

dishant_18's gravatar image

accept rate: 12%

@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

afaxnraner's gravatar image

accept rate: 22%

@afaxnrarer thnx for the help.. Sorry for such irritating question but m a newbie to coding!


answered 30 May '17, 14:30

dishant_18's gravatar image

accept rate: 12%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 29 May '17, 12:51

question was seen: 458 times

last updated: 01 Jun '17, 17:55