COOK82C - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Hussain Kara Fallah
Primary Tester: Hasan Jaddouh
Secondary Tester: Istvan Nagi
Editorialist: Udit Sanghi

DIFFICULTY:

EASY-Medium

PREREQUISITES:

Queue

PROBLEM:

Given an array of numbers and m queries. You have the keep doing the following operation -
Divide the take the maximum number and divide it by 2. Now for each query, tell the number we were taking in the Q[i]th operation

QUICK EXPLANATION:

Take 2 queues, q1 and q2. Push all elements in decreasing order to q1. Now as you are taking the elements see the maximum of q1 and q2, store it and then divide it by 2 and push it in q2. When q1 becomes empty then only look at q2.

EXPLANATION:

First let’s calculate the constraint on Q[i]. So a[i] < 2^{63}. This means that at most an element will can be divided 63 times before reaching 0. And, there are totally 10^6 items. That means that Q[i] will be at max 63(10^6).

First of all, can u think of a brute-force solution.
Just keep doing all stuff manually like taking the maximum in an array and then dividing it by 2 and putting in the array again. This will take time O(n*6.3*{10^6}).

Now, can we do better.
So taking the max right now takes O(n). We can reduce this to O(log n) by using a priority_queue.
Now the complexity will be This will take time O(logN*6.3*{10^6}).

Hmm… Too slow. We need to do this operation in constant time.

Here’s a key observation -

After every number has been once divided, you only need to divide the numbers again in the same order as before. So, currently it doesn't make much sense but it will once you see an example.
Before that, you only need to compare between the highest number which has been divided yet and which has not been divided yet.

n = 5
old_a = [28,25,17,14,13]
new_a = []
// old array contains the element which have not yet been divided yet and new array contains those which have been divided atleast once.
operation 1 - 28
old_a = [25,17,14,13]
new_a = [14]

operation 2 - 25
old_a = [17,14,13]
new_a = [14,12]

operation 3 - 17
old_a = [14,13]
new_a = [14,12,8]

operation 4 - 14
old_a = [13]
new_a = [14,12,8,7]

operation 5 - 14
old_a = [13]
new_a = [12,8,7,7]

operation 6 - 13
old_a = []
new_a = [12,8,7,7,6]

// Now you will realize that we only select [12,8,7,7,6] in order now and keep dividing them.
Like 12,8,7,7,6,12/2,8/2,7/2,7/2,6/2,(12/2)/2,(8/2)/2 etc.

For these purposes we can use a queue.
Make 2 queue, q1 and q2.
Push all elements in q1 in decreasing order.
Now for the first operation u’ll choose the maximum element which is the front of q1 and push half of that number in q2.
After that, you’'l have 2 queues to choose from q1,q2, choose the queue which has has the maximum element and keep repeating this until… q1 is empty.
Then, you can just repeat the process with the elements of q2.
Remember to store the answer after each operation. Then, process the queries and answer the queries with the answers you stored.

EDITORIALIST’s, AUTHOR’S AND TESTER’S SOLUTIONS:

EDITORIALIST’s solution: [Here] 333
AUTHOR’s solution: [Here] 444
TESTER’s solution: [Here] 555

1 Like
2

how to handle the query? can anyone explain this?

3

“Now you will realize that we only select [12,8,7,7,6] in order now and keep dividing them”

Can I get a proof of this?

4

@prakhariitd `In making of new_a ,at every point we are ensured that new_a’s first element is at max = 2*(new_a’s last) + 1. Now while choosing max from old_a and new_a, let ‘a’ be max in old_a and ‘b’ be max in new_a ,there are two cases :-

  1. ‘a’ >= ‘b’. i.e. ‘a’/2 >=‘b’/2 . Now ‘a’/2 will be inserted at last of new_a satisfying ‘b’<= (2*(‘a’/2))+1.
  2. ‘a’ < ‘b’ . i.e. ‘b’/2 will be inserted at end of new_a and because all elements in new_a were between [‘b’,‘b’/2] the new max of new_a (let it be ‘c’) will keep on satisfying the property ‘c’<=(2*(‘b’/2))+1 as ‘c’<=‘b’.`

And once old_a ends we are sure that the element to be inserted at end of new_a will be lesser than or equal to its current last element , hence giving us freedom to go ahead with that single queue only i.e. new_a .
Hope that helps.

5

@vivek96 just store all the queries in an array or vector.According to the above solution you will have all the answers in an array . you can then use these queries to find the answer.for eg if the query is 3 you can use ans[3].Hope it helps.

6

In The Editorialist’s Soln - When Both The Queue’s have Elements, and in the else condition, it is given that-

   ans[i] = y;
            q2.push(y/2);
            q2.pop();
but should'nt it be - 

     ans[i] = y;
            q1.push(y / 2);
            q2.pop();
because when we are popping from the second queue should'nt the value  be pushed in the first queue.

Please Help.

7

Can someone tell me why priority queue can not be used
i am getting TLE for this
https://www.codechef.com/viewsolution/17204471

@mathecodician plzz help

8

I also tried to solve it using a priority queue and got TLE. Let me explain why.

  1. insertion, deletion takes O(log(N))
  2. Each number can be divided 63 times, so there can be 63*N number of sequences total
  3. total time complexity is O(log(N)63N) = O(2063N) = O(1.2 * 10^9) Hence TLE.
1 Like
9

what is diffrence in two implementations of finding MSB

  1. AUTHOR’s solution

    for(ll i = 62 ; i >= 0 ; i–){
    if( (arr[j] & (1ll<<i)) ){
    bucket[i].push_back(arr[j]);
    break;
    }
    }

2)TESTER’s solution

int cnt(long long x){
int ret=0;
while(x){
	ret++;
	x/=2;
}
return ret;
}

My solution is getting accepted by finding MSB with Author’s method But Getting WA with Tester’s method
Could Anyone Please Explain.