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

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

please explain

please explain algorithm so that i can read code

ok
first explain my functoin
*** checkT() : check our sequence is zig zag or not
*** check() : check our sequence end or not
*** gogo() : number of day that must pass to reach zig zag(may several gogo need to get zig zag and must chech with function checkt() for it)
*** goback() : when is zig zag it get number of day need to coming out from zig zag(now we have first day and last dey of zig zag!)
*** in main(loop while(endd &&zz) for it we must get first day of zig zag(in first loop) then(second loop) must get day of coming out from zig zig(if substract 1 from it get last day of zig zag)