Problem Link:
Author: Sufiyan Ansari
Tester: Chirantan Muliya , Tushar Sain
Editorialist: Sufiyan Ansari
Difficulty
EASY-MEDIUM
PREREQUISITES
Binary Search Over Solution
EXPLANATION & SOLUTION:
This is a simple BSOS (Binary Search Over Solution).
As we are asked to find the minimum speed for completion of task, let’s first find the possible values of speed K.
As speed is positive, we can have minimum possible K as 1.
In case of maximum possible, as mentioned in
problem day_to_complete_garland = ceil( basket / k )
Ao, for any speed more than max(B) the answer would be same k = max(B) i.e. maximum value of
array. It will take N days to complete (as per question M>=N, so no chance of invalid input)
Hence, we can have speed range for 1 to Bmax. Now we can use binary search over this limit and see
for which minimum speed K the conditions still holds true i.e., days to complete garland <= M
Algorithm:
int minimumSpeed():
L = 1, R = max(B)
while L <= R:
K = (L+R)/2
if (days_with_speed(K) <= M):
ans = K
R = K – 1 #doing this to find even smaller solution if possible
else:
L = K + 1
return ans
Time Complexity: O(NlogN)
However, if you try to use brute force by having complexity O(TN), then it will surely give TLE as constraints does not allow that.
Setter's Solution
#include<bits/stdc++.h>
#define ll long long intp
using namespace std;
long days(vector < long > & basket, long h) {
long ans = 0;
for (long i: basket) {
ans += i / h;
if (i % h) ans++;
}
return ans;
}
long minSpeed(vector < long > & basket, long h) {
long mi = -1;
for (long i: basket)
mi = max(mi, i);
long l = 1, r = mi, ans = 0;
while (l <= r) {
long m = (l + r) / 2;
if (days(basket, m) <= h) {
ans = m;
r = m - 1;
} else l = m + 1;
}
return ans;
}
int main() {
long t;
cin >> t;
while (t--) {
long n, m;
cin >> n >> m;
vector < long > basket(n);
for (long i = 0; i < n; i++)
cin >> basket[i];
cout << minSpeed(basket, m) << "\n";
}
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define loopf(i,a,b) for(ll i=a;i<b;i++)
#define loopb(i,a,b) for(ll i=a;i>b;i--)
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ff first
#define ss second
#define vc vector
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mapii map<int,int>
#define mapll map<ll,ll>
#define all(x) x.begin(),x.end()
#define endl "\n"
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define read(a) for(auto &i:a)cin>>i
#define print(a) for(auto i:a)cout<<i<<" "
#define ub(v,i) upper_bound(all(v),i)
#define lb(v,i) lower_bound(all(v),i)
const ll M=1e9+7;
const ll N=100001;
bool checker(ll k,ll b[],ll n,ll m)
{
loopf(i,0,n)
m-=(b[i]/k+(b[i]%k!=0));
return m>=0;
}
void solve()
{
ll n,m;
cin>>n>>m;
ll b[n];
read(b);
ll l=1,r=(ll)1e9;
ll k;
while(l<=r)
{
ll mid=(l+r)>>1;
if(checker(mid,b,n,m))
{
k=mid;
r=mid-1;
}
else
l=mid+1;
}
cout<<k<<endl;
}
int main()
{
// #ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #endif
fast
clock_t begin = clock();
int t=0;
cin>>t;
int c=1;
while(c<=t)
{
solve(),c++;
}
// #ifndef ONLINE_JUDGE
// clock_t end = clock();
// cout<<"\n\nExecuted in : "<<double(end-begin)/CLOCKS_PER_SEC*1000<<"ms\n";
// #endif
}