FORESTGA - Editorial

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

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

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:

2 Likes

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

3 Likes

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

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

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

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

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: CodeChef: Practical coding for everyone

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

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

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

1 Like

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

1 Like

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

Thanks in advance.

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

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

I am getting wrong answer for only few test cases can someone please help
https://www.codechef.com/viewsolution/16177188

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

The maximum answer is 10^18-1, so 10^18 (or even 10^18-1) is good as an upper bound.

I got TLE many times using binary Search too… it got removed when I declared arrays globally instead of declaring locally and passing them again and again…

Thank you for the solution! This taught me a lot.

Thanks your tips works to handle overflows…

Easy C++ Code
https://www.codechef.com/viewsolution/71836988