need the editorial for cook82c

editorial
,
1

can somebody post the editorial for cook82c

2

I am also looking for it, but not able to find. :frowning:

3

You just need two Stacks and a Queue.

→ First of all, get all element and keep it in first Stack.

→ Sort all with increasing order.

→ Have a queue.

Do this repetion with rule:

  1. If queue empty and stack not empty, pop last element in stack and divide by two and keep in queue.

  2. If queue not empty and stack not empty then:

    a. If front element >= stack element: pop element in queue, divide by two, and push to queue again.

    b. Else pop last element in stack, divide by two, and push to queue.

  3. If stack empty and queue not empty, pop front element in queue and divide by two and push back to queue.

  4. Else, all element already processed

*Note: keep all solution in second stack. Don’t queue an element if element/2 < 1.

*Code: TVLAiq - Online C++ Compiler & Debugging Tool - Ideone.com

Edit 1: First case miss type, change to “Queue empty and Stack not Empty”

1 Like
4

I used a priority queue and got wrong ans. just insert all elements in a priority queue and output the max element in O(1) and keep on removing top element and inserting the half of it when the next query comes. here is the link to my code CodeChef: Practical coding for everyone

5

Here is my solution for COOK82C in a lot easier manner with the above mention approach.
https://www.codechef.com/viewsolution/13780820

6

This is O(NlogN + 63*N) right (in worst case)?

And also a small correction in first point,

  1. If queue is empty and stack is not empty*
7

Yes,

thanks for the correction

8

Can someone post the solution based on priority queue? I used priority queue but got TLE.