×

# MINEAT - Editorial

Div1, Div2
Practice

Author: Praveen Dhinwa
Tester: Triveni Mahatha

Easy-Medium

Binary search

# PROBLEM:

You are given an array $A$ of $N$ integers. You need to find the smallest $K$ that satisfies this inequality; $\sum \limits_{i=1}^N \left \lceil \frac{A[i]}{K} \right \rceil \le H$, where $\left \lceil \right \rceil$ indicates the ceil function.

# EXPLANATION:

According to the problem statement, Chef will need $\left \lceil \frac{A[i]}{K} \right \rceil$ hours to finish the $i^{th}$ pile. Hence, we need to find the smallest $K$ that satisfies this inequality; $\sum \limits_{i=1}^N \left \lceil \frac{A[i]}{K} \right \rceil \le H$.

Iterate over values of $K$ from $1$ to $MAX$ and break whenever you find the solution. Time complexity for the same will be $O(N.MAX)$, where $MAX$ is maximum element that can be present in the array.

For this subtask we need something better than brute-force. Hence, we will try to make some-observations first. Lets name the left side of our function as cost function. Observe that, our cost function is inversely proportional to $K$. Our cost function will decrease while $K$ increases. At some point it will become smaller than $H$. We need to find this point. Observe that, this problem has reduced to standard formulation of binary search problem. We just need to binary search on values of $K$ now and change the limits of $K$ according to the difference between our cost function and $H$. For more implementation details, you can have a look at attached solutions.

# Time Complexity:

$O(N.log(MAX))$

# AUTHOR'S AND TESTER'S SOLUTIONS

This question is marked "community wiki".

306719
accept rate: 7%

19.7k350498541

 0 why can't I see the solution?? the links don't work answered 12 Mar '18, 17:26 1 accept rate: 0%
 0 unable to see the solutions , bucket policy needs to be updated . answered 12 Mar '18, 21:47 1.2k●11 accept rate: 19%
 0 I have a doubt. For the following test case: 5 7 9 3 8 10 5 The answer should be 6. So taking k=6, the above inequality will be calculated as following: 9/6 + 3/6 + 8/6 + 10/6 + 5/6 (Ceil of all the terms are added) 2 + 1 + 2 + 2 + 1 =8 Hour available is 7, so am I doing something. If there's any problem in logic, please point out the correct solution to above test case and logic. Thanks answered 12 Mar '18, 23:53 1 accept rate: 0%
 0 @philomath_mht the ans. will be 8 as you can only divide maximum (7-5)=2 bunch of bananas and the minimum required bananas that should be eaten is 8. 9/8 + 3/8 + 8/8 + 10/8 + 5/8 = 2 + 1 + 1 + 2 + 1 = 7 answered 13 Mar '18, 02:06 0●1 accept rate: 0%
 0 Simple binary search : Link to solution https://www.codechef.com/viewsolution/17582805 answered 13 Mar '18, 03:23 240●1●10 accept rate: 13%
 0 can anyone tell me what is the mistake? https://www.codechef.com/viewsolution/17824477 answered 13 Mar '18, 20:22 3★dharmick 1 accept rate: 0%
 0 Change int to long long && float to double. Here's your modified solution : https://www.codechef.com/viewsolution/17827412 answered 14 Mar '18, 03:13 1●1 accept rate: 0%
 0 ! Should have tried this. Was just too lazy to do it :p answered 14 Mar '18, 09:08 39●2 accept rate: 7%
 0 Please tell what's wrong with my solution here answered 15 Mar '18, 16:57 5 accept rate: 0%
 0 you can look at my code. its almost similar to your code(99%same) link -https://www.codechef.com/viewsolution/17841451 Do upvote if you find useful. answered 15 Mar '18, 18:00 3★ankush23 31●4 accept rate: 0%
 0 https://www.codechef.com/viewsolution/17841507 Can someone tell me what's wrong with this??? answered 15 Mar '18, 18:43 2★rak_9792 11●2 accept rate: 0%
 0 https://www.codechef.com/viewsolution/17889934 can someone tell me what's wrong with this?? answered 18 Mar '18, 21:02 2★rohitp12 2 accept rate: 0%
 0 Can someone tell me what is the mistake in my code: https://www.codechef.com/viewsolution/17768075 answered 28 Mar '18, 22:10 1 accept rate: 0%
 0 my solution: https://www.codechef.com/viewsolution/17587199 answered 21 Apr '18, 18:12 1 accept rate: 0%
 0 I was getting a PA with my solution and just after I changed ** ans += std::ceil((float)a[i]/k); to ans += (a[i] + hr - 1)/hr ; ** it go AC...will someone please explain how the latter is different then the first one? answered 01 Aug '18, 01:26 64●5 accept rate: 9%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,491
×1,648
×1,023
×265
×5

question asked: 10 Mar '18, 07:31

question was seen: 5,939 times

last updated: 01 Aug '18, 01:26