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:
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.
1 Like
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.
@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
@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.