Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (oldest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 1 2 ]    NEXT >
Re: Good job. (response to post by | Reply
Anyone knows what happened to this article? I find the topic very interesting!
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.
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 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 :
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 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 sin_13) | Reply
Yes, It's great. Can you write about suffix tree or suffix array?
Re: Good job. (response to post by cep21) | Reply
Well yes but then you have that nasty coefficient of N. 2log3(N) didn't look so bad. Well except I suppose 2log3(N) = 2log2(N)/log2(3), and log2(3) < 2. Darn. I just have this vague memory of a problem where I used something other than a binary search.

Oh actually I guess it was a binary tree type thing or something. But I found the code and the branching factor was set to

int num = (int)(43.66827238/log(lbl));

Which makes me scratch my head a bit and wonder what equation I solved to get that number.
Re: Good job. (response to post by LynValente) | Reply
Why stop at three? Base N binary search! O(1) running time!
Re: Good job. (response to post by LynValente) | Reply
Whether it's easier to code or not, I've thought a bit about problems that require binary-search-like algorithms, and come to the realization that in order to do an K-ary search for the same effect as a binary search, you need to do (K-1)*logKN comparisons, and using 2 for K really is optimal when this is the case :-) Alternatively, you could have another base X where you do an X-ary search among the K choices, but I still think a flat binary search would involve fewer comparisons :-)
Re: Good job. (response to post by danielp) | Reply
I also found the article very interesting. I had heard a bit about these two problems but never learned about them in detail before now.

Also, on the binary search topic, it seems that base 3 might be faster than base 2 for doing logarithmic-style searches. Am I just crazy or do people stick to base 2 because it is easier to code?
Re: Good job. (response to post by radeye) | Reply
Of course he is not the first using that, the idea is not hard at all. He was just the first who used this idea in Romanian programing contests. Look what Kawigi said: "Ah, sounds like a name for radeye's version of binary search". That's because he first saw this kind of binary search at you. We use to say that this was "Mihai's version of binary search" because we first saw it at him. He gived that name too, and that's why we use it.
However, i don't think that we really need to use a special name for this. It's just a binary search after all.
Re: Good job. (response to post by radeye) | Reply
I think daniel meant that Mihai used it in his code for romanian programming contests and that a lot of romanian high schoolers learned that trick from his code.

Another strange thing is that romanians use the term Lee's algorithm for breadth first search, because of one book published in 95 aimed at programming contests which described bfs as Lee's algorithm. We didn't have CLR back then, it was just published in 2000, and we had poor internet coverage, so that was one of the very few books that dealt with algorithmics.

This is one reason I hate when science is explained in movies, cause it's most of the time very wrong, and a lot of people think it's correct.
Re: Good job. (response to post by danielp) | Reply
>> Mihai Patrascu is the one who used this kind of binary search for the first time

Heh, really? I've been doing it since before he was a gleam in his father's eye. And the idea is obvious enough that I'm sure we can find references back to the 50's and before.
Re: Good job. (response to post by Krzysan) | Reply
Mihai Patrascu is the one who used this kind of binary search for the first time (as we know). In the solutions of the problems he proposed for some Romanian olympiads he used to call this kind of search "meta-binary search". We just got the name and the idea:)
Re: Good job. (response to post by danielp) | Reply
That's a terrible name for this idea. There's nothing "meta" about it.
Re: Good job. (response to post by Kawigi) | Reply
Yes, that's the idea. You cand find a shorter implementation in the article.
[ 1 2 ]    NEXT >