### 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
`time`

is large enough, then`H[i] + R[i] * time`

may overflow. To fix this, you can replace the statement`if (H[i] + R[i] * time >= L)`

with`if (time >= (L - H[i]) / R[i])`

. Notice that thereâ€™s no multiplication. -
`total_cut`

may overflow. To fix this, return`true`

as soon as`total_cut`

exceeds`W`

. This is to avoid further increases in`total_cut`

which 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})