JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 1 2 ]    NEXT >
Good job. | Reply
Great article, i've found it very usefull, especially problem links at the end (to valladolid, etc.) It should be more of such links.
Re: Good job. (response to post by sin_13) | Reply
What's meta-binary search? By searching on Google I just found the expression on another romanian's website :).
Re: Good job. (response to post by Cosmin.ro) | Reply
A meta-binary search is some kind of binary search where powers of 2 are used. You can look on the source code in the article to figure out. I prefer this version of the binary search because it's easier to code in most of the cases.
Yes, romanian folks use to call this kind of search "meta-binary search".
Re: Good job. (response to post by danielp) | Reply
Ah, sounds like a name for radeye's version of binary search, for instance, part of this code.
Re: Good job. (response to post by Kawigi) | Reply
Yes, that's the idea. You cand find a shorter implementation in the article.
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 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
>> 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 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 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 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 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 LynValente) | Reply
Why stop at three? Base N binary search! O(1) running time!
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 sin_13) | Reply
Yes, It's great. Can you write about suffix tree or suffix array?
Internal Error

Your request could not be processed. Please inform TopCoder.