3294,3295 - problems

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

Post Reply
ledins
New poster
Posts: 2
Joined: Sat Oct 01, 2005 3:23 am

3294,3295 - problems

Post by ledins » Sat Oct 01, 2005 3:27 am

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?

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

Re: 3294,3295 - problems

Post by nnahas » Tue Oct 04, 2005 9:26 pm

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)

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Thu Oct 13, 2005 8:09 am

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

Mahbub
Self judging is the best judging!

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

try this

Post by shahriar_manzoor » Thu Oct 13, 2005 9:34 am


Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro » Thu Oct 13, 2005 1:53 pm

Cool the judge solution for H is the same as mine :)

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Thu Oct 13, 2005 7:19 pm

i never thought there will be analysis of ICPC problems! thanks a lot sumit vi!
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Thu Oct 13, 2005 7:38 pm

:( 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 :cry:
Self judging is the best judging!

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

Post by nnahas » Thu Oct 13, 2005 9:17 pm

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 :cry:
I think he meant 2D range trees, augmented with Max information: see this link: http://www.cs.aau.dk/~simas/aalg04/slides/aalg11.ppt

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Fri Oct 14, 2005 10:46 am

hmm... till now i saw 4 different names of this data structure,
2D tree
2D interval tree
range tree
2D range tree

:lol:

But thanks to u u gave me the right link :wink:
Self judging is the best judging!

Post Reply

Return to “ACM ICPC Archive Board”