You are not logged in. Please login at www.codechef.com to post your questions!

×

FORESTGA - Editorial

2
2

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

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter
Tester

This question is marked "community wiki".

asked 16 May '16, 01:08

kevinsogo's gravatar image

7★kevinsogo
1.7k472135
accept rate: 11%

edited 17 May '16, 22:47


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

link

answered 20 May '16, 07:59

nishant_coder's gravatar image

5★nishant_coder
765
accept rate: 20%

edited 20 May '16, 08:07

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

link

answered 17 May '16, 11:51

shivam217's gravatar image

4★shivam217
8123515
accept rate: 18%

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

link

answered 16 May '16, 15:13

hitesh_saini1's gravatar image

3★hitesh_saini1
1
accept rate: 0%

can test cases be disclosed? esp. #15

link

answered 16 May '16, 16:23

palash1010's gravatar image

2★palash1010
1
accept rate: 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

link

answered 16 May '16, 16:29

likecs's gravatar image

6★likecs
3.1k636
accept rate: 9%

Can you please explain a little bit, how solution using min heap is working ?

(17 May '16, 20:40) shivam2174★

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

link

answered 16 May '16, 17:36

skag's gravatar image

4★skag
162
accept rate: 33%

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

link

answered 16 May '16, 18:00

atulag's gravatar image

4★atulag
661
accept rate: 14%

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.

link

answered 16 May '16, 18:31

mightymercado's gravatar image

4★mightymercado
2826
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) kevinsogo7★

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.

link

answered 16 May '16, 18:32

lohit_97's gravatar image

4★lohit_97
3108
accept rate: 2%

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

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

link

answered 16 May '16, 21:09

anupam_datta's gravatar image

4★anupam_datta
368521
accept rate: 7%

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

link

answered 16 May '16, 21:36

sidgairo18's gravatar image

3★sidgairo18
1
accept rate: 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

link

answered 17 May '16, 17:03

jawa2code's gravatar image

3★jawa2code
24127
accept rate: 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

link

answered 17 May '16, 19:15

demo01's gravatar image

2★demo01
702
accept rate: 12%

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

link

answered 17 May '16, 19:16

tao_of_coding's gravatar image

3★tao_of_coding
12
accept rate: 0%

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

link

answered 18 May '16, 01:25

typeof_yash's gravatar image

2★typeof_yash
411
accept rate: 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

link

answered 18 May '16, 21:25

varuns_2729's gravatar image

4★varuns_2729
62
accept rate: 0%

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

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

link

answered 19 May '16, 12:39

shoban05's gravatar image

2★shoban05
812
accept rate: 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

lohit_97's gravatar image

4★lohit_97
3108
accept rate: 2%

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

Thanks in advance.

link

answered 20 May '16, 22:20

aayush_10zn's gravatar image

1★aayush_10zn
211
accept rate: 0%

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

My solution is giving TLE even though the complexity is O(n log n)

link

answered 14 Nov '16, 14:12

samarjeet27's gravatar image

3★samarjeet27
361
accept rate: 16%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×11,590
×2,610
×594
×139

question asked: 16 May '16, 01:08

question was seen: 6,224 times

last updated: 14 Nov '16, 14:12