PROBLEM LINK:Div1, Div2 DIFFICULTY:EasyMedium 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 #1Iterate 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 #2For this subtask we need something better than bruteforce. Hence, we will try to make someobservations 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".
asked 10 Mar, 07:31

unable to see the solutions , bucket policy needs to be updated . answered 12 Mar, 21:47

I have a doubt. For the following test case:
The answer should be 6. So taking k=6, the above inequality will be calculated as following:
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, 23:53

@philomath_mht the ans. will be 8 as you can only divide maximum (75)=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, 02:06

Simple binary search : Link to solution https://www.codechef.com/viewsolution/17582805 answered 13 Mar, 03:23

Can anyone tell last test case? My solution is https://www.codechef.com/viewsolution/17773507 Can anyone please point out the mistake in my code. Edit: Saw the tester's solution. So basically my calculateHour function was a little different. Tester solution has something like this: for (i = 0; i <len;i++) { total+=(arr[i]+k1)/k; } I tried it and my code got accepted now. Whereas in my solution i had this: for (i = 0; i <len;i++) { if(arr[i]<=k) { total++; } else { total+=(arr[i]/k)+1; } } What was the last test case that gave wrong answer verdict on my solution? Can anyone provide some help? answered 13 Mar, 08:57

can anyone tell me what is the mistake? answered 13 Mar, 20:22

Change int to long long && float to double. Here's your modified solution : answered 14 Mar, 03:13

! Should have tried this. Was just too lazy to do it :p answered 14 Mar, 09:08
