Search found 30 matches

Thu Feb 05, 2009 5:19 am
Forum: Algorithms
Topic: Query about interval search tree
Replies: 6
Views: 2232

Re: Query about interval search tree

Thank you mf for having the patience to read the post and replying to all the questions of mine. I would think this is the most useful post I have seen for a while. Thank you once again.
Wed Feb 04, 2009 8:58 pm
Forum: Algorithms
Topic: Query about interval search tree
Replies: 6
Views: 2232

Re: Query about interval search tree

Now I have a new type of query. Given n intervals and a query point (1 dimensional), return the interval whose high end is less than the query point and the low end is maximum. Given intervals [1,3] [5,6] [4,7] [12,14] [13,14] [17,19] and the query point is 8 the answer is [5,6] as 6 < 8 and 5 is th...
Wed Feb 04, 2009 7:33 pm
Forum: Algorithms
Topic: Query about interval search tree
Replies: 6
Views: 2232

Re: Query about interval search tree

I understand most of the part but I want to know why do you call the function recurse with range [-infinity, infinity]. Should not I call recurse with [a, b].
I understand why you call the function with parameter [-infinity, +infinity].

Wed Feb 04, 2009 6:09 pm
Forum: Algorithms
Topic: Query about interval search tree
Replies: 6
Views: 2232

Re: Query about interval search tree

Thank you mf for your reply. I understand most of the part but I want to know why do you call the function recurse with range [-infinity, infinity]. Should not I call recurse with [a, b]. Is there any way to use STL and make life easier. What about if I change the query something like this " Given n...
Wed Feb 04, 2009 9:54 am
Forum: Algorithms
Topic: Query about interval search tree
Replies: 6
Views: 2232

Hello everybody, I am a PhD Student in Computer Science. In my research, I have stumbled upon a query about interval search tree. I would be glad if any one can reply to my query. Given n intervals and another query interval i, is there any interval in the given n intervals that is fully contained i...
Mon Dec 10, 2007 6:15 pm
Forum: ACM ICPC Archive Board
Topic: Lazy Jumping Frog - 3652 (Live Archive)
Replies: 8
Views: 8348

I am getting TLE in 929

I am getting TLE in 929. I used dijkstra for it. I check that every node once popped from the queue is not inserted again. Moreover I also break the loop when destination is popped. any other optimization needed ? Is it possible to solve this problem with Dijkstra only. I saw in the board some other...
Sat Aug 04, 2007 4:09 pm
Forum: Volume 112 (11200-11299)
Topic: 11259 - Coin Changing Again
Replies: 12
Views: 4484

11259 - Coin Changing Again

I tried DP but got TLE.
what could a better algorithm for this problem?
the complexity of my algorithm for each query is O( 4 * v + 4 * v ) .
Sun Jul 22, 2007 4:25 am
Forum: Volume 112 (11200-11299)
Topic: 11227 - The silver bullet.
Replies: 3
Views: 2284
i found the bug..please ignore my previous post.
thank you
Sun Jul 22, 2007 4:09 am
Forum: Volume 112 (11200-11299)
Topic: 11227 - The silver bullet.
Replies: 3
Views: 2284

11227 - The silver bullet.

I am getting WA in this problem. I am using O( n^2 logn ) algorithm for solving this problem. I use STL set to take care of the multiple instance of a set. Can anyone give me some tricky input output ? I use EPSILON = 1e-7 to check the equality of two doubles. Please help me in this. If any one want...
Thu Jan 11, 2007 7:12 pm
Forum: Volume 111 (11100-11199)
Topic: 11149 - Power of Matrix
Replies: 42
Views: 19995
yes they are correct
Fri Jan 05, 2007 3:25 am
Forum: Volume 111 (11100-11199)
Topic: 11127 - Triple-Free Binary Strings
Replies: 13
Views: 4949

about tle in 11127 triple binary string

Jan wrote: You are checking the validity after calculating a full sequence. this is not right. i did check for validity after putting every character. my problem was that i didn't check the validity efficiently. my code for checking the validity was naive, now i changed it and got ac in around 3 se...
Thu Jan 04, 2007 1:39 am
Forum: Volume 111 (11100-11199)
Topic: 11127 - Triple-Free Binary Strings
Replies: 13
Views: 4949

getting TLE

im getting TLE in this problem. any possible optimization u want me to consider. i used backtracking. here is the code:

GOT AC CODE DELETED

thank you
Tue Jan 02, 2007 3:55 am
Forum: Volume 111 (11100-11199)
Topic: 11153 - Museums
Replies: 16
Views: 9286

thank you

hey thank you observer and mf.
just after posting in the board i came to understand what wf was trying to say. i got it accepted less than 1 sec. i wasnt understanding how you decreased your states. now i understand
thank you once again for letting me know about the idea:)
Bye
Tue Jan 02, 2007 2:38 am
Forum: Volume 111 (11100-11199)
Topic: 11153 - Museums
Replies: 16
Views: 9286
mf wrote : Actually, just a bitmask of visited museums and current location can be enough. This would be just about 54000 states. You can use this DP to find minimum time required to visit a subset of museums, and then iterate over all subsets to check their feasibility and pick the one with maximu...
Sun Dec 03, 2006 3:21 am
Forum: Volume 9 (900-999)
Topic: 960 - Gaussian Primes
Replies: 12
Views: 5460
How to solve this problem ? any hints will be appreciated
bye