JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
<< 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.ps
First : 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 <O(n), O(1)> 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!
<< PREV    [ 1 2 ]

RSS