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 (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Good job. << PREV    [ 1 2 ]
 Re: Good job. (response to post by chungtq) | Reply Me and azotlichid have one about suffix arrays in the making, hopefully it will be ready next month.
 Re: Good job. (response to post by danielp) | Reply Thank you for the excellent tutorial . Amazing algorithm :) ! But I got confused at the end of the article, when you wrote:"... From now we will solve the RMQ problem for an array A[0, N - 1] where |A[i] - A[i + 1]| = 1, i = [1, N - 1]. We transform A in a binary array with N-1 elements, where A[i] = A[i] - A[i + 1]. It's obvious that elements in A can be just +1 or -1. Notice that the old value of A[i] is now the sum of A[1], A[2] .. A[i] plus the old A[0]. However, we won't need the old values from now on.To solve this restricted version of the problem we need to partition A into blocks of size l = [(log N) / 2]. Let A'[i] be the minimum value for the i-th block in A and B[i] be the position of this minimum value in A. Both A and B are N/l long. Now, we preprocess A' using the ST algorithm described in Section. ..."Then I read the another links in this discussion : http://www.cs.sunysb.edu/~bender/pub/lca.psFirst : create A' then, apply ST algorithm for A,A' - and then normalize A - then compute tables for every blocks. ( You normalized the array A at very first of the algorithm - Is that wrong or did I get something wrong ? )
 Re: Good job. (response to post by hungson175) | Reply You have to normalize the array first, as described in the article. After that, you may use the algorithm described at the end of the article.[LATER EDIT]Note that you don't actually normalize A, this is a forced expresion. You just use LCA queries for computing the RMQ queries on the original vector. For that LCA queries you use RMQ queries on a +-1 vector, and that's the vector you process. So, the way that's described in the article, it's necesarry to build the cartesian tree first, and compute the euler tour on it in order to have an RMQ algorithm.However, don't expect to code this algorithm in a topcoder contest;). It's just too long to code:)
 Re: Good job. (response to post by Cosmin.ro) | Reply Anyone knows what happened to this article? I find the topic very interesting!
 Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Good job. Previous Thread  |  Next Thread << PREV    [ 1 2 ]