UVa OJ Board

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.

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...

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].

Thank you for your help..

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...

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...

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...

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 ) .

i found the bug..please ignore my previous post.
thank you

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...

yes they are correct

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...

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

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

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...

How to solve this problem ? any hints will be appreciated
bye