Search found 30 matches
- Thu Feb 05, 2009 5:19 am
- Forum: Algorithms
- Topic: Query about interval search tree
- Replies: 6
- Views: 2205
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: 2205
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: 2205
Re: Query about interval search tree
I understand why you call the function with parameter [-infinity, +infinity].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].
Thank you for your help..
- Wed Feb 04, 2009 6:09 pm
- Forum: Algorithms
- Topic: Query about interval search tree
- Replies: 6
- Views: 2205
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: 2205
Query about interval search tree
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: 8129
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: 4407
11259 - Coin Changing Again
I tried DP but got TLE.
what could a better algorithm for this problem?
please help.
the complexity of my algorithm for each query is O( 4 * v + 4 * v ) .
what could a better algorithm for this problem?
please help.
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: 2257
- Sun Jul 22, 2007 4:09 am
- Forum: Volume 112 (11200-11299)
- Topic: 11227 - The silver bullet.
- Replies: 3
- Views: 2257
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: 19822
- Fri Jan 05, 2007 3:25 am
- Forum: Volume 111 (11100-11199)
- Topic: 11127 - Triple-Free Binary Strings
- Replies: 13
- Views: 4903
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: 4903
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
GOT AC

thank you
- Tue Jan 02, 2007 3:55 am
- Forum: Volume 111 (11100-11199)
- Topic: 11153 - Museums
- Replies: 16
- Views: 9168
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
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: 9168
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: 5435