MINEAT - Editorial


Div1, Div2


Author: Praveen Dhinwa

Tester: Triveni Mahatha

Editorialist: Adarsh Kumar




Binary search


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.


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:



Setter’s solution

Tester’s solution


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

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.


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


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



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

Please tell what’s wrong with my solution

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.


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


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

Can someone tell me what is the mistake in my code:

my solution:

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?