Page **1** of **1**

### 3294,3295 - problems

Posted: **Sat Oct 01, 2005 3:27 am**

by **ledins**

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?

### Re: 3294,3295 - problems

Posted: **Tue Oct 04, 2005 9:26 pm**

by **nnahas**

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?

I think 3295 has been solved there:

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)

Posted: **Thu Oct 13, 2005 8:09 am**

by **shanto86**

well can u plz a bit elaborate on that 3294? i mean panda-bamboo??

Mahbub

### try this

Posted: **Thu Oct 13, 2005 9:34 am**

by **shahriar_manzoor**

Posted: **Thu Oct 13, 2005 1:53 pm**

by **Cosmin.ro**

Cool the judge solution for H is the same as mine

Posted: **Thu Oct 13, 2005 7:19 pm**

by **shanto86**

i never thought there will be analysis of ICPC problems! thanks a lot sumit vi!

Posted: **Thu Oct 13, 2005 7:38 pm**

by **shanto86**

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

Posted: **Thu Oct 13, 2005 9:17 pm**

by **nnahas**

shanto86 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

I think he meant 2D range trees, augmented with Max information: see this link:

http://www.cs.aau.dk/~simas/aalg04/slides/aalg11.ppt

Posted: **Fri Oct 14, 2005 10:46 am**

by **shanto86**

hmm... till now i saw 4 different names of this data structure,

2D tree

2D interval tree

range tree

2D range tree

But thanks to u u gave me the right link