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?
3294,3295 - problems
Moderator: Board moderators
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 2-D 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