MINEAT - Editorial

editorial
, , , ,
1

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
2

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

3

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

4

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

5

@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

6

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

7

can anyone tell me what is the mistake?

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

8

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

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

@dharmick

9

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

10

Please tell what’s wrong with my solution
here

11

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.

12

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

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

13

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

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

14

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

15

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

16

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?