Problem Link :
Author : Himanshu Mishra
Tester : Misha Chorniy
Editorialist : Anand Jaisingh
Pre-Requisites :
Binary Search
Explanation :
First of all, let’s think : We already have M balloons with us. There is an imaginary shop, that is willing to supply any number of candies to us, but at a cost
Now, on each day we need to buy certain number of candies ( maybe 0 ) from the shop and give it to the girl, so that she remains happy each day, and we never need to buy an additional balloon. We need to minimize the maximum over the number of candies we purchase each day over the N days.
If on the i^{th} day, the girl is given x_i balloons, then she will be happy if given a minimum of c_i = max(0,( A[i]-x_i) \cdot B[i]) more candies too. Let’s invert this, if the girl is given c_i candies on the i^{th} day, then we need to give her at least max(0,A[i]-floor(c_i/B[i])) more balloons too.
Now, let’s fix a particular value of the maximum number of candies I’m going to purchase over all days. Let this value be k, i.e assume max( c_1,c_2...c_n ) = k . So, we just assume now, that we purchase exactly k candies each day, i.e c_i=k for all i , since giving more candies is always going to help us use lesser balloons, and the maxima over the N days is still k.
Then, on day i, to be happy , the girl requires at least max(0,A[i]-(k/B[i])) more balloons, But remember, we cannot buy a balloon. So, we need sum of the max(0,A[i]-(k/B[i])) to be \le M . So, we need to find the minimum value of k, such that considering I give the girl the minimum number of balloons required each day after giving her k candies, then that sums to a number \le M .
We can try all k over some range for the first sub-task. To proceed to the second sub-task :
Claim : As the value of k increases, the sum of the minimum number of balloons to be given to the girl each day decreases.
This is very intuitive, just think about it. So, we need to try and find the minimum value of k, such that the sum required is \le M . But linear search with a break is still is bad.
Now, next we can actually binary search over the required minimum value of k. Assume we reach a particular mid of the binary search. Now, use this mid as k, giving the girl minimum number of additional balloons each day, and check if it sums to something \le M . If yes, go \le mid , else go > mid .
For example, the pseudo code for this would look something like :
while(low < high)
{
int mid=(low+high)/2;
long long now=0;
for(int i=0;i < n;i++)
{
long long curr=max(0,A[i]-(mid/B[i])));
now+=curr;
}
if(now<=m)
{
high=mid;
}
else
{
low=mid+1;
}
}
Time Complexity : O(N \cdot log (10^{18})) . Why setting high=10^{18} works : Consider the worst case, N=10^5, M=0, A[i]=10^9 , B[i]=10^9, 1 \le i \le N . So, On each day we have to make the girl happy with only candies, and the maximum value of A[i] \cdot B[i] can be 10^{18}.