eh maaf nih... cuma agak penasaran.. henry luk kenal gue kah? gue punya temen kantor dulu namanya henry luk juga.. sorry banget nih OOT... and back to the case.. vk_leon anak kaskus khan yah :p hehehehe kalo ide lu preprocess nya bikin BST wah itu terlalu lama.. emang ntar mau serach nya jadi cepet banget.. tapi emang apa guna nya di bikin search tree.. gue ada idea lebih bagus :p preprocess nya 1 langkah doang.. yaitu mengalikan semua angka nya.. lalu output array nya tinggal angka hasil preprocess di bagi dengan input[i] sendiri.. yang perlu kita cari justru cara bagi nya.. karna gak bole pake operator 'division' itu sendiri.. jadi kita bikin sendiri nah sekarang pertanyaan nya.. ada yang bisa bantuin gue discover method pembagian tanpa operasi pembagian?
2008/6/8 viking leon <[EMAIL PROTECTED]>: > sory double posting keteken send waktu gambar2 BStnya > > preprocess bikin: > - binary search tree (left selalu lebih kecil dari parent, kanan selalu > lebih gede dari parent) > tapi yang disimpan dalam binary tree adalah indexnya bkan valuenya > > untuk array ini: [2,4,1,3] > BST value-nya: > 2 > / \ > 1 4 > / > 3 > BST indexnya: > 0 > / \ > 2 1 > / > 3 > tuk bikin BST dari array yang sudah ada kira2: O(n) > > > > searchnya pake algo kira2 begini: > - search on left, > kalo belum ktemu search on right > kalo udah ktemu terus search on left (cari terus ke node left paling dalam > yang bisa ditemukan note: node right engga usah disearch) > > jadi tuk search: > queryMin( 0, 3 ) = > - ktemu 0, keep on searching left > - ktemu 2 keep on searching left which is null > so hasilnya = 2 > > queryMin( 1, 1 ) = > - 0, belum ktemu cari kiri > - 2 belum ktemu kiri, kanan ga ada > - recursif back to 0, kanannya 1 > - 1 ktemu, cari kiri null > hasil = 1 > > queryMin( 1, 2 ) = 1 > - 0 belum ktemu, cari kiri > - 2 ktemu cari kiri, null > hasil=2 > > queryMin( 0, 1 ) = 2 > - 0 ktemu, keep kiri > - kiri = 2, tidak ada di index balek ke parent > hasil = 0 > > queryMin( 3, 3 ) = > - 0 belum ktemu cari kiri > - kiri =2 tidak ada di index balek parent search kanan > - 1 belum ktemu cari kiri = null > - cari kanan, ktemu =3, keep kiri = null > - hasil = 3 > > searchnya kira2 = O(log n) > > regards, > yohan > > > > --- On Sat, 6/7/08, Felix Halim <[EMAIL PROTECTED]> wrote: > > From: Felix Halim <[EMAIL PROTECTED]> > Subject: Re: [JUG-Indonesia] Kode menarik > To: jug-indonesia@yahoogroups.com > Date: Saturday, June 7, 2008, 1:45 PM > > 2008/6/7 Hendry <[EMAIL PROTECTED] com>: >> soal ini kamu yang bikin? atau penjelasan berikut ini based on your >> assumption? >> kalau kamu yang bikin, i got no further questions, tapi kalau hanya >> based on assumption, seperti nya arti dan maksud dari soal dan >> penjelasan yang diberikan berikut sudah berbeda. > > Soal ini adalah soal classic (sudah ada dari jaman dahulu), jadi bukan > saya yang bikin. > Yang research solusinya juga banyak (banyak scientific paper ttg problem > ini). > > Hmm... saya tulis ulang deh problemnya, sepertinya kurang jelas: > > Diberikan array of integer A yang isinya adalah bilangan integer acak > sebanyak N elements. > Saya ingin query bilangan integer terkecil dari array A yang index nya > antara i dan j (inclusive). > Index dari array adalah 0-based (index dimulai dari angka 0). > > Untuk memprocess tiap query, harus tidak lebih dari O ( log N ) steps. > Tapi query ini bisa banyak kali (querynya bukan cuman satu kali). > Dan anda diperbolehkan untuk preprocess array A terlebih dahulu tapi > tidak lebih dari O ( N log N ) steps. > > Semoga tidak ada keambiguan lagi. > > 2008/6/7 viking leon <[EMAIL PROTECTED] com>: >> preprocessnya pake >> - merge sort = O(n log n) > > Begitu kamu sort, array indexnya berantakan. > >> selanjutnya search bilangan pake >> - binary search = O (log n) >> kalo mau ambil bilangan terkecil atau terbesar malah bisa constant time >> O(1) > > Querynya adalah "cari bilangan terkecil antara index i dan index j di array > A" > Kalau kamu sort, maka index i dan j nya sudah berantakan, maka > hasilnya akan salah. > Apakah masih blum jelas tentang hal ini? > > 2008/6/7 Hendry Luk <[EMAIL PROTECTED] com>: >> napa gak preprocessnya langsung swap bilangan terkecil ke paling depan? >> O(n), lebih efisien drpd merge sort O(n log n). >> >> Selanjutnya. .. searchnya... .. array[0] ;) .... O(1) >> >> Gw gak ngerti nih batasan preprocessingnya > > Ok, contoh berikut mungkin akan lebih jelas: > > A = [ 2, 4, 1, 3 ] > > queryMin( 0, 3 ) = 1 // nilai terkecil di array A antara index 0..3 > adalah 1 (dengan index 3) > queryMin( 1, 1 ) = 4 // nilai terkecil di array A antara index 1..1 > adalah 4 (dengan index 1) > queryMin( 1, 2 ) = 1 // nilai terkecil di array A antara index 1..2 > adalah 1 (dengan index 3) > queryMin( 0, 1 ) = 2 // nilai terkecil di array A antara index 0..1 > adalah 2 (dengan index 0) > queryMin( 3, 3 ) = 3 // nilai terkecil di array A antara index 3..3 > adalah 3 (dengan index 3) > > Kalau kamu sort array A, maka indexnya semua akan berantakan, dan > hasilnya akan salah: > > A = [ 1, 2, 3, 4 ] > > queryMin( 0, 3 ) = 1 // nilai terkecil di array A antara index 0..3 > adalah 1 (dengan index 3) (ok ini benar) > queryMin( 1, 1 ) = 2 // nilai terkecil di array A antara index 1..1 > adalah 2 (dengan index 1) (ini SALAH) > queryMin( 1, 2 ) = 1 // nilai terkecil di array A antara index 1..2 > adalah 2 (dengan index 1) (ini SALAH) > queryMin( 0, 1 ) = 2 // nilai terkecil di array A antara index 0..1 > adalah 1 (dengan index 0) (ini SALAH) > queryMin( 3, 3 ) = 3 // nilai terkecil di array A antara index 3..3 > adalah 4 (dengan index 3) (ini SALAH) > > Query pertama mungkin benar, tapi query ke dua dan seterusnya akan salah. > Karena indexnya setelah disort, bukan lagi index AWAL dari array A semula. > Sedangkan query yang diminta adalah index AWAL dari array A. > > Felix Halim > > -- George Burns - "You can't help getting older, but you don't have to get old."
