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

×

Getting TLE in COOK82C

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

sm1dash's gravatar image

2★sm1dash
102
accept rate: 0%

edited 29 May '17, 13:46

vijju123's gravatar image

4★vijju123 ♦♦
15.2k11859


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.

link

answered 29 May '17, 17:29

phantomhive's gravatar image

4★phantomhive
944
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.

link

answered 30 May '17, 03:02

afaxnraner's gravatar image

6★afaxnraner
5915
accept rate: 22%

@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

link

answered 30 May '17, 11:45

dishant_18's gravatar image

5★dishant_18
61419
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.

link

answered 30 May '17, 13:22

afaxnraner's gravatar image

6★afaxnraner
5915
accept rate: 22%

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

link

answered 30 May '17, 14:30

dishant_18's gravatar image

5★dishant_18
61419
accept rate: 12%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×2,698
×715
×176
×11

question asked: 29 May '17, 12:51

question was seen: 430 times

last updated: 01 Jun '17, 17:55