JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (oldest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Re: Citations? (response to post by danielp) | Reply


It remains now to show how the in-block queries can be made. Note that the length of a block is l = [(log N) / 2], which is quite small. Also, note that A is a binary array. The total number of binary arrays of size l is 2^l=sqrt(N). So, for each binary block of size l we need to lock up in a table P the value for RMQ between every pair of indices. This can be trivially computed in O(sqrt(N)*l2)=O(N) time and space. To index table P, preprocess the type of each block in A and store it in array T[1, N/l]. The block type is a binary number obtained by replacing -1 with 0 and +1 with 1.


I don't quite get this. Can you please elaborate ?

say we have block like 1 2 3 4 3 4 3 2 1, the +/-1 array would be
1 1 1 1 -1 1 -1 -1 -1, how to calculate the value between 2 and 6.
ie 1 1 -1 1 -1 -1
Re: Citations? (response to post by Larry) | Reply
This article was based on my experience with RMQ and LCA during a long period of time. I tried to make this writing not too hard but quite complete. Here are some writings that inspired me. I strongly encourage you to take a look if you want to find more things:
- "Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE" by Johannes Fischer and Volker Heunn (link: http://www.bio.ifi.lmu.de/~fischer/fischer06theoretical.pdf)
- "The LCA Problem Revisited" by Michael A.Bender and Martin Farach-Colton (link: http://www.math.tau.ac.il/~haimk/seminar04/LCA-seminar-modified.ppt) - a very good presentation, ideal for quick learning of some LCA and RMQ aproaches
- "Faster algorithms for finding lowest common ancestors in directed acyclic graphs" by Artur Czumaj, Miroslav Kowaluk and Andrzej Lingas (link: http://www.cis.njit.edu/~czumaj/PUBLICATIONS/Czumaj-Kowaluk-Lingas-TCS-Summer-2005-r1-Aug-21-2006.pdf)
Re: Citations? (response to post by rrenaud) | Reply
This was actually one of my favorite algorithms but the paper that Cosmin.ro is talking about is available here:

http://www.cs.sunysb.edu/~bender/pub/lca.ps

So basically this tutorial is really an example from that (very short) paper.
Re: Citations? (response to post by Cosmin.ro) | Reply
Seeing this article on topcoder makes me proud to have had Farach-Colton as a professor.

(Waits idly to hear Larry make the same claim about Bender)
Re: Citations? (response to post by misof) | Reply
I think the paper that should be cited is M. A. Bender and M. Farach-Colton. "The LCA Problem Revisited."
Citations? | Reply
Some of the content looks pretty similar to some articles I read in the past, for example http://www14.informatik.tu-muenchen.de/konferenzen/Jass03/presentations/kiefer.pdf comes to mind. No offense intended, but IMHO in case when part of the TC article is taken from an existing source the TC article should contain proper citations. (In addition, the citations may be helpful if someone wants to pursue the topic deeper.)
RSS