TLE on Hussain Set from May Cook-Off 2017

general
, , , ,
1

Hi guys, I’ve been working optimizing the solution of this problem for a long time; and, I’ve no idea now why it’s getting TLE. The complexity is (NlogN + N * 63). Here it is : https://www.codechef.com/viewsolution/13787521

Algorithm is simple. I’ll divide all the elements into 63 stacks as per their log value. Stacks will be processed starting from the one with greatest log value. And, for each element x in the stack, I’ll store x/2 into a queue. While processing the next stack (with lower log value), I’ll also consider the queue created from the previous step.

2

My solution is somewhat similar to your approach, see if it can help :slight_smile:

https://www.codechef.com/viewsolution/13788391

3

Thanks so much. Mine got accepted after initializing the deque with the initial capacity. Seems array copying was wasting execution time.