min(a1,a2,…,ak)≥ (b1+b2+…+bk)/k , can we solve this query using binary search ?
Can anyone provide a solution without using segment tree? With detailed explanation.
1 Like
@akshatsharma Yes , I solved it using binary search. We can binary search on the maximum size of the subset. Now to check if it is possible to form a good subset of size “k”, we first make a pair of { power , endurance } and sort it in descending order of power. Now we iterate from the highest power to lowest power. When we are at any index idx, its corresponding power will be minimum from 1 to idx and we can consider all endurances from 1 to idx - 1 and take the minimum k - 1 endurances. We can keep track of k - 1 minimum endurances using priority queue.
Let the sum of minimum k - 1 endurances be sum , then if power[idx] * k >= (sum + endurance[idx] ) , then it is possible to form a good subset of size k. Unfortunately, due to a silly bug I couldn’t get it accepted during contest 
. AC Code. Do let me know if you didn’t understand anything 
12 Likes
@tihorsharma123 @vijju123, why are you maintaining “ascending order or sorted B array of k elements” when doing binary search. I don’t understand why is it necessary for array B to be sorted in ascending order.
int mainquery(ll x,ll y)
{
int lo=0;
int hi=n-1;
int k=0;
int ans=0;
while(lo<=hi)
{
int mid=(lo+hi)/2;
k=query1(1,0,n-1,0,mid); // the number of element
ll val=query2(1,0,n-1,0,mid); // the sum in given range
if((x*1LL*(k+1)*1LL)>=(val+y))
{
ans=k+1;
lo=mid+1;
}
else
hi=mid-1;
}
return ans;
}
its the query function i wrote with binary search , its passing the case in testcase bank but getting WA , help me debug
@vijju123 Tester’s code gives wrong answer for following case
1
12
10 100
12 1
12 1
12 1
12 1
12 1
12 1
12 1
12 1
12 1
12 1
12 100000000
correct answer is 11 whereas Tester’s code outputs 10.
1 Like
Here is my recursive implementation of the testers solution.
https://www.codechef.com/viewsolution/19229847
Yes. Even my intuition was that segment tree can be avoided. But I had no time to experiment as I wanted to publish editorials on time. Theres a reason why its said “Editorialist’s solution to be provided on demand” instead of giving it by default. I feel without proper investigation/explorations they wont be worthy enough 
1 Like
I did saw some solutions using binary search. I think we can!
I’m also searching soln similar with this idea. If someone finds or had done this. Do post their soln here.
Where you stated that we find maximum k such that,
\sum_{j=1}^{k} b_{j} + B_{i} <= (k+1)*A_{i}
I dont understand why we \sum b_{j} from 1 to k, we could have found maximum and why not for some other l and r?
What?
I had to use some notation to convey that we are querying over sum of b_j. I think you are getting unnecessarily confused?
@soham1234 @vijju123 Can you please tell me why my code is giving me WA. Thanks
https://www.codechef.com/viewsolution/18941742
He should check the proof and hand exercises then. I think the proof and deduction via it is the best way for him
1 Like
Did you try this proof-
Q- Given a sorted array C[] such that C1≤C2≤C3≤…≤Ck, prove that C1 ≤(C1+C2)/2≤(C1+C2+C3)/3.
Because of the inequality given in the question. In my approach ,I fixed the size of the subset ( let it be k ) and current minimum to be pow. Then pow >= (b1 + b2 + … bk) / k which is nothing but pow * k >= (b1 + b2 + … bk) . Therefore using greedy approach it makes sense to take the minimum k values of B array. Hope it helps. Let me know if something is unclear.
Yes, I tried that proof. When searching for appropriate subset, why does popping minimum element in array B work ?
You want fit in as many balls in a bag of weight W. What do you chose? Lighter balls or heavy balls? We only have to maximise number of balls in bag.
Then apply the logic to current scenario. Thanks @tihorsharma123 for helping me