PROBLEM LINK:Author: Maksym Bevza 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:
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:
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.
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_R1,t_R\}$), and the solution maintains the invariant that Since PitfallsWhile 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 The next possible source of error is arithmetic overflow. Notice that we're dealing with large integers here; large enough to potentially overflow 64bit integers. (In some languages such as Python, this doesn't occur.) There are a few places where overflow may occur:
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:
Using this, we can be sure that Time Complexity:$O(N \log \text{ans})$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 16 May '16, 01:08

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

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

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_mon1 then only 10th case passes and all other showing the WA. Thank in advance answered 16 May '16, 15:13

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 collegemate wrote. He used minheaps 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

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

In the worst cases there are chances of overflow in C++. answered 16 May '16, 18:00

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(x1) 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

i did in nlogn ( the complexity of the sort function) and then a linear scan answered 16 May '16, 21:09

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

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

i followed the same approach by reducing upper bound to min(wh[i]/r[i]) and lower bound to min (lh[i]/r[i]) and then applied above algo and my second subtask shows WA in some of the test cases of subtask #2 answered 17 May '16, 19:15

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

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

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

Anything special for subtask 2 task #9..!! Getting WA..!! Don't know why..?? Anyone..?? answered 19 May '16, 12:39

@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

Few test cases failing. Please can someone help me out. Thanks in advance. answered 20 May '16, 22:20

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
