PROBLEM LINK: Chintu Ki Press
DIFFICULTY:
Medium
PREREQUISITES:
Binary search , Maths
PROBLEM:
You are given M printers and time taken by each printer to print one page is also given. You have to find minimum time required to print total P pages, given more than one printer can work simultaneously.
QUICK EXPLANATION:
We can find answer by doing binary search over all the possible answers i.e over the space T \in [1 , 10^{18} ].
EXPLANATION:
Firstly, since more than one printer can work simultaneously therefore working on all M printers simultaneously will always be optimal.
Using the constraints we can find the range of answer T .
Minimum time to print P pages can be T = 1s and maximum time can be T = 10^{18}s (each printer can take maximum 10^9s to print one page and maximum number of pages to be print i.e. P can also be 10^9 so T \leq 10^{18}s ) .
Now, Take l = 1 and r = 10^{18} and perform binary search on the space [l , r] .
Take T = mid be your answer and calculate total number of pages all M printers can print in time T i.e. sum = \displaystyle\sum_{i = 0}^{m-1} \left\lfloor\frac{T}{t_i}\right\rfloor .
if sum \geq P, it means time T is sufficient to print P pages and it can be minimized if possible hence our search space becomes [l , mid - 1] .
On the other hand if sum < P, it means time T is insufficient to print P pages and that’s why we will search in upper half i.e. [mid + 1 , r] .
Repeating above steps until l \leq r, we will get the minimum time T recquired to print P pages.
Time-Complexity: O(M*log S) , where S = 10^{18}.
SOLUTIONS:
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll m, p;
ll a[200005];
bool check(ll time)
{
ll i, s = 0;
for (i = 0; i < m; i++)
{
s += (time / a[i]);
if (s >= p)
return true;
}
if (s >= p)
return true;
else
return false;
}
int main()
{
ll i, j, k, ans = 1e18 + 1;
cin >> m >> p;
for (i = 0; i < m; i++)
cin >> a[i];
ll l = 1, r = 1e18;
while (l <= r)
{
ll mid = (l + r) / 2;
if (check(mid))
{
r = mid - 1;
ans = min(ans, mid);
}
else
l = mid + 1;
}
cout << ans << endl;
return 0;
}