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

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

1 Like

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 CodeChef: Practical coding for everyone

1 Like

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 -CodeChef: Practical coding for everyone
Do upvote if you find useful.

1 Like

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

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.

what is wrong with my code . anyone please help .
CodeChef: Practical coding for everyone .

Is there any list of other test cases beyond what is posted in the hints section. I’m matching all those 100%, and have come up with a few test cases of 100+ number and 10000+ hours and my solution seems okay to me, but I fail every test on submission.

I’m sure I’m just missing something dumb, but can’t figure it out.