Aye aye... how r ya doing, win! ;) Btw [EMAIL PROTECTED] itu orang laen. Just when i thought gw satu2nya nama-depan Hendry on the planet.
2008/6/9 Adelwin Handoyo <[EMAIL PROTECTED]>: > 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] <vk_leon%40yahoo.com>>: > > > 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]<felix.halim%40gmail.com>> > wrote: > > > > From: Felix Halim <[EMAIL PROTECTED] <felix.halim%40gmail.com>> > > Subject: Re: [JUG-Indonesia] Kode menarik > > To: jug-indonesia@yahoogroups.com <jug-indonesia%40yahoogroups.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." > >
