HMAPPY — Editorial

Problem Link :

Division 1

Division 2

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

Tester’s Coder : Link

My Code : Link

1 Like

IMO, this question was way tougher than MINDSUM and CCIRCLES in terms of getting the intuition. Surprised to see both the problems getting relatively less successful submissions than this one.

2 Likes

Why cant we use dynamic programming?

please explain

if the girl is given ci candies on the ith day, then we need to give her at least max(0,A[i]−floor(ci/B[i])) more balloons too.

How this formula came?

Even i used the binary search but did not get full points. Can anyone point out the mistake in my code. It is not passing two test cases in sub task 2
https://www.codechef.com/viewsolution/20942154

@restlessninja the only bug i could see is that you have taken ceil, instead of which you need to take floor.

Video solution: https://www.youtube.com/watch?v=UzwNDRjCEE4

1 Like

c_ i =( A[i]-x_i ) \cdot B[i] .

So,

(x_i)= A[i]-floor(c[i]/B[i]), we just rearrange the terms in the equation.

Obviously , we cannot have negative values in both cases, so we take maximum among 0 and that.

3 Likes

Thanks @anand20

Maybe we can use it for smaller constraints. The large constraints here would not allow some dp solution have \ge 2 states to pass

XD not for all…
but yes some of my friends solved my question(CCIRCLES).
but can’t solve this one with that speed.
according to me reason was that condition when one circle is inside the other… many of good coders missed it… mostly people got at least one wrong answer XD

CCIRCLES was quite intuitive but maybe that condition was not for some of them…