EDITORIAL
PROBLEM NAME : Draicy & Momos
DIFFICULTY : Easy-Medium
PREREQUISITES : Binary Search
PROBLEM : Draicy enjoys momos and there are N momo stalls at the Momo Carnival. He eats momos in an unusual way, only leaving X momos at each stall. In theory, if a stall has K momos, he will consume K−X momos and leave X momos behind. He must satiate his appetite H at this carnival, which means he must eat at least H momos. He’s also thoughtful of his fellow momo lovers, so he tries to leave as many momos as possible behind, along with satisfying his appetite.
Tell him the maximum number of momos he can leave behind at every stall such that he satiates his hunger.
Note : You have to print -1 if we cannot satiate draicy’s Hunger.
TASK : Calculate the maximum number of momos he can leave behind at every stall such that he satiates his hunger.
CONSTRAINTS :
1 ≤ T ≤ 100
1 ≤ N ≤ 10^5
1 ≤ H ≤ 10^ {12}
1≤ A_i ≤ 10^9
SAMPLE INPUT (1) :
1
5 10
6 2 8 4 5
SAMPLE OUTPUT (1) :
3
EXPLANATION :
Naive Approach :
The range of valid X(Momos left on each stall) is from (0 - Maximum element of the array).
Calculate the number of momos he can eat while leaving X behind for each conceivable value of X.
It is a valid response if the resultant amount is greater than or equal to H(hunger).
We’d look for X+1 and repeat the process until we find the best possible outcome, because we need to maximise the value of X.
If X does not have a valid value, i.e. the total of all the elements < H we print -1.
Else we print the optimal value of X.
Optimal Approach:
By using Binary Search to discover the ideal value of X, we can dramatically minimise the time complexity.
Define a search space ranging from (0 - Maximum entry of the array).
In our binary search, we check the mid value in the search space.
If the current mid value meets our criteria (the resultant amount is higher than or equal to H(hunger)), we consider the right half of the array in relation to our mid value; otherwise, we move in the opposite direction…
This reduces our complexity from N2 to N*log(N).
SOLUTION:
#include<bits/stdc++.h>
using namespace std;
bool pred(long long int x,long long int H,vector<int> &stalls){
long long int sum=0;
for(long long int k : stalls){
if(k-x >= 0){
sum += k-x;
}
}
return (sum >= H);
}
void solve(){
long long int N,H; cin >> N >> H;
vector<int> stalls(N,0);
long long int mx = -1;
for(long long int &x : stalls){
cin >> x;
mx = max(mx,x);
}
long long int lo=0,hi=mx;
while((hi-lo)>1){
long long int mid = lo + (hi-lo)/2;
if(pred(mid,H,stalls)) lo=mid;
else hi = mid-1;
}
if(pred(hi,H,stalls)){
cout << hi << endl;
}
else if(pred(lo,H,stalls)){
cout << lo << endl;
}
else{
cout << -1 << endl;
}
}
int32_t main(){
// sieve();
long long int t;
cin >> t;
long long int counter = 1;
while(t--){
// cout << "Case #" << counter <<": " ;
solve();
counter++;
}
return 0;
}
OPTIMAL COMPLEXITY :
Time - O(N*log(N))
Space - O(1)