MINEAT - Editorial

PROBLEM LINK:

Div1, Div2
Practice

Author: Praveen Dhinwa
Tester: Triveni Mahatha
Editorialist: Adarsh Kumar

DIFFICULTY:

Easy-Medium

PREREQUISITES:

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*}{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*}{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*}{K} \right \rceil \le H.

Subtask #1

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.

Subtask #2

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

Setter's solution
Tester's solution

2 Likes

why can’t I see the solution?? the links don’t work

unable to see the solutions , bucket policy needs to be updated .

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

@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

Simple binary search : Link to solution https://www.codechef.com/viewsolution/17582805

can anyone tell me what is the mistake?

https://www.codechef.com/viewsolution/17824477

Change int to long long && float to double. Here’s your modified solution :

https://www.codechef.com/viewsolution/17827412

@dharmick

! Should have tried this. Was just too lazy to do it :stuck_out_tongue:

Please tell what’s wrong with my solution
here

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.

https://www.codechef.com/viewsolution/17841507

Can someone tell me what’s wrong with this???

https://www.codechef.com/viewsolution/17889934

can someone tell me what’s wrong with this??

Can someone tell me what is the mistake in my code:
https://www.codechef.com/viewsolution/17768075

my solution:
https://www.codechef.com/viewsolution/17587199

I was getting a PA with my solution and just after I changed

**
ans += std::ceil((float)a*/k); to 
ans += (a* + hr - 1)/hr ;
**

it go AC…will someone please explain how the latter is different then the first one?

what if we sum all the piles and divide them with the no. of hours given and
take the upper bound of the quotient.

simple code for beginners using binary search …link to my sol.