You are not logged in. Please login at www.codechef.com to post your questions!

×

MINIONS - Editorial

2
1

PROBLEM LINK:

Div1
Div2
Practice

Setter- Igor Barenblat
Tester- Misha Chorniy
Editorialist- Abhishek Pandey

DIFFICULTY:

Medium

PRE-REQUISITES:

Segment Tree

PROBLEM:

Given $N$ pairs of integers, find a $sub-set$ 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 $2-3$ 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-

  • What to store in segment tree?
  • How will we store and why it works?
  • Query and Updates. Implementation is integrated with this section.

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 $r-l+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!!
DING!!
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!

View Content

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?

View Content

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.

View Content

Reference code is below-

View Content

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]??$

View Content

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-

View Content

The query function is also easy. The tester used iterative segment tree. The query function (along with update) is given below-

View Content

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 :).

Setter

View Content

Tester

View Content

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. //Even child (2n) has lesser sum than (2n+1) child.. Prove this. Hint in tab below. (You may assume same number of terms in both nodes)

View Content

2. Tester's Notes-

View Content

3. Tester's Proof-

View Content

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-

View Content

7. OMG YOU READ TILL HERE? Here, I have an awesome blog on segment trees for you :) . Click here

8. Related Problems-

  • Set of Questions
  • One question from Hackerearth. Check out their section for more! Refer to my previous segment tree editorials as well for more :)
This question is marked "community wiki".

asked 16 Jun '18, 18:54

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 20 Jun '18, 14:06

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?

(18 Jun '18, 19:47) ay23064★

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?

(18 Jun '18, 19:51) vijju123 ♦♦5★

@vijju123 @ay2306 is asking for purpose of sorting. And how it is helpful here.

(18 Jun '18, 20:23) aryanc4035★
1

He should check the proof and hand exercises then. I think the proof and deduction via it is the best way for him :)

(18 Jun '18, 20:29) vijju123 ♦♦5★

@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 :)

link

answered 18 Jun '18, 18:57

tihorsharma123's gravatar image

2★tihorsharma123
49918
accept rate: 15%

complexity O(nlogn) Nice Approach @tihorsharma.. got Ac in java
https://www.codechef.com/viewsolution/18943916

(19 Jun '18, 01:49) hemant_dhanuka5★
1

Thank you :)

(19 Jun '18, 01:56) tihorsharma1232★

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.

link

answered 18 Jun '18, 01:09

soham1234's gravatar image

6★soham1234
1.8k614
accept rate: 22%

@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.

link

answered 22 Jun '18, 23:29

ankurdua15's gravatar image

6★ankurdua15
611
accept rate: 33%

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) vijju123 ♦♦5★

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.

link

answered 18 Jun '18, 00:52

soham1234's gravatar image

6★soham1234
1.8k614
accept rate: 22%

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) vijju123 ♦♦5★

@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) underdog_eagle4★

Can anyone provide a solution without using segment tree? With detailed explanation.

link

answered 18 Jun '18, 18:50

romok's gravatar image

3★romok
113
accept rate: 0%

i do agree with you that it would be so appreciable if setter has added comments in his code , that would make it lot easier.

(19 Jun '18, 10:29) gyanendra3713★

@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?

link

answered 18 Jun '18, 01:02

aman_robotics's gravatar image

6★aman_robotics
1217
accept rate: 6%

edited 18 Jun '18, 01:08

min(a1,a2,...,ak)≥ (b1+b2+..+bk)/k , can we solve this query using binary search ?

link

answered 18 Jun '18, 18:04

akshatsharma's gravatar image

4★akshatsharma
282
accept rate: 0%

I did saw some solutions using binary search. I think we can!

(18 Jun '18, 18:09) vijju123 ♦♦5★

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) aryanc4035★

@aryanc - Check accepted answer of @tihorsharma123 , he used Binary Search afaik

(18 Jun '18, 19:39) vijju123 ♦♦5★

@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.

link

answered 18 Jun '18, 21:36

rajesh_xyz's gravatar image

0★rajesh_xyz
11
accept rate: 0%

edited 18 Jun '18, 21:40

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) vijju123 ♦♦5★

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) tihorsharma1232★

Yes, I tried that proof. When searching for appropriate subset, why does popping minimum element in array B work ?

(18 Jun '18, 21:43) rajesh_xyz0★

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) vijju123 ♦♦5★
1

No problem :) @vijju123

(19 Jun '18, 01:56) tihorsharma1232★
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

link

answered 19 Jun '18, 13:01

akshatsharma's gravatar image

4★akshatsharma
282
accept rate: 0%

All the test cases were maximal, so official cases wont help. I will try to add few more cases.

(19 Jun '18, 13:38) vijju123 ♦♦5★

issue solved i was using int instead of long long .

(20 Jun '18, 13:46) akshatsharma4★

Here is my recursive implementation of the testers solution. https://www.codechef.com/viewsolution/19229847

link

answered 15 Jul '18, 17:09

sorablaze_11's gravatar image

4★sorablaze_11
1
accept rate: 0%

Good job dear. Hope you liked the editorial :)

(15 Jul '18, 21:31) vijju123 ♦♦5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,658
×1,768
×46
×34

question asked: 16 Jun '18, 18:54

question was seen: 2,493 times

last updated: 15 Jul '18, 21:31