menarik sih menarik, tapi aku butuh waktu lammaaa utk mengertinya, sol
--- In jug-indonesia@yahoogroups.com, "Felix Halim" <[EMAIL PROTECTED]>
wrote:
>
> 2008/6/10 Andrian Kurniady <[EMAIL PROTECTED]>:
> > 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 [/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
>
