×

# FORESTGA - Editorial

Author: Maksym Bevza
Tester: Kevin Atienza
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

Easy

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:

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

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

# AUTHOR'S AND TESTER'S SOLUTIONS:

This question is marked "community wiki".

1.7k586142
accept rate: 11%

 2 I used PRIORITY QUEUE which stores the time taken by tree to reach minimum length, initial height of tree and rate of growth. The tree with minimum time will be on top of the priority queue and it will always be included. In this way we can calculate the minimum time to reach the required length with complexity O(NlogN). It will be more clear to you after seeing my solution. See my solution here... https://www.codechef.com/viewsolution/10016046 answered 20 May '16, 07:59 79●5 accept rate: 20%
 1 We can avoid the arithmetic overflow problem in C/C++ also. Here's the trick. If overflow happens ( value > 10^18 ) , then variable takes some negative value. Since we are given that maximum value of woods required is 10^18 , this means we have got total Woods >= woods required. Few optimization steps can be: 1 - In every month, the height of tree increases by atleast 1(one) . So if "months" > woods required , then for this month , total Woods >= woods required 2 - If for one tree , initial height of tree >= wood required , then total Woods >= woods required 3 - If for one tree , increased height >= wood required , then total Woods >= woods required answered 17 May '16, 11:51 838●3●5●15 accept rate: 20%
 0 My sol is this can somebody will find the bug in it because iam getting error in thr 10th test case only and if print the min_mon-1 then only 10th case passes and all other showing the WA. Thank in advance answered 16 May '16, 15:13 1 accept rate: 0%
 0 can test cases be disclosed? esp. #15 answered 16 May '16, 16:23 1 accept rate: 0%
 0 For avoiding overflow bugs in C++, one can also use double or long double. Solution 1. Also, a solution with better complexity O(n logn) exists for this question as one of my college-mate wrote. He used min-heaps for the solution, where heap was build on the (h, r, l) values where h = initial height, r = growth rate, l = number of days after which the trees grows to required minimum length l as specified in question Here is a link to his solution in C. Solution 2 answered 16 May '16, 16:29 6★likecs 3.7k●23●80 accept rate: 9% Can you please explain a little bit, how solution using min heap is working ? (17 May '16, 20:40)
 0 Can someone help me, i a unable to find whats wrong in my code.Thanks in Advance. sol. link. https://www.codechef.com/viewsolution/10101257 answered 16 May '16, 17:36 4★skag 16●2 accept rate: 33%
 0 In the worst cases there are chances of overflow in C++. Also if binary search is applied it might give lower bound of answer. Here is AC python sol. for applying navies binary search for this problem. https://www.codechef.com/viewsolution/10036267 answered 16 May '16, 18:00 4★atulag 106●2 accept rate: 12%
 0 I got AC even when I used 10^18 as my upper bound for binary_search and I also used python to avoid integer overflow. answered 16 May '16, 18:31 281●6 accept rate: 11% The maximum answer is 10^18-1, so 10^18 (or even 10^18-1) is good as an upper bound. (17 May '16, 22:47)
 0 Another O(nlogn) solution, which is without using Binary Search. I calculated the time for each tree to grow enough. Let those be t1 , t2 , t3,..., tn. I sorted it. -> O(nlogn). Then, at each of these times(t1 , t2 , t3,..., tn), I calculated the wood I will have and compared it with wood required. If wood I have at time t(x) is more than wood required, then the answer lies between t(x-1) and t(x), and hence that can be found in O(1). Also, calculating the total wood that I will have at time t(x) can be calculated in O(1). Please look at my solution for more understanding. Solution. answered 16 May '16, 18:32 4★lohit_97 342●8 accept rate: 4%
 0 i did in nlogn ( the complexity of the sort function) and then a linear scan https://www.codechef.com/viewsolution/10020689 answered 16 May '16, 21:09 469●5●29 accept rate: 7%
 0 Yes, I too used binary search and was getting wrong answer until I changed the upper bound to 10^18. In C and C++ need to cutoff the moving sum as soon as we get a value >= W. This will prevent integer overflow. Nice problem. Had fun coding it :) answered 16 May '16, 21:36 1 accept rate: 0%
 0 Hello My solution has passed fro the large inputs,but for small inputs only one is failing please help me to find the case Regards Samuel answered 17 May '16, 17:03 24●1●2●7 accept rate: 0%
 0 i followed the same approach by reducing upper bound to min(w-h[i]/r[i]) and lower bound to min (l-h[i]/r[i]) and then applied above algo and my second subtask shows WA in some of the test cases of sub-task #2 answered 17 May '16, 19:15 2★demo01 70●1●2 accept rate: 12%
 0 Also failed test 15 only (using approach described by user lohi above). Any info on what was unique about this test case? answered 17 May '16, 19:16 1●2 accept rate: 0%
 0 Can someone find the bug in my code. I used STLs and getting 2 testcases incorrect. https://www.codechef.com/viewsolution/10074184 answered 18 May '16, 01:25 41●1 accept rate: 0%
 0 For those who used C++ and their solution failed Test Case #15, use long double. I too was stuck on the same test case because I thought double and long double are same, but long double worked. Here's the solution: https://www.codechef.com/viewsolution/10086777 answered 18 May '16, 21:25 6●3 accept rate: 0%
 0 Anything special for subtask 2 task #9..!! Getting WA..!! Don't know why..?? Anyone..?? https://www.codechef.com/viewsolution/10063609 answered 19 May '16, 12:39 2★shoban05 8●1●2 accept rate: 0%
 0 @tao_of_coding If the user whose approach you followed is me, then, subtask 15 might not be working cause it maybe going out of bounds, if you are ceil() function. For answers > 10^9, it will not give correct answer. All the best! Use long double instead, of ceil function and make your own ceil function. link This answer is marked "community wiki". answered 19 May '16, 14:21 4★lohit_97 342●8 accept rate: 4%
 0 Few test cases failing. Please can someone help me out. https://www.codechef.com/viewsolution/10134958 Thanks in advance. answered 20 May '16, 22:20 21●1 accept rate: 0%
 0 https://www.codechef.com/viewsolution/12100042 My solution is giving TLE even though the complexity is O(n log n) answered 14 Nov '16, 14:12 76●3 accept rate: 16%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,683
×3,766
×1,038
×141

question asked: 16 May '16, 01:08

question was seen: 8,496 times

last updated: 09 Nov '17, 00:35