my idea is to use priority queue and divide the max each time by 2 and push it back manually ,please suggest me how to handle queries? what is your approach??
1 Like
I think u accidently asked the same question twice as https://discuss.codechef.com/questions/99844/how-to-handles-query-in-hussain-set-question. 
ops,Sorry…magic of double click.lol
Haha, no worries 
1 Like
your approach?
I haven’t attempted the problem, i hope someone else gives a more moving solution to your query.
1 Like
okay,still waiting
The priority queue approach will time out as it did for me. For query you have no choice but to emulate each step, atleast for me. If query1 = 1, query2 = 4. You must do the operation required (max to max/2 and then put back) 3 times to answer. This is fine. What you must achieve is to find the max in O(1) and put it back in O(1). PQ, will take log(N) steps. A hint would be , if you have a sorted array in non decreasing order A, then a[i]/2 is less than equal to a[i+1]/2.
can u explain in detail
Sure, but which part do you want me to explain in detail?
how to handle the queries? with array we have to sort every time? its very confusing
** Part 1 **:
Here, the key observation is that, if we have a non decreasing sorted array A, then we have a[i]/2 <= a[i+1]/2. This is the “invariant”. Now suppose, you have built a stack, on this sorted array with the top element as the max. For the first query we have the stack[top] as the answer. We remove this element from the stack and put stack[top]/2 in a “queue”. Now, for the next query you have two choices, either it’s the new top of the stack or the first element in the queue, you can take the maximum of these two elements and print.
Queries can be handled by keeping track of previous query & current query.Suppose previous query was 1 and next is 7.Simply perform the operation (7-1) times and return the ans.
My solution : link text
1 Like
**Part 2 **: Now, once you have printed the element, you have to modify this element to element/2. We push this modified element in the queue and continue the same way as before. You may ask what guarantee’s that this algorithm works, it works because, top of the stack is always the maximum element in the stack (the way we built it) and the front of the queue is the maximum in the queue (due to the invariant).
then how to handle queries? means i will store the max everytime?
No, you just modify the stack and queue each time like I mentioned above. Suppose your first query is 1, the answer is stack[top]/2. Next query is 3. So you do the above process 2 times, and then you find the answer as max(stack[top], queue.front())
great,can u provide easy code(c++/java) for this.
Check my submission on the practice.