PROBLEM LINK:Setter Igor Barenblat DIFFICULTY:Medium PREREQUISITES:PROBLEM:Given $N$ pairs of integers, find a $subset$ of maximum size such that $min(a_1,a_2,...,a_k) \ge$ $\large \frac{b_1+b_2+..+b_k}{k}$ QUICK EXPLANATION:Key to Success A good grasp over segment tree, implementing it properly and/or good debugging skills can help you get an AC. Implementation practice is a must. We make $2$ arrays of pairs. The first one, $Arr[]$ will store the pair $\{a_i,b_i\}$ and second one $index[]$ will store $\{b_i,i\}$ (where $i$ is the index). We now sort both these arrays. Starting from end of $Arr[]$ (i.e. from the pair with maximum $A_i$ to pair with minimum $A_i$ [helps avoiding finding the minimum $A_i$ every time] ) we try to find maximum number of $\sum_{i=1}^{i=k}b_i$ such that $k*A_i \ge \sum_{i=1}^{i=k}b_i$ which can be done using segment tree. EXPLANATION:This editorial is divided into $23$ sections. The first section will describe the concept and thinking process to solve the question. The second one will brief about implementation as I find it tricky solution. We will refer to tester @mgch solution for that. The concept involved will discuss
1.What to store in segment tree I acknowledge that we can approach this problem in many ways. We will discuss tester's approach here. He decided to store $2$ things $\sum_{i=l}^{i=r}b_i$ in that range, and $rl+1$ (i.e. sum of $b_i$ and number of elements in the given range). Instead of storing them in a single node, he made $2$ arrays for that. Please dont get confused by that :) 2.How we will store and why it works We made $2$ arrays $Arr[]$ and $Index[]$. We will store sorted $\sum_{i=l}^{i=r}b_i$ in the nodes. What does this mean and why does it work? Lets first discuss the proof that its correct and then discuss further working. DING!! Oh no! You hear that alarm? It means its time for some hand exercises! Grab your pen and paper and lets get to it :). Q Given a sorted array $C[]$ such that $C_1 \le C_2 \le C_3 \le ... \le C_k$, prove that $C_1$ $\large \le \frac{(C_1+C_2)}{2} \le \frac{(C_1+C_2+C_3)}{3}...$. I think the standard mathematics proof is simple. Let me give an intuitional proof! Its given in tab below so that it doesnt give spoilers to those who want to give a try! The tester's proof will be given in Chef Vijju's corner. Now, keeping the ahead proof in mind, and our objective to find the maximum size of set, we will query for maximum $k$ such that $\sum_{j=1}^{j=k}b_j +B_i \le (k+1)*A_i$. Here $\sum_{j=1}^{j=k}b_j $ are already in the tree, and we are querying for pair $\{A_i,B_i\}$ Why $(k+1)*A_i?$ Where did the division go? What is this $A_i?$ How is this minimum? The required query is standard. But wait! How do we guarantee that the $B_i$ chosen are only from the pairs such that their $A_i$ are greater than or equal to the current $A_i$ we are using this as minimum? This will be discussed in next section, where we will complete whats exactly stored in the tree and how/why it works. Make sure that the question/proof given to you above is clear! 3. Query and Update Now, you guys would be at least a little confused. Things were going smooothly but then this evil editorialist threw up an evil question on your face :( Well, turns out its simple to fix as well! Instead of building tree at once, we build it step by step. What we do, is, that the tree is initially empty. As we iterative from pairs with maximum $A_i$ to minimum $A_i$, we add the $B_i$ to the tree by updating the tree. Reference code is below What do we do in update function? For that, lets first discuss relation between parent and child. Recall that we are storing "storing sorted $\sum_{i=l}^{i=r}b_i$, and the number of elements (for convenience purposes only)in the nodes". So, what can the relation be? If we know the information in $[L,mid]$ and the information in $[mid+1,R]$, how can we calculate information for $[L,R]??$ Can you now, knowing the relation between nodes, try to frame the update and query function? In update function you have to update correct leaf and hence its parents, and in query you must obtain the result. Reference codes of tester (iterative) are given below. do try to put them in recursive for practice :) upd function is given below The query function is also easy. The tester used iterative segment tree. The query function (along with update) is given below Now your turn! Refer to tester's code. Right now, you might feel its easy to do. Try writing your own recursive version of the code! You will face a few (or many) WA, dont worry. Debug them, that will give you tremendous improvement. Refer to editorial, ask doubts! Dont get disheartened by WAs :). Debugging segment tree sometimes give headaches even to red coders, so practice the proper implementation by writing the recusrive solution! SOLUTION:The codes which I received are pasted below for reference. This is done so that you dont have to wait for @admin to link solutions up. Please copy them and paste at a place where you are comfortable to read :). Editorialist's solution will be put on demand. Edit A lot of people have been expressing their unability to be able to come up with a recursive function of tester's solution. Its ok, its a part of learning. I will update editorialist's solution for you to cross check. The code also has some questions related to implementation. Further, I have added one test file in test case bank. Its huge, but it was the most trickiest one, so I hope it helps. Please mail me/ping me if there are ANY concerns. Thank you :) Editorialist's Solution (Recursive Segment Tree) $Time$ $complexity=$ $O(NlogN)$ CHEF VIJJU'S CORNER:1. I mentioned a line in the comments of query function. 2. Tester's Notes 3. Tester's Proof 4. Read tester's notes. He said something about "Tree must have ${2}^{l}$ leaves" for his iterative version to work. Why? 5. Refer to tester's solution. Try to write a recursive solution to the same. :) 6. Test Case Bank 7. OMG YOU READ TILL HERE? Here, I have an awesome blog on segment trees for you :) . Click here 8. Related Problems
This question is marked "community wiki".
asked 16 Jun '18, 18:54

@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 :) answered 18 Jun '18, 18:57
complexity O(nlogn)
Nice Approach @tihorsharma.. got Ac in java
(19 Jun '18, 01:49)
1
Thank you :)
(19 Jun '18, 01:56)

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. answered 18 Jun '18, 01:09

@vijju123 Tester's code gives wrong answer for following case answered 22 Jun '18, 23:29
Will inform him that his solution got hacked xD. Nice job. The setter's solution (used to make TC) is correct. The idea is also correct, he made a minor bug in implementation, so no major problem. Thanks :)
(23 Jun '18, 01:25)

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. answered 18 Jun '18, 00:52
1
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 :)
(18 Jun '18, 01:03)
@soham1234 @vijju123 Can you please tell me why my code is giving me WA. Thanks https://www.codechef.com/viewsolution/18941742
(18 Jun '18, 19:52)

@soham1234 can you please explain your solution a bit more elaborately (the significance of blocked array)
answered 18 Jun '18, 01:02

min(a1,a2,...,ak)≥ (b1+b2+..+bk)/k , can we solve this query using binary search ? answered 18 Jun '18, 18:04
I did saw some solutions using binary search. I think we can!
(18 Jun '18, 18:09)
I'm also searching soln similar with this idea. If someone finds or had done this. Do post their soln here.
(18 Jun '18, 19:25)
@aryanc  Check accepted answer of @tihorsharma123 , he used Binary Search afaik
(18 Jun '18, 19:39)

@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. answered 18 Jun '18, 21:36
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.
(18 Jun '18, 21:41)
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.
(18 Jun '18, 21:43)
Yes, I tried that proof. When searching for appropriate subset, why does popping minimum element in array B work ?
(18 Jun '18, 21:43)
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 :)
(18 Jun '18, 21:53)

Here is my recursive implementation of the testers solution. https://www.codechef.com/viewsolution/19229847 answered 15 Jul '18, 17:09

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?
@vijju123 @ay2306 is asking for purpose of sorting. And how it is helpful here.
He should check the proof and hand exercises then. I think the proof and deduction via it is the best way for him :)