FORESTGA - Editorial

binary-search
easy
editorial
may16

#1

PROBLEM LINK:

Contest
Practice

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* + R* * 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*, &R*);
    }
    ll time = 0;
    while (!can_cut(time)) time++;
    printf("%lld

", 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* + R* * time may overflow. To fix this, you can replace the statement if (H* + R* * time >= L) with if (time >= (L - H*) / R*). 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 ext{ans})

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester


#2

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

sol link
https://www.codechef.com/viewsolution/10103183


#3

can test cases be disclosed? esp. #15


#4

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


#5

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


#6

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


#7

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.


#8

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.


#9

i did in nlogn ( the complexity of the sort function) and then a linear scan

https://www.codechef.com/viewsolution/10020689


#10

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 :slight_smile:


#11

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

Solution


#12

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


#13

i followed the same approach by reducing upper bound to min(w-h*/r*) and lower bound to min (l-h*/r*) and then applied above algo and my second subtask shows WA in some of the test cases of sub-task #2


#14

Also failed test 15 only (using approach described by user lohi above). Any info on what was unique about this test case?


#15

Can someone find the bug in my code. I used STLs and getting 2 testcases incorrect.
https://www.codechef.com/viewsolution/10074184


#16

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


#17

Anything special for subtask 2 task #9…!!
Getting WA…!! Don’t know why…??
Anyone…??

https://www.codechef.com/viewsolution/10063609


#18

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


#19

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


#20

Few test cases failing. Please can someone help me out.
https://www.codechef.com/viewsolution/10134958

Thanks in advance.