PROBLEM LINK:
Author: Maksym Bevza
Tester: Kevin Atienza
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Easy
PREREQUISITES:
Binary search
PROBLEM:
There are N trees. The initial height of the i th tree is H_i meters, and the height increases R_i meters per month.
A tree with height lower than L cannot be cut. What is the fewest number of months before the Chef can cut W meters of height of wood?
QUICK EXPLANATION:
Binary search the answer.
However, in some languages, you need to take care of some overflow issues. These will be addressed below.
EXPLANATION:
The most straightforward solution for this that I can think of is to just loop through the number of months, say t, and then check if there is enough wood after this number of months. Checking is simple: For each tree, we know that after t months its height is H_i + R_it, so if this height is \ge L, then we can add this height to the total amount of height of wood we can cut. Then we just compare the total wood we have with W.
The following C++ code illustrates this:
#include <stdio.h>
#define N 100111
#define ll long long
int n;
ll H[N];
ll R[N];
ll W, L;
bool can_cut(ll time) {
ll total_cut = 0;
for (int i = 0; i < n; i++) {
ll height = H[i] + R[i] * time;
if (height >= L) total_cut += height;
}
return total_cut >= W;
}
int main() {
scanf("%d%lld%lld", &n, &W, &L);
for (int i = 0; i < n; i++) {
scanf("%lld%lld", &H[i], &R[i]);
}
ll time = 0;
while (!can_cut(time)) time++;
printf("%lld\n", time);
}
Unfortunately, this doesn’t work for the second subtask because the answer can be very large. Indeed, it can reach up to 10^{18}-1, and there’s not enough time to even loop up to 10^{12}!
We need to find an insight that will improve our solution. Here’s the key insight: If there’s enough wood at time t, then there’s enough wood at time t+1, and indeed for every t' such that t' > t. In other words, the amount of wood only increases with time.
This simple fact actually allows us to use binary search to find the answer! Because suppose we know that the answer lies in the range [t_L,t_R]. Let t_M be a time somewhere within [t_L,t_R]. Then:
- If there’s enough wood at time t_M, then the answer is in [t_L,t_M].
- If there isn’t enough wood at time t_M, then the answer is in [t_M+1,t_R].
Thus, if we choose t_M to be roughly in the middle of the range [t_L,t_R], then checking once on t_M will reduce the range’s size by roughly half. Thus, if A is the size of the range where the solution can be, then there will just be O(\log A) checks before the range becomes of size 1, at which point we already know the answer!
The following pseudocode shows how to do it.
t_L = -1
t_R = 10^18
while t_R - t_L > 1:
t_M = (t_L + t_R) / 2
if can_cut(t_M):
t_R = t_M
else:
t_L = t_M
print t_R
Note that t_L and t_R in this binary search is slightly different; the range containing the solution is not [t_L,t_R], rather it is (t_L,t_R] (or \{t_L+1,t_L+2,\ldots,t_R-1,t_R\}), and the solution maintains the invariant that can_cut(t_L) == false and can_cut(t_R) == true.
Since can_cut runs in O(N) time, and \log_2 10^{18} \le 64 so can_cut is only called a few times, this solution runs fast enough for the time limit!
Pitfalls
While mathematically correct, the solution above suffers from some pitfalls. One common mistake might be setting the bounds, especially the lower bound. Notice that in the pseudocode above I set t_L = -1. This is because a solution of 0 is possible! This is when the amount of wood is enough to begin with, so we don’t even need to wait.
The next possible source of error is arithmetic overflow. Notice that we’re dealing with large integers here; large enough to potentially overflow 64-bit integers. (In some languages such as Python, this doesn’t occur.) There are a few places where overflow may occur:
- If
timeis large enough, thenH[i] + R[i] * timemay overflow. To fix this, you can replace the statementif (H[i] + R[i] * time >= L)withif (time >= (L - H[i]) / R[i]). Notice that there’s no multiplication. -
total_cutmay overflow. To fix this, returntrueas soon astotal_cutexceedsW. This is to avoid further increases intotal_cutwhich may trigger overflow.
An additional technique to further defend against overflow is to dynamically find the upper bound by doubling. In other words, we add an initial step where we try to find a suitably small upper bound, but using just a few steps. Here’s a pseudocode:
t_L = -1
// compute t_R by doubling
t_R = 1
while !can_cut(t_R):
t_R *= 2
// now, binary search
while t_R - t_L > 1:
t_M = (t_L + t_R) / 2
if can_cut(t_M):
t_R = t_M
else:
t_L = t_M
print t_R
Using this, we can be sure that t_R is at most twice the solution, so our upper bound isn’t that far off.
Time Complexity:
O(N \log \text{ans})
