Sekedar info.., dari hasil googling... :)
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
Felix Halim wrote:
2008/6/10 Andrian Kurniady <[EMAIL PROTECTED]
<mailto:andrian%40kurniady.net>>:
> Pake RMQ yang O(log N) bisa dapet segini :
>
> Preprocess Time: 0.372
> 1000000 Queries Time: 0.372
> TOTAL Time: 0.744
Inilah sang jawara :D
He eh, kalo pake bottom-up + plain-array DP bisa lebih kenceng
daripada pake rekursi + tree structure.
> Pake RMQ yang O(1) dapet nya segituan juga.
> [Spoiler] http://andrian.kurniady.net/Minimum.java
<http://andrian.kurniady.net/Minimum.java> [/Spoiler]
> Bener gak? :-D
Congats!!! Sodara2, perkenalkan Andrian Kurniady, master DP + calon
juara INC 2008 :D
Sepertinya pertanyaan saya sudah setop sampai disini, karena udah gak
ada yang lebih kenceng dari O( 1 ) query time :P
Yang versi O(log N) nya bisa dibuat tergantung "lebar" sehingga kalau
j-i+1 nya kecil, versi O( log N ) nya bisa finish hanya dalam beberapa
steps, sehingga tidak jauh beda dengan versi O( 1 ) nya. However
versi O( 1 ) nya guaranteed hanya butuh 1 step untuk "lebar" apapun.
Soal gini2an cocoknya jadi "interview" questions nich. Karena di
kuliah biasanya cuman diajarin dasar dari tree data structure dan itu
tergantung kreativitas programmer untuk menggunakannya secara
efficient. Untuk yang RMQ versi O( 1 ) nya biasanya terlalu susah
untuk orang awam, karena butuh pengetahuan tentang Dynamic Programming
yang kuat. Tapi kelihatannya bukan masalah bagi seorang Andrian
Kurniady :P
Menarik kan? Mau soal lagi? :D
Felix Halim
__
