PROBLEM LINK: Chintu Ki Press

Fractal Code Fiesta




Binary search , Maths


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.


We can find answer by doing binary search over all the possible answers i.e over the space T \in [1 , 10^{18} ].


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


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;
		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);
			l = mid + 1;
	cout << ans << endl;

	return 0;