JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (oldest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Citations?
 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 be1 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.psSo 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.)
 Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Citations? Previous Thread  |  Next Thread