VACCNE - Editorial

editorial
,
1

PROBLEM LINK:

Contest
Author: Tejus Kaw
Tester: Rahul Sharma
Editorialist: Tejus Kaw

DIFFICULTY:

Easy

PREREQUISITES:

Binary Search

QUICK EXPLANATION :

HERE BASICALLY WHAT WE ARE DOING IS THAT WE ARE FIXING THE MAXIMUM AMOUNT OF FINE IN N DAYS AND AFTER GIVING THE FINE WE HAVE TO CHECK WHETHER THE REQUIRED VACCINES IN TOTAL IS LESS THAN M OR NOT . FOR FINDING k(maximum fine in n days) we can simply use lower_bound of binary search. :smiley:

EXPLANATION :

In starting the approach will be of using a heap and in each iteration , the one with maximum total_fine , we will give a vaccine.But on seeing the Constraints it will lead to TLE.

If on the i^{th} day, the city is given x_i vaccines, then city is given a minimum of c_i = max(0,( A[i]-x_i) \cdot B[i]) fine too. Let’s invert this, if the city is given c_i fine on the i^{th} day, then we need to give city at least max(0,A[i]-floor(c_i/B[i])) more vaccines too.

Now, let’s fix a particular value of the maximum fine I’m going give 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 give k amount of fine each day, i.e c_i=k for all i, since giving more fine is always going to help us use lesser vaccine , and the maxima over the N days is still k.

Then, on day i, the city requires at least max(0,A[i]-(k/B[i])) more vaccines , But remember, we cannot have extra vaccines . 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 it we give city minimum number of vaccines required each day after giving k amount of fine, then that sums to a number \le M .

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. REMEMBER A[i]â‹…B[i] can be 10^{18}.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std; 
typedef complex<double> base;
typedef long double ld;
typedef long long ll; 
#define pb push_back
#define pii pair<int,int>
#define pll pair< ll , ll >
#define vi vector<int>
#define vvi vector< vi > 
const int maxn=(int)(1e5+5);
const ll mod=(ll)(1e9+7);
ll a[maxn],b[maxn];
int n;ll m; 
bool check(ll mid)
{
    ll add=0;
 
    for(int i=0;i<n;i++)
    {
        ll now=a[i]-(mid/b[i]);
 
        add+=max(0ll,now);
 
        if(add>m)
        {
            return false;
        }
    }
 
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
 
    cin>>n>>m;
 
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
 
    for(int i=0;i<n;i++)
    {
        cin>>b[i];
    }
 
    ll low=0,high=(ll)(1e18);
 
    while(low<high)
    {
        ll mid=(low+high)>>1;
 
        if(check(mid))
        {
            high=mid;
        }
        else
        {
            low=mid+1;
        }
    }
 
    cout<<low<<endl;
 
    return 0;
}