3294,3295  problems
Moderator: Board moderators
3294,3295  problems
The ultimate bamboo eater is something strange  anyone has an idea? All my ideas run out of time.
the triangle counting is kind of easy, but what do you do with finding the lines with more than 2 points one them? I mean, how?
the triangle counting is kind of easy, but what do you do with finding the lines with more than 2 points one them? I mean, how?
Re: 3294,3295  problems
I think 3295 has been solved there:ledins wrote:The ultimate bamboo eater is something strange  anyone has an idea? All my ideas run out of time.
the triangle counting is kind of easy, but what do you do with finding the lines with more than 2 points one them? I mean, how?
http://forums.topcoder.com/?module=Thre ... 81&start=0
I think that 3294 is not easy. I think I have a O(n (lg (n))^3) divide and conquer algorithm that uses range trees and that recursively bisects the point set according to bamboo "deliciousness", and intuitively I think that in practice my algo would run in O(n (lg (n))^2)

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
I think he meant 2D range trees, augmented with Max information: see this link: http://www.cs.aau.dk/~simas/aalg04/slides/aalg11.pptshanto86 wrote: i heard about Red black tree, i also heard about interval tree. but what is 2D interval tree?? can any one tell me or give a link to any site where i can find it.
i gave a search at google but no satisfactory result