I don’t think segment tree is necessary. We see that if we store {bi,i} in increasing order then our pointer always moves right. Also only case where it might fail is when the bi we are going to include belongs to some ai which is less than our current minimum. But this can be tackled introducing blocked array.
3 Likes
@soham1234 can you please explain your solution a bit more elaborately (the significance of blocked array)
only case where it might fail is when the bi we are going to include belongs to some ai .
What does it mean?
Yes surely. See what I am doing is sorting at first wrt to ai, then taking a seperate array which stores {bi,i} (here i is the index after sorting first time) and then sort that 2nd array. You can easily see for a[0] you can include all the elements if you want. Formally for any ai, you need sum of b’s in sorted order from i to n. Also note that once a bk gets included for some aj, it’s not removed for some ai>aj until bk belongs to some ak<ai.(WHY? Because otherwise ak will be the minimum.) . So for this reason I introduced the blocked array so that I don’t include some bk in my answer when ai is the current minimum and ak<ai, where {ak,bk} was a pair. Have a look at my implementation, hopefully you will understand.
3 Likes
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.