 # Chef and His Garden

please post the editorial of Chef and His Garden

if you want ,… i can explain it’s algorithm ?

the way is in my code…it’s rather easy to read!
https://www.codechef.com/viewsolution/11130064

The question looks difficult on the very first go,but it can be solved if you make some useful observations:
1.The number of time intervals for any particular test case be at most 2.This is because of the fact that the initial height and the growth rates of the first two trees predetermine the fate of the rest of the trees.
2.The answer for 1 tree is time from 0 to infinity.
3.If you have two time intervals like in this case: start1=x,end1=y & start2=y+1 and end2=z,then the answer you have two print is 1 time interval from x to z.
For instance lets consider the fact that initially the first tree is taller than the second tree,and its growth is rate is also more then the first tree will always remain taller than the second tree thus we have got our intial start and end time as 0 and infinity respectively.The rest of the trees will obviously narrow the time gap between 0 and infinity.What i mean to say is you will never get a case if you traverse through rest of the trees where start has to be deccreased and end needs to increased.Similarly you need to try out other possible combinations of the initial height and growth rates of the first two trees.
Here is my code for reference: https://www.codechef.com/viewsolution/11113718

2 Likes

This can be done just by considering both cases and then taking intersection.

3 Likes

the way is in my code… its easy for read!
https://www.codechef.com/viewsolution/11130064