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