Re: [JUG-Indonesia] Kode menarik
2008/6/11 Feris Thia [EMAIL PROTECTED]: Untuk pemakaian algoritma yang eksekusinya optimal seperti ini memang memori harus besar untuk preprocessnya ya ? Belum baca teorinya sih, tapi pas eksekusi code dari Felix dan Andrian saya harus menambah heap size nya :p Bisa dihitung kok pemakaian memorynya: public static final int[] A = new int[N]; public static final int[][] B = new int[22][N]; public static final int[] lvmat = new int[110]; public static final int[] duapang = new int[30]; Space nya sekitar O ( N log N ). Sekitar 96 MB. ( 24 * 1 juta * 4 byte = 96 MB ) Kalau pake BST, spacenya sekitar O ( N ). Sekitar 40 MB. (setiap node ada 5 values dan total ada 2N nodes, jadi 10N space = 10 * 1 juta * 4 byte = 40 MB) Blum saya test pake profiler sih bener apa kaga. Secara teori harusnya sekitar situ plus minus temporary variables + call stack. 2008/6/11 Kong Putra [EMAIL PROTECTED]: Sekedar info.., dari hasil googling... :) http://www.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor Tidak perlu baca artikel itu pun harusnya bisa kok solve soal RMQ ini. Kalau dilihat sekelebatan, sepertinya solusi O( 1 ) nya si Andrian Kurniady tidak ada di artikel tersebut :P Bener gak kur? coba di cek deh... Felix Halim
Re: [JUG-Indonesia] Kode menarik
Ada kayaknya deh, di text itu nyebutnya Sparse Table (ST) algorithm. Kalau punya Felix itu Segment-tree. Bener gak? TreeNode loe nggak bersih 40mb lix kayaknya, kan itu Class/Object, jadi kayaknya masih ada overheadnya juga. -Kurniady 2008/6/11 Felix Halim [EMAIL PROTECTED]: 2008/6/11 Feris Thia [EMAIL PROTECTED]: Untuk pemakaian algoritma yang eksekusinya optimal seperti ini memang memori harus besar untuk preprocessnya ya ? Belum baca teorinya sih, tapi pas eksekusi code dari Felix dan Andrian saya harus menambah heap size nya :p Bisa dihitung kok pemakaian memorynya: public static final int[] A = new int[N]; public static final int[][] B = new int[22][N]; public static final int[] lvmat = new int[110]; public static final int[] duapang = new int[30]; Space nya sekitar O ( N log N ). Sekitar 96 MB. ( 24 * 1 juta * 4 byte = 96 MB ) Kalau pake BST, spacenya sekitar O ( N ). Sekitar 40 MB. (setiap node ada 5 values dan total ada 2N nodes, jadi 10N space = 10 * 1 juta * 4 byte = 40 MB) Blum saya test pake profiler sih bener apa kaga. Secara teori harusnya sekitar situ plus minus temporary variables + call stack. 2008/6/11 Kong Putra [EMAIL PROTECTED]: Sekedar info.., dari hasil googling... :) http://www.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor Tidak perlu baca artikel itu pun harusnya bisa kok solve soal RMQ ini. Kalau dilihat sekelebatan, sepertinya solusi O( 1 ) nya si Andrian Kurniady tidak ada di artikel tersebut :P Bener gak kur? coba di cek deh... Felix Halim
Re: [JUG-Indonesia] Kode menarik
2008/6/10 Andrian Kurniady [EMAIL PROTECTED]: Ini namanya Range-Minimum Query (RMQ) kan? :D Yah dibocorin... gak seru lagi deh... :P Kalo udah tau keyword nya, udah bisa googling cari2 sendiri jawabannya. Tapi selama blum tahu keywordnya akan mikir keras... Kayaknya sekarang incentive mikirnya udah gak ada kalo dah tahu keywordnya. BTW Lix, itu punya lu kayaknya bukan Binary Search Tree ( http://en.wikipedia.org/wiki/Binary_search_tree ) deh, itu Binary Tree biasa soalnya elemennya nggak sorted kan...? Karena udah bocor sama si Kurniady, yah gw jawabin deh... Range-Index nya yang gw BST in, bukan valuenya. Jadi pas query, gw cari leftmost index sama rightmost index (log N). Kalo diantaranya dia akan langsung return memonya. Felix Halim
Re: [JUG-Indonesia] Kode menarik
Berikut code BST yang run hanya dalam O ( log N ). Dengan pre-processing time O ( N ). Bayangkan anda adalah Google. Yang mempunyai 1 juta data dalam suatu array. Karena pengguna google itu banyak, maka yang query data ke Google akan sangat banyak. Masing2 query itu ingin mengetahui value terkecil dari index i sampai j. Di code saya, preprocessing timenya less than 1 second. Dan bisa menjawab 1 juta queries dalam 5 detik. Karena saya hanya perlu log( 1 juta ) = 20 kali looping untuk masing2 query. Untuk yang lain, especially Kurniady. Coba improve code yang saya attach supaya bisa menjawab 1 juta queries dalam 1 detik. Katanya kan ada tuch algo O ( 1 ) nya untuk query :D Itu tantangan berikutnya :D Bagi yang ingin mempelajari code BST nya, silahkan tanya kalau tidak dimengerti. Felix Halim Minimum.java Description: Binary data
Re: [JUG-Indonesia] Kode menarik
Pake RMQ yang O(log N) bisa dapet segini : Preprocess Time: 0.372 100 Queries Time: 0.372 TOTAL Time: 0.744 Pake RMQ yang O(1) dapet nya segituan juga. [Spoiler] http://andrian.kurniady.net/Minimum.java [/Spoiler] Bener gak? :-D -Andrian Kurniady 2008/6/10 Felix Halim [EMAIL PROTECTED]: Berikut code BST yang run hanya dalam O ( log N ). Dengan pre-processing time O ( N ). Bayangkan anda adalah Google. Yang mempunyai 1 juta data dalam suatu array. Karena pengguna google itu banyak, maka yang query data ke Google akan sangat banyak. Masing2 query itu ingin mengetahui value terkecil dari index i sampai j. Di code saya, preprocessing timenya less than 1 second. Dan bisa menjawab 1 juta queries dalam 5 detik. Karena saya hanya perlu log( 1 juta ) = 20 kali looping untuk masing2 query. Untuk yang lain, especially Kurniady. Coba improve code yang saya attach supaya bisa menjawab 1 juta queries dalam 1 detik. Katanya kan ada tuch algo O ( 1 ) nya untuk query :D Itu tantangan berikutnya :D Bagi yang ingin mempelajari code BST nya, silahkan tanya kalau tidak dimengerti. Felix Halim
Re: [JUG-Indonesia] Kode menarik
mabok gue ... F 2008/6/10 Andrian Kurniady [EMAIL PROTECTED]: Pake RMQ yang O(log N) bisa dapet segini : Preprocess Time: 0.372 100 Queries Time: 0.372 TOTAL Time: 0.744 Pake RMQ yang O(1) dapet nya segituan juga. [Spoiler] http://andrian.kurniady.net/Minimum.java [/Spoiler] Bener gak? :-D -Andrian Kurniady 2008/6/10 Felix Halim [EMAIL PROTECTED]: Berikut code BST yang run hanya dalam O ( log N ). Dengan pre-processing time O ( N ). Bayangkan anda adalah Google. Yang mempunyai 1 juta data dalam suatu array. Karena pengguna google itu banyak, maka yang query data ke Google akan sangat banyak. Masing2 query itu ingin mengetahui value terkecil dari index i sampai j. Di code saya, preprocessing timenya less than 1 second. Dan bisa menjawab 1 juta queries dalam 5 detik. Karena saya hanya perlu log( 1 juta ) = 20 kali looping untuk masing2 query. Untuk yang lain, especially Kurniady. Coba improve code yang saya attach supaya bisa menjawab 1 juta queries dalam 1 detik. Katanya kan ada tuch algo O ( 1 ) nya untuk query :D Itu tantangan berikutnya :D Bagi yang ingin mempelajari code BST nya, silahkan tanya kalau tidak dimengerti. Felix Halim Kalau mau keluar dari mailing list ini, caranya kirim sebuah email ke [EMAIL PROTECTED] Jangan lupa, website JUG Indonesia adalah http://www.jug.or.id Yahoo! Groups Links -- -- Frans Thamura Director of Meruvian Education, Consulting, Networking, Profesional Marketplace, OpenSource Development and Implementation Mobile: +62 855 7888 699 YM: [EMAIL PROTECTED] Linkedin: http://www.linkedin.com/in/fthamura Join jTechnopreneur Program @ jtechnopreneur.com
Re: [JUG-Indonesia] Kode menarik
wah engga kepikiran dibikin BSTnya kayak gitu gt;.lt;, jempolan deh struktur treenya . regards - yohan - --- On Tue, 6/10/08, Felix Halim lt;[EMAIL PROTECTED]gt; wrote: From: Felix Halim lt;[EMAIL PROTECTED]gt; Subject: Re: [JUG-Indonesia] Kode menarik To: jug-indonesia@yahoogroups.com Date: Tuesday, June 10, 2008, 7:03 PM Berikut code BST yang run hanya dalam O ( log N ). Dengan pre-processing time O ( N ). Bayangkan anda adalah Google. Yang mempunyai 1 juta data dalam suatu array. Karena pengguna google itu banyak, maka yang query data ke Google akan sangat banyak. Masing2 query itu ingin mengetahui value terkecil dari index i sampai j. Di code saya, preprocessing timenya less than 1 second. Dan bisa menjawab 1 juta queries dalam 5 detik. Karena saya hanya perlu log( 1 juta ) = 20 kali looping untuk masing2 query. Untuk yang lain, especially Kurniady. Coba improve code yang saya attach supaya bisa menjawab 1 juta queries dalam 1 detik. Katanya kan ada tuch algo O ( 1 ) nya untuk query :D Itu tantangan berikutnya :D Bagi yang ingin mempelajari code BST nya, silahkan tanya kalau tidak dimengerti. Felix Halim
Re: [JUG-Indonesia] Kode menarik
2008/6/10 Andrian Kurniady [EMAIL PROTECTED]: Pake RMQ yang O(log N) bisa dapet segini : Preprocess Time: 0.372 100 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
Re: [JUG-Indonesia] Kode menarik
Sekedar info.., dari hasil googling... :) http://www.topcoder.com/tc?module=Staticd1=tutorialsd2=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 100 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 __
Re: [JUG-Indonesia] Kode menarik
Untuk pemakaian algoritma yang eksekusinya optimal seperti ini memang memori harus besar untuk preprocessnya ya ? Belum baca teorinya sih, tapi pas eksekusi code dari Felix dan Andrian saya harus menambah heap size nya :p Regards, Feris Andrian Kurniady wrote: Pake RMQ yang O(log N) bisa dapet segini : Preprocess Time: 0.372 100 Queries Time: 0.372 TOTAL Time: 0.744
Re: [JUG-Indonesia] Kode menarik
2008/6/9 Eko Wibowo [EMAIL PROTECTED]: Hint : pake pohon2an :D hehehehe S*** Tree btw kalo datanya ga berubah2, bisa lbh bagus lg, pre processing O(N log N) dan query O(1) S*** Tree ? Bukannya S** Tree ? Anyway, pake BST juga bisa kok asal tau tricknya :P S** Tree itu untuk soal lanjutan :P Karena makin banyak yang nimbrung, saya jadi makin semangat. Saya attach skeleton code nya, yang punya waktu luang silahkan coba coding :D BTW, buat anak2 BINUS yang ikut pelatihan tidak boleh jawab :P Juga gak boleh kasih hint aneh2. 6 hari lagi babak final INC 2008! Kalo bisa jawab soal yang ini (sampe jadi codingnya), calon masuk 10 besar deh :D Felix Halim Minimum.java Description: Binary data
Re: [JUG-Indonesia] Kode menarik
oh iya lix, kelebihan 1 * :P hehehehe bisa pk R** jg nih kl statis Felix Halim [EMAIL PROTECTED] wrote: 2008/6/9 Eko Wibowo [EMAIL PROTECTED]: Hint : pake pohon2an :D hehehehe S*** Tree btw kalo datanya ga berubah2, bisa lbh bagus lg, pre processing O(N log N) dan query O(1) S*** Tree ? Bukannya S** Tree ? Anyway, pake BST juga bisa kok asal tau tricknya :P S** Tree itu untuk soal lanjutan :P Karena makin banyak yang nimbrung, saya jadi makin semangat. Saya attach skeleton code nya, yang punya waktu luang silahkan coba coding :D BTW, buat anak2 BINUS yang ikut pelatihan tidak boleh jawab :P Juga gak boleh kasih hint aneh2. 6 hari lagi babak final INC 2008! Kalo bisa jawab soal yang ini (sampe jadi codingnya), calon masuk 10 besar deh :D Felix Halim
Re: [JUG-Indonesia] Kode menarik
gue inget kuliah jadi nya.. ada metoda pembuatan BST yang menjamin tree nya jadi nya seimbang.. jadi bisa nurunin step untuk search nya AVL tree yah namanya kalo gak salah.. 2008/6/9 Eko Wibowo [EMAIL PROTECTED]: oh iya lix, kelebihan 1 * :P hehehehe bisa pk R** jg nih kl statis Felix Halim [EMAIL PROTECTED] wrote: 2008/6/9 Eko Wibowo [EMAIL PROTECTED]: Hint : pake pohon2an :D hehehehe S*** Tree btw kalo datanya ga berubah2, bisa lbh bagus lg, pre processing O(N log N) dan query O(1) S*** Tree ? Bukannya S** Tree ? Anyway, pake BST juga bisa kok asal tau tricknya :P S** Tree itu untuk soal lanjutan :P Karena makin banyak yang nimbrung, saya jadi makin semangat. Saya attach skeleton code nya, yang punya waktu luang silahkan coba coding :D BTW, buat anak2 BINUS yang ikut pelatihan tidak boleh jawab :P Juga gak boleh kasih hint aneh2. 6 hari lagi babak final INC 2008! Kalo bisa jawab soal yang ini (sampe jadi codingnya), calon masuk 10 besar deh :D Felix Halim -- EB White - Genius is more often found in a cracked pot than in a whole one.
Re: [JUG-Indonesia] Kode menarik
lh avl tree khan buat BST... jadi search nya bisa minimum... jadi ya gak perlu traverse the entire tree laa 2008/6/9 Felix Halim [EMAIL PROTECTED]: 2008/6/9 Eko Wibowo [EMAIL PROTECTED]: oh iya lix, kelebihan 1 * :P hehehehe bisa pk R** jg nih kl statis Udah2, jangan kasih hint melulu... hus2... Yang penting reasoning dibaliknya. Meski pake S** Tree atawa R**, kalo cara pakenya salah yah akan saya salahkan :P Gak perlu tahu algo2 advanced kok, BST sudah cukup cepat. Dengan preprocessing time O(N) dan query time O(log N) akan saya anggap benar. Tetapi cara konstruksi BST dan cara query dari BST tersebut harus dilakukan dengan benar. Disitulah letak permasalahn sekaligus keindahannya ;) Jadi sekarang tinggal dipikirkan bagaimana menggunakan BST supaya bisa seperti itu :) FYI, codenya singkat sekali kok, bisa di coding dalam 10 menit :D Ini kan soal programming contest classic. 2008/6/9 Adelwin Handoyo [EMAIL PROTECTED]: gue inget kuliah jadi nya.. ada metoda pembuatan BST yang menjamin tree nya jadi nya seimbang.. jadi bisa nurunin step untuk search nya AVL tree yah namanya kalo gak salah.. Struktur data AVL tree memang akan membuat tree nya seimbang, sehingga kedalamannya log N. Tetapi kalau metode pencariannya adalah traversing the entire tree, yah sama juga boong :D Untuk problem ini, tidak perlu menggunakan AVL tree. Felix Halim Kalau mau keluar dari mailing list ini, caranya kirim sebuah email ke [EMAIL PROTECTED] Jangan lupa, website JUG Indonesia adalah http://www.jug.or.id Yahoo! Groups Links -- EB White - Genius is more often found in a cracked pot than in a whole one.
Re: [JUG-Indonesia] Kode menarik
2008/6/9 Adelwin Handoyo [EMAIL PROTECTED]: lh avl tree khan buat BST... Betul, AVL adalah balanced BST. jadi search nya bisa minimum... Search untuk maximum value atau minimum value di balanced BST memang betul bisa O( log N ). Tetapi constraint di soal saya itu ada 2: - cari minimum value - yang ber-index antara i sampai j inclusive Jadi kalau anda mencari value yang minimum, belum tentu index dari value tersebut berada di range i sampai j. Sehingga anda harus mencari lebih dari sekedar minimum. jadi ya gak perlu traverse the entire tree laa Coba perlihatkan cara anda mencari minimum value di BST yang mempunyai index antara i dan j. Felix Halim
Re: [JUG-Indonesia] Kode menarik
2008/6/9 Eko Wibowo [EMAIL PROTECTED]: oh iya lix, kelebihan 1 * :P hehehehe bisa pk R** jg nih kl statis Udah2, jangan kasih hint melulu... hus2... Yang penting reasoning dibaliknya. Meski pake S** Tree atawa R**, kalo cara pakenya salah yah akan saya salahkan :P Gak perlu tahu algo2 advanced kok, BST sudah cukup cepat. Dengan preprocessing time O(N) dan query time O(log N) akan saya anggap benar. Tetapi cara konstruksi BST dan cara query dari BST tersebut harus dilakukan dengan benar. Disitulah letak permasalahn sekaligus keindahannya ;) Jadi sekarang tinggal dipikirkan bagaimana menggunakan BST supaya bisa seperti itu :) FYI, codenya singkat sekali kok, bisa di coding dalam 10 menit :D Ini kan soal programming contest classic. 2008/6/9 Adelwin Handoyo [EMAIL PROTECTED]: gue inget kuliah jadi nya.. ada metoda pembuatan BST yang menjamin tree nya jadi nya seimbang.. jadi bisa nurunin step untuk search nya AVL tree yah namanya kalo gak salah.. Struktur data AVL tree memang akan membuat tree nya seimbang, sehingga kedalamannya log N. Tetapi kalau metode pencariannya adalah traversing the entire tree, yah sama juga boong :D Untuk problem ini, tidak perlu menggunakan AVL tree. Felix Halim
Re: [JUG-Indonesia] Kode menarik
ooowww mengerti... hehehe my bad.. sorry :p 2008/6/9 Felix Halim [EMAIL PROTECTED]: 2008/6/9 Adelwin Handoyo [EMAIL PROTECTED]: lh avl tree khan buat BST... Betul, AVL adalah balanced BST. jadi search nya bisa minimum... Search untuk maximum value atau minimum value di balanced BST memang betul bisa O( log N ). Tetapi constraint di soal saya itu ada 2: - cari minimum value - yang ber-index antara i sampai j inclusive Jadi kalau anda mencari value yang minimum, belum tentu index dari value tersebut berada di range i sampai j. Sehingga anda harus mencari lebih dari sekedar minimum. jadi ya gak perlu traverse the entire tree laa Coba perlihatkan cara anda mencari minimum value di BST yang mempunyai index antara i dan j. Felix Halim Kalau mau keluar dari mailing list ini, caranya kirim sebuah email ke [EMAIL PROTECTED] Jangan lupa, website JUG Indonesia adalah http://www.jug.or.id Yahoo! Groups Links -- Phyllis Diller - Never go to bed mad. Stay up and fight.
Re: [JUG-Indonesia] Kode menarik
Kepikir list of turning point... ini yang akan di BST-in. Ga tau bener atau kaga ? Lagi ga sempat coding... padahal tertarik banget :p Tunggu yang mecahin aja deh... hehehehe Regards, Feris 2008/6/9 Felix Halim [EMAIL PROTECTED]: 2008/6/9 Eko Wibowo [EMAIL PROTECTED]blue_marcadian%40yahoo.com : oh iya lix, kelebihan 1 * :P hehehehe bisa pk R** jg nih kl statis Udah2, jangan kasih hint melulu... hus2... Yang penting reasoning dibaliknya. Meski pake S** Tree atawa R**, kalo cara pakenya salah yah akan saya salahkan :P Gak perlu tahu algo2 advanced kok, BST sudah cukup cepat. Dengan preprocessing time O(N) dan query time O(log N) akan saya anggap benar. Tetapi cara konstruksi BST dan cara query dari BST tersebut harus dilakukan dengan benar. Disitulah letak permasalahn sekaligus keindahannya ;) Jadi sekarang tinggal dipikirkan bagaimana menggunakan BST supaya bisa seperti itu :) FYI, codenya singkat sekali kok, bisa di coding dalam 10 menit :D Ini kan soal programming contest classic. 2008/6/9 Adelwin Handoyo [EMAIL PROTECTED] adelwin%40gmail.com: gue inget kuliah jadi nya.. ada metoda pembuatan BST yang menjamin tree nya jadi nya seimbang.. jadi bisa nurunin step untuk search nya AVL tree yah namanya kalo gak salah.. Struktur data AVL tree memang akan membuat tree nya seimbang, sehingga kedalamannya log N. Tetapi kalau metode pencariannya adalah traversing the entire tree, yah sama juga boong :D Untuk problem ini, tidak perlu menggunakan AVL tree. Felix Halim -- Thanks Best Regards, Feris PT. Putera Handal Indotama A Business Intelligence Company Jl. K.H. Moh Mansyur No. 11 B 8 - 12 Jakarta - Indonesia Phone : +6221-30119353 Fax : +6221-5513483 Mobile : +628176-474-525 http://business-intelligence.phi-integration.com http://blog.komputasiawan.com
Re: [JUG-Indonesia] Kode menarik
wah kelupaan lagi searchnya hehehe bolong terus engga tau boleh atau engga, biar bantu agar searchnya lebih cepet ... di BSTnya satu node consist of index, dan valuenya: cth: gt;gt; BST value-nya: gt;gt; 2 gt;gt; / \ gt;gt; 1 4 gt;gt;nbsp;nbsp; / gt;gt; 3 gt;gt; BST indexnya: gt;gt; 0 gt;gt; / \ gt;gt; 2 1 gt;gt;nbsp;nbsp; / gt;gt;nbsp; 3 jadinya nbsp;nbsp;nbsp;nbsp;nbsp; i:0|v:2 nbsp;nbsp;nbsp;nbsp; /nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; \ nbsp; i:2|v:1nbsp;nbsp; i:1|v:4 nbsp; nbsp; nbsp; nbsp; nbsp; nbsp; nbsp; / nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; 1:3|v:3 selama belum ktemu nodenya, bisa dicompare valuenya dengan node skarang ... kalo lebih kecil cari di kiri, kalo besar cari di kanan. dengan begini bisa bener2 search pake binary search dalam sebuah BST. misal mencari (3,3), parent v=2 3gt;2 cari di kanan ktemu node 4 4gt;3 cari di kiri ktemu 3, selanjutnya stelah node ktemu bisa cari berdasar index melulu. --- On Mon, 6/9/08, Felix Halim lt;[EMAIL PROTECTED]gt; wrote: From: Felix Halim lt;[EMAIL PROTECTED]gt; Subject: Re: [JUG-Indonesia] Kode menarik To: jug-indonesia@yahoogroups.com Date: Monday, June 9, 2008, 12:09 PM Di email sebelumnya, saya hanya mengkritik BST construction nya. Sekarang saya kritik di algo searchnya. Algo search kamu meskipun menggunakan balanced BST, tetap run in O( N ). Berikut adalah algo kamu untuk search: 2008/6/9 viking leon lt;[EMAIL PROTECTED] comgt;: gt; search on left, gt; kalo belum ktemu search on right gt; kalo udah ktemu terus search on left gt; (cari terus ke node left paling dalam yang gt; bisa ditemukan note: node right engga usah disearch) Algo ini berjalan seperti: 1. in-order Tree traversal biasa, dan akan berhenti jika menemukan suatu node yang mempunyai index antara index queryMin(i,j) , ini O( N ). 2. lalu algonya dilanjutkan dengan traverse ke kiri dari node terakhir itu O( log N ). Kalau ternyata index yang dicari ada di ujung paling kanan bawah, maka kamu akan traverse the entire tree O( N ) sebelum algonya berubah jadi algo ke-2 yang O( log N ). Jadi dalam kasus A = [1, 2, 3, ..., 100] kalau saya queryMin(99, 99) maka kamu akan looping 1 juta kali. Dan ini masih termasuk O( N ). Dalam hal ini, AVL tree, B-Tree, RB-Tree, etc-Tree tidak akan menolong. Bener gak? mohon koreksi kalau saya salah ngerti. Tapi idenya sudah bagus, menggunakan BST. Hanya perlu di-improve supaya worst-case nya dipastikan O( log N ). BTW, saya senang ada yang suka algo di milis JUG :) Felix Halim 2008/6/9 viking leon lt;[EMAIL PROTECTED] comgt;: gt; hehehe, maksudnya aku dapet tapi penjelasannya agak salah: gt; gt; kalau inputnya [1... 1] malah lebih bagus gt; gt; semakin lempeng ke kanan semakin bagus buat cari bilangan terkecil :-) ... gt; karena pada dasarnya stelah ktemu struktur di kanan kita abaikan contoh gt; kalo cari query terkecil [1...1] ktemu 1, cari di kiri null, maka gt; langsung stop dia alhasil O(1) gt; gt; kalau [1 ... 1] nah ini bakal jadi big problem, bener anda bilang bukan gt; O(log n) lagi tapi bakal jadi O(n) gt; gt; tuk BST-nya supaya optimal (balanced on height) saya ada ide pake self gt; balancing BST entah mau pake AA tree, AVL tree, Red-Black Tree, dll gt; udah lupa semua algoritmanya tapi menurut aku pre-processnya bakal less gt; equal O(n log n) ... which is meeting the requirement. gt; gt; regards, gt; yohan gt; gt; --- On Mon, 6/9/08, Felix Halim lt;felix.halim@ gmail.comgt; wrote: gt; gt; From: Felix Halim lt;felix.halim@ gmail.comgt; gt; Subject: Re: [JUG-Indonesia] Kode menarik gt; To: jug-indonesia@ yahoogroups. com gt; Date: Monday, June 9, 2008, 2:40 AM gt; gt; 2008/6/8 viking leon lt;[EMAIL PROTECTED] comgt;: gt;gt; preprocess bikin: gt;gt; - binary search tree (left selalu lebih kecil dari parent, kanan selalu gt;gt; lebih gede dari parent) gt;gt; tapi yang disimpan dalam binary tree adalah indexnya bkan valuenya gt;gt; gt;gt; untuk array ini: [2,4,1,3] gt;gt; BST value-nya: gt;gt; 2 gt;gt; / \ gt;gt; 1 4 gt;gt; / gt;gt; 3 gt;gt; BST indexnya: gt;gt; 0 gt;gt; / \ gt;gt; 2 1 gt;gt; / gt;gt; 3 gt;gt; tuk bikin BST dari array yang sudah ada kira2: O(n) gt; gt; Good answer! gt; gt; BST nya bagus, tapi ada kekurangan. gt; gt; Kalau input saya adalah gt; gt; A = [ 1, 2, 3, 4, .., 100 ] gt; gt; Maka BST kamu akan lempeng ke kanan :P gt; Pencarian Query nya akan jadi O ( N ) bukan O ( log N ) lagi. gt; gt;gt; searchnya kira2 = O(log n) gt; gt; Kalau konstruksi BST nya seperti diatas, maka statement itu tidak benar. gt; Bagaimana anda tweak BST nya supaya querynya guaranteed O ( log N ) ? gt; gt; Felix Halim gt; gt;
Re: [JUG-Indonesia] Kode menarik
ow soalnya ada dua yah, maapkan engga kebaca yang awal, jaid engga tau . regards, yohan --- On Mon, 6/9/08, Jecki Sumargo lt;[EMAIL PROTECTED]gt; wrote: From: Jecki Sumargo lt;[EMAIL PROTECTED]gt; Subject: Re: [JUG-Indonesia] Kode menarik To: jug-indonesia@yahoogroups.com Date: Monday, June 9, 2008, 8:56 AM 2008/6/9 Adelwin Handoyo lt;[EMAIL PROTECTED] comgt;: gt; eh maaf nih... gt; cuma agak penasaran.. gt; henry luk kenal gue kah? gt; gue punya temen kantor dulu namanya henry luk juga.. gt; sorry banget nih OOT... gt; and back to the case.. gt; vk_leon anak kaskus khan yah :p gt; hehehehe gt; kalo ide lu preprocess nya bikin BST wah itu terlalu lama.. gt; emang ntar mau serach nya jadi cepet banget.. gt; tapi emang apa guna nya di bikin search tree.. gt; gue ada idea lebih bagus :p gt; preprocess nya 1 langkah doang.. gt; yaitu mengalikan semua angka nya.. gt; lalu output array nya tinggal angka hasil preprocess di bagi dengan gt; input[i] sendiri.. gt; yang perlu kita cari justru cara bagi nya.. karna gak bole pake gt; operator 'division' itu sendiri.. jadi kita bikin sendiri gt; nah sekarang pertanyaan nya.. ada yang bisa bantuin gue discover gt; method pembagian tanpa operasi pembagian? gt; Sepertinya ini mengacu pada soal yg beda nih? Di sini ud ada 2 soal. 1 Dari 'naray citra' (thread starter) dan 1 lagi dari Felix Halim. SOAL 1) There is an array A[N+1] of N integers. You have to compose an array Output[N+1] such that Output[i] will be equal to the productof all the elements of A[] except A[i]. Example: INPUT:[4, 3, 2, 1, 2] OUTPUT:[12, 16, 24, 48, 24] Solve it without division operator and in O(n) with out using division SOAL 2) 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. Yang di-post oleh viking_leon itu untuk soal 2 sepertinya.
Re: [JUG-Indonesia] Kode menarik
On 6/9/08, viking leon [EMAIL PROTECTED] wrote: engga tau boleh atau engga, biar bantu agar searchnya lebih cepet ... di BSTnya satu node consist of index, dan valuenya: Boleh, silahkan dioprek-oprek BST nya. Tambahin apapun terserah, saya hanya liat complexitasnya. selama belum ktemu nodenya, bisa dicompare valuenya dengan node skarang ... Valuenya? yang saya query adalah index i sampai index j. Saya tidak punya value apapun awalnya. Maksud kamu menggunakan value root pada awalnya? kalo lebih kecil cari di kiri, kalo besar cari di kanan. dengan begini bisa bener2 search pake binary search dalam sebuah BST. misal mencari (3,3), parent v=2 3 2 cari di kanan ktemu node 4 Darimana value 3 berasal? (3,3) itu index i=3 sampai index j=3. Bukan berarti value = 3. Felix Halim
Re: [JUG-Indonesia] Kode menarik
2008/6/6 Felix Halim [EMAIL PROTECTED]: Cara itu terkenal dengan nama Dynamic Programming. Kalo tertarik bikin code2 menarik, itu ladangnya ada di Programming Contest. Ini ada problem yang lebih menantang: Diberikan array of integer A (0-based index). Saya ingin mencari bilangan integer terkecil di array A dengan index antara [i, j] (inclusive). Jawabannya harus dalam O ( log N ) Ini namanya Range-Minimum Query (RMQ) kan? :D Kalo dalam O(1) boleh gak ? ^_^ Ada satu lagi cara untuk solusi soal ini, preprocess dalam O(N log N), query dalam O(1), tidak pake tree dan tidak pake rekursi... BTW Lix, itu punya lu kayaknya bukan Binary Search Tree ( http://en.wikipedia.org/wiki/Binary_search_tree ) deh, itu Binary Tree biasa soalnya elemennya nggak sorted kan...? -Kurniady
Re: [JUG-Indonesia] Kode menarik
hmm, aku krang ngerti batasannya. anyway just another idea: 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: nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; 2 nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; /nbsp;nbsp;nbsp;nbsp;nbsp; \ nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; 1nbsp;nbsp;nbsp;nbsp;nbsp; nbsp; nbsp; 4 nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; / nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; nbsp;nbsp; 3 BST indexnya: --- On Sat, 6/7/08, Felix Halim lt;[EMAIL PROTECTED]gt; wrote: From: Felix Halim lt;[EMAIL PROTECTED]gt; Subject: Re: [JUG-Indonesia] Kode menarik To: jug-indonesia@yahoogroups.com Date: Saturday, June 7, 2008, 1:45 PM 2008/6/7 Hendry lt;[EMAIL PROTECTED] comgt;: gt; soal ini kamu yang bikin? atau penjelasan berikut ini based on your assumption? gt; kalau kamu yang bikin, i got no further questions, tapi kalau hanya gt; based on assumption, seperti nya arti dan maksud dari soal dan gt; 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 lt;[EMAIL PROTECTED] comgt;: gt; preprocessnya pake gt; - merge sort = O(n log n) Begitu kamu sort, array indexnya berantakan. gt; selanjutnya search bilangan pake gt; - binary search = O (log n) gt; 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 lt;[EMAIL PROTECTED] comgt;: gt; napa gak preprocessnya langsung swap bilangan terkecil ke paling depan? gt; O(n), lebih efisien drpd merge sort O(n log n). gt; gt; Selanjutnya. .. searchnya... .. array[0] ;) O(1) gt; gt; 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
Re: [JUG-Indonesia] Kode menarik
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: nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; 2 nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; /nbsp;nbsp;nbsp;nbsp;nbsp; \ nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; 1nbsp;nbsp;nbsp;nbsp;nbsp; nbsp; nbsp; 4 nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; / nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; nbsp;nbsp; 3 BST indexnya: nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; 0 nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; /nbsp;nbsp;nbsp;nbsp; \ nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; 2nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; 1 nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; / nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; 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 leftnbsp; 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 lt;[EMAIL PROTECTED]gt; wrote: From: Felix Halim lt;[EMAIL PROTECTED]gt; Subject: Re: [JUG-Indonesia] Kode menarik To: jug-indonesia@yahoogroups.com Date: Saturday, June 7, 2008, 1:45 PM 2008/6/7 Hendry lt;[EMAIL PROTECTED] comgt;: gt; soal ini kamu yang bikin? atau penjelasan berikut ini based on your assumption? gt; kalau kamu yang bikin, i got no further questions, tapi kalau hanya gt; based on assumption, seperti nya arti dan maksud dari soal dan gt; 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 lt;[EMAIL PROTECTED] comgt;: gt; preprocessnya pake gt; - merge sort = O(n log n) Begitu kamu sort, array indexnya berantakan. gt; selanjutnya search bilangan pake gt; - binary search = O (log n) gt; 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 lt;[EMAIL PROTECTED] comgt;: gt; napa gak preprocessnya langsung swap bilangan terkecil ke paling depan? gt; O(n), lebih efisien drpd merge sort O(n log n). gt; gt; Selanjutnya. .. searchnya... .. array[0] ;) O(1) gt; gt; 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
Re: [JUG-Indonesia] Kode menarik
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 / \ 21 / 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
Re: [JUG-Indonesia] Kode menarik
2008/6/8 viking leon [EMAIL PROTECTED]: 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 / \ 21 / 3 tuk bikin BST dari array yang sudah ada kira2: O(n) Good answer! BST nya bagus, tapi ada kekurangan. Kalau input saya adalah A = [ 1, 2, 3, 4, .., 100 ] Maka BST kamu akan lempeng ke kanan :P Pencarian Query nya akan jadi O ( N ) bukan O ( log N ) lagi. searchnya kira2 = O(log n) Kalau konstruksi BST nya seperti diatas, maka statement itu tidak benar. Bagaimana anda tweak BST nya supaya querynya guaranteed O ( log N ) ? Felix Halim
Re: [JUG-Indonesia] Kode menarik
hehehe, maksudnya aku dapet tapi penjelasannya agak salah: kalau inputnya [1... 1] malah lebih bagus semakin lempeng ke kanan semakin bagus buat cari bilangan terkecil :-) ... karena pada dasarnya stelah ktemu struktur di kanan kita abaikan contoh kalo cari query terkecil [1...1] ktemu 1, cari di kiri null, maka langsung stop dia alhasil O(1) kalau [1 ... 1] nah ini bakal jadi big problem, bener anda bilang bukan O(log n) lagi tapi bakal jadi O(n) tuk BST-nya supaya optimal (balanced on height) saya ada ide pake self balancing BST entah mau pake AA tree, AVL tree, Red-Black Tree, dll udah lupa semua algoritmanya tapi menurut aku pre-processnya bakal less equal O(n log n) ... which is meeting the requirement. regards, yohan --- On Mon, 6/9/08, Felix Halim lt;[EMAIL PROTECTED]gt; wrote: From: Felix Halim lt;[EMAIL PROTECTED]gt; Subject: Re: [JUG-Indonesia] Kode menarik To: jug-indonesia@yahoogroups.com Date: Monday, June 9, 2008, 2:40 AM 2008/6/8 viking leon lt;[EMAIL PROTECTED] comgt;: gt; preprocess bikin: gt; - binary search tree (left selalu lebih kecil dari parent, kanan selalu gt; lebih gede dari parent) gt; tapi yang disimpan dalam binary tree adalah indexnya bkan valuenya gt; gt; untuk array ini: [2,4,1,3] gt; BST value-nya: gt; 2 gt;/ \ gt; 1 4 gt; / gt; 3 gt; BST indexnya: gt; 0 gt;/ \ gt; 21 gt; / gt; 3 gt; tuk bikin BST dari array yang sudah ada kira2: O(n) Good answer! BST nya bagus, tapi ada kekurangan. Kalau input saya adalah A = [ 1, 2, 3, 4, .., 100 ] Maka BST kamu akan lempeng ke kanan :P Pencarian Query nya akan jadi O ( N ) bukan O ( log N ) lagi. gt; searchnya kira2 = O(log n) Kalau konstruksi BST nya seperti diatas, maka statement itu tidak benar. Bagaimana anda tweak BST nya supaya querynya guaranteed O ( log N ) ? Felix Halim
Re: [JUG-Indonesia] Kode menarik
iya anak kaskus :D menurut saya kalo pake kali bagi untuk searchnya engga bisa log n lo, jadinya kira2 O(2n) cth: [2,1,4,3] 2x1x4x3=24 ini udah O(n) 24:3=8 24:4=6 24:1=24 24:2=12 ini O(n) lagi total O(2n) kalo untuk one time operation emang O(2n) keliatan bagus ... tapi untuk data yang besar + operasi search yang berulang2, akan jadi jauh lebih lambat, tujuannya di preprocess untuk searchnya bisa optimal O(log n), overheadnya O(n log n) itu termasuk kecil jga dengan pertimbangan hanya perlu one time pre-processing juga ada kemungkinan kalo dikali terus kalo datanya besar bisa ga ketampung (oversize or whatever the name) cth data = 1jt 1x search = 2jt 2000x search =nbsp; 4m preprocess log 1jt=6 1jt x 6 = 6jt 2000 x search = 12 jt total 18 jt 4m ama 18 jt, bakal kerasa banget bedanya regards, yohan --- On Mon, 6/9/08, Adelwin Handoyo lt;[EMAIL PROTECTED]gt; wrote: From: Adelwin Handoyo lt;[EMAIL PROTECTED]gt; Subject: Re: [JUG-Indonesia] Kode menarik To: jug-indonesia@yahoogroups.com Date: Monday, June 9, 2008, 1:08 AM 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 lt;[EMAIL PROTECTED] comgt;: gt; sory double posting keteken send waktu gambar2 BStnya gt; gt; preprocess bikin: gt; - binary search tree (left selalu lebih kecil dari parent, kanan selalu gt; lebih gede dari parent) gt; tapi yang disimpan dalam binary tree adalah indexnya bkan valuenya gt; gt; untuk array ini: [2,4,1,3] gt; BST value-nya: gt; 2 gt;/ \ gt; 1 4 gt; / gt; 3 gt; BST indexnya: gt; 0 gt;/ \ gt; 21 gt; / gt; 3 gt; tuk bikin BST dari array yang sudah ada kira2: O(n) gt; gt; gt; gt; searchnya pake algo kira2 begini: gt; - search on left, gt; kalo belum ktemu search on right gt; kalo udah ktemu terus search on left (cari terus ke node left paling dalam gt; yang bisa ditemukan note: node right engga usah disearch) gt; gt; jadi tuk search: gt; queryMin( 0, 3 ) = gt; - ktemu 0, keep on searching left gt; - ktemu 2 keep on searching left which is null gt; so hasilnya = 2 gt; gt; queryMin( 1, 1 ) = gt; - 0, belum ktemu cari kiri gt; - 2 belum ktemu kiri, kanan ga ada gt; - recursif back to 0, kanannya 1 gt; - 1 ktemu, cari kiri null gt; hasil = 1 gt; gt; queryMin( 1, 2 ) = 1 gt; - 0 belum ktemu, cari kiri gt; - 2 ktemu cari kiri, null gt; hasil=2 gt; gt; queryMin( 0, 1 ) = 2 gt; - 0 ktemu, keep kiri gt; - kiri = 2, tidak ada di index balek ke parent gt; hasil = 0 gt; gt; queryMin( 3, 3 ) = gt; - 0 belum ktemu cari kiri gt; - kiri =2 tidak ada di index balek parent search kanan gt; - 1 belum ktemu cari kiri = null gt; - cari kanan, ktemu =3, keep kiri = null gt; - hasil = 3 gt; gt; searchnya kira2 = O(log n) gt; gt; regards, gt; yohan gt; gt; gt; gt; --- On Sat, 6/7/08, Felix Halim lt;felix.halim@ gmail.comgt; wrote: gt; gt; From: Felix Halim lt;felix.halim@ gmail.comgt; gt; Subject: Re: [JUG-Indonesia] Kode menarik gt; To: jug-indonesia@ yahoogroups. com gt; Date: Saturday, June 7, 2008, 1:45 PM gt; gt; 2008/6/7 Hendry lt;hendry.htc@ gmail. comgt;: gt;gt; soal ini kamu yang bikin? atau penjelasan berikut ini based on your gt;gt; assumption? gt;gt; kalau kamu yang bikin, i got no further questions, tapi kalau hanya gt;gt; based on assumption, seperti nya arti dan maksud dari soal dan gt;gt; penjelasan yang diberikan berikut sudah berbeda. gt; gt; Soal ini adalah soal classic (sudah ada dari jaman dahulu), jadi bukan gt; saya yang bikin. gt; Yang research solusinya juga banyak (banyak scientific paper ttg problem gt; ini). gt; gt; Hmm... saya tulis ulang deh problemnya, sepertinya kurang jelas: gt; gt; Diberikan array of integer A yang isinya adalah bilangan integer acak gt; sebanyak N elements. gt; Saya ingin query bilangan integer terkecil dari array A yang index nya gt; antara i dan j (inclusive). gt; Index dari array adalah 0-based (index dimulai dari angka 0). gt; gt; Untuk memprocess tiap query, harus tidak lebih dari O ( log N ) steps. gt; Tapi query ini bisa banyak kali (querynya
Re: [JUG-Indonesia] Kode menarik
ini ngomongin log, gue gak mudeng tapi kalau gue lihat , tree dan index ini bisa dipake buat cari value dalam tree kagak yah apakah array ini bisa merepresentasikan tree? F
Re: [JUG-Indonesia] Kode menarik
mungkin agak kebalik bukan arraynya merepresentasikan tree tetapi arraynya direpresentasikan dalam tree. Tapi yang disimpan oleh treenya hanya index dari array tersebut (value sesungguhnya tetap di array) . setelah index dari bilangan terkecil ditemukan dengan melakukan search pada tree, selanjutnya indexnya perlu di lookup ke arraynya untuk mengetahui bilangan sesungguhnya. --- On Mon, 6/9/08, Frans Thamura lt;[EMAIL PROTECTED]gt; wrote: From: Frans Thamura lt;[EMAIL PROTECTED]gt; Subject: Re: [JUG-Indonesia] Kode menarik To: jug-indonesia@yahoogroups.com Date: Monday, June 9, 2008, 6:47 AM ini ngomongin log, gue gak mudeng tapi kalau gue lihat , tree dan index ini bisa dipake buat cari value dalam tree kagak yah apakah array ini bisa merepresentasikan tree? F
Re: [JUG-Indonesia] Kode menarik
2008/6/9 viking leon [EMAIL PROTECTED]: mungkin agak kebalik bukan arraynya merepresentasikan tree tetapi arraynya direpresentasikan dalam tree. Tapi yang disimpan oleh treenya hanya index dari array tersebut (value sesungguhnya tetap di array) . setelah index dari bilangan terkecil ditemukan dengan melakukan search pada tree, selanjutnya indexnya perlu di lookup ke arraynya untuk mengetahui bilangan sesungguhnya. array dirubah jadi tree, emang harus adaindex, saya sih pake satu dimensi iparent untuk melakukannya tapi gimana searchnya diatas dijelaskan log untuk search bisa kanan saja ini gimana yah
Re: [JUG-Indonesia] Kode menarik
ow cara searchnya ada di postingan lama sih ... saya post lagi dibawah, maaf kalo tulisannya acak2an Re: [JUG-Indonesia] Kode menarik 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: nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; 2 nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; /nbsp;nbsp;nbsp;nbsp;nbsp; \ nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; 1nbsp;nbsp;nbsp;nbsp;nbsp; nbsp; nbsp; 4 nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; / nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; nbsp;nbsp; 3 BST indexnya: nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; 0 nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; /nbsp;nbsp;nbsp;nbsp; \ nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; 2nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; 1 nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; / nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp; 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 leftnbsp; 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) masalah search kanan aja mungkin maksudnya kiri saja, tree bagian kanan stelah ktemu bisa diabaikan karena pada dasarnya untuk mencari bilangan terkecil, bagian kiri selalu lebih kecil dari parent sedangkan bagian kanan selalu lebih besar dari parent, jadi kalo sudah dapat parentnya engga perlu lagi untuk mencari disbelah kanan karena sudah pasti lebih besar. tentang log n, ini maksudnya waktu untuk mencari sebuah node dalam BST kira2 sebanding dengan height/tinggi dari tree tersebut. tinggi sebuah BST yang balance kira2 adalah log n. regards, yohan --- On Mon, 6/9/08, Frans Thamura lt;[EMAIL PROTECTED]gt; wrote: From: Frans Thamura lt;[EMAIL PROTECTED]gt; Subject: Re: [JUG-Indonesia] Kode menarik To: jug-indonesia@yahoogroups.com Date: Monday, June 9, 2008, 6:57 AM 2008/6/9 viking leon lt;[EMAIL PROTECTED] comgt;: mungkin agak kebalik bukan arraynya merepresentasikan tree tetapi arraynya direpresentasikan dalam tree. Tapi yang disimpan oleh treenya hanya index dari array tersebut (value sesungguhnya tetap di array) . setelah index dari bilangan terkecil ditemukan dengan melakukan search pada tree, selanjutnya indexnya perlu di lookup ke arraynya untuk mengetahui bilangan sesungguhnya. array dirubah jadi tree, emang harus adaindex, saya sih pake satu dimensi iparent untuk melakukannya tapi gimana searchnya diatas dijelaskan log untuk search bisa kanan saja ini gimana yah
Re: [JUG-Indonesia] Kode menarik
yah bener gara gara reply ini saya jadi ikutan nimbrung maklum lg search sebuah value dalam tree tiap kali refresh ini akan jadi core feature di dalam cimande http://www.jroller.com/fthamura/entry/cimande_update_security_hole maklum feature ini sudah build in di cimande 1.2.3.2 tap saya melihat tree interceptor ini sebuah methode yang rakus memory makanya saya lg cari metode lain 2008/6/9 viking leon [EMAIL PROTECTED]: ow cara searchnya ada di postingan lama sih ... saya post lagi dibawah, maaf kalo tulisannya acak2an Re: [JUG-Indonesia] Kode menarik 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 / \ 21 / 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) masalah search kanan aja mungkin maksudnya kiri saja, tree bagian kanan stelah ktemu bisa diabaikan karena pada dasarnya untuk mencari bilangan terkecil, bagian kiri selalu lebih kecil dari parent sedangkan bagian kanan selalu lebih besar dari parent, jadi kalo sudah dapat parentnya engga perlu lagi untuk mencari disbelah kanan karena sudah pasti lebih besar. tentang log n, ini maksudnya waktu untuk mencari sebuah node dalam BST kira2 sebanding dengan height/tinggi dari tree tersebut. tinggi sebuah BST yang balance kira2 adalah log n. regards, yohan --- On *Mon, 6/9/08, Frans Thamura [EMAIL PROTECTED]* wrote: From: Frans Thamura [EMAIL PROTECTED] Subject: Re: [JUG-Indonesia] Kode menarik To: jug-indonesia@yahoogroups.com Date: Monday, June 9, 2008, 6:57 AM 2008/6/9 viking leon [EMAIL PROTECTED] com [EMAIL PROTECTED]: mungkin agak kebalik bukan arraynya merepresentasikan tree tetapi arraynya direpresentasikan dalam tree. Tapi yang disimpan oleh treenya hanya index dari array tersebut (value sesungguhnya tetap di array) . setelah index dari bilangan terkecil ditemukan dengan melakukan search pada tree, selanjutnya indexnya perlu di lookup ke arraynya untuk mengetahui bilangan sesungguhnya. array dirubah jadi tree, emang harus adaindex, saya sih pake satu dimensi iparent untuk melakukannya tapi gimana searchnya diatas dijelaskan log untuk search bisa kanan saja ini gimana yah -- -- Frans Thamura Director of Meruvian Education, Consulting, Networking, Profesional Marketplace, OpenSource Development and Implementation Mobile: +62 855 7888 699 YM: [EMAIL PROTECTED] Linkedin: http://www.linkedin.com/in/fthamura Join jTechnopreneur Program @ jtechnopreneur.com
Re: [JUG-Indonesia] Kode menarik
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? Sepertinya ini mengacu pada soal yg beda nih? Di sini ud ada 2 soal. 1 Dari 'naray citra' (thread starter) dan 1 lagi dari Felix Halim. SOAL 1) There is an array A[N+1] of N integers. You have to compose an array Output[N+1] such that Output[i] will be equal to the productof all the elements of A[] except A[i]. Example: INPUT:[4, 3, 2, 1, 2] OUTPUT:[12, 16, 24, 48, 24] Solve it without division operator and in O(n) with out using division SOAL 2) 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. Yang di-post oleh viking_leon itu untuk soal 2 sepertinya.
Re: [JUG-Indonesia] Kode menarik
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
Re: [JUG-Indonesia] Kode menarik
oalah... ternyata kowe... japri ajeh dah.. :p malu di milis.. wakakaka 2008/6/9 Hendry Luk [EMAIL PROTECTED]: 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]: 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
Re: [JUG-Indonesia] Kode menarik
Di email sebelumnya, saya hanya mengkritik BST construction nya. Sekarang saya kritik di algo searchnya. Algo search kamu meskipun menggunakan balanced BST, tetap run in O( N ). Berikut adalah algo kamu untuk search: 2008/6/9 viking leon [EMAIL PROTECTED]: 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) Algo ini berjalan seperti: 1. in-order Tree traversal biasa, dan akan berhenti jika menemukan suatu node yang mempunyai index antara index queryMin(i,j), ini O( N ). 2. lalu algonya dilanjutkan dengan traverse ke kiri dari node terakhir itu O( log N ). Kalau ternyata index yang dicari ada di ujung paling kanan bawah, maka kamu akan traverse the entire tree O( N ) sebelum algonya berubah jadi algo ke-2 yang O( log N ). Jadi dalam kasus A = [1, 2, 3, ..., 100] kalau saya queryMin(99, 99) maka kamu akan looping 1 juta kali. Dan ini masih termasuk O( N ). Dalam hal ini, AVL tree, B-Tree, RB-Tree, etc-Tree tidak akan menolong. Bener gak? mohon koreksi kalau saya salah ngerti. Tapi idenya sudah bagus, menggunakan BST. Hanya perlu di-improve supaya worst-case nya dipastikan O( log N ). BTW, saya senang ada yang suka algo di milis JUG :) Felix Halim 2008/6/9 viking leon [EMAIL PROTECTED]: hehehe, maksudnya aku dapet tapi penjelasannya agak salah: kalau inputnya [1... 1] malah lebih bagus semakin lempeng ke kanan semakin bagus buat cari bilangan terkecil :-) ... karena pada dasarnya stelah ktemu struktur di kanan kita abaikan contoh kalo cari query terkecil [1...1] ktemu 1, cari di kiri null, maka langsung stop dia alhasil O(1) kalau [1 ... 1] nah ini bakal jadi big problem, bener anda bilang bukan O(log n) lagi tapi bakal jadi O(n) tuk BST-nya supaya optimal (balanced on height) saya ada ide pake self balancing BST entah mau pake AA tree, AVL tree, Red-Black Tree, dll udah lupa semua algoritmanya tapi menurut aku pre-processnya bakal less equal O(n log n) ... which is meeting the requirement. regards, yohan --- On Mon, 6/9/08, Felix Halim [EMAIL PROTECTED] wrote: From: Felix Halim [EMAIL PROTECTED] Subject: Re: [JUG-Indonesia] Kode menarik To: jug-indonesia@yahoogroups.com Date: Monday, June 9, 2008, 2:40 AM 2008/6/8 viking leon [EMAIL PROTECTED] com: 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) Good answer! BST nya bagus, tapi ada kekurangan. Kalau input saya adalah A = [ 1, 2, 3, 4, .., 100 ] Maka BST kamu akan lempeng ke kanan :P Pencarian Query nya akan jadi O ( N ) bukan O ( log N ) lagi. searchnya kira2 = O(log n) Kalau konstruksi BST nya seperti diatas, maka statement itu tidak benar. Bagaimana anda tweak BST nya supaya querynya guaranteed O ( log N ) ? Felix Halim
Re: [JUG-Indonesia] Kode menarik
Hint : pake pohon2an :D hehehehe S*** Tree btw kalo datanya ga berubah2, bisa lbh bagus lg, pre processing O(N log N) dan query O(1) Felix Halim [EMAIL PROTECTED] wrote: Di email sebelumnya, saya hanya mengkritik BST construction nya. Sekarang saya kritik di algo searchnya. Algo search kamu meskipun menggunakan balanced BST, tetap run in O( N ). Berikut adalah algo kamu untuk search: 2008/6/9 viking leon [EMAIL PROTECTED]: 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) Algo ini berjalan seperti: 1. in-order Tree traversal biasa, dan akan berhenti jika menemukan suatu node yang mempunyai index antara index queryMin(i,j), ini O( N ). 2. lalu algonya dilanjutkan dengan traverse ke kiri dari node terakhir itu O( log N ). Kalau ternyata index yang dicari ada di ujung paling kanan bawah, maka kamu akan traverse the entire tree O( N ) sebelum algonya berubah jadi algo ke-2 yang O( log N ). Jadi dalam kasus A = [1, 2, 3, ..., 100] kalau saya queryMin(99, 99) maka kamu akan looping 1 juta kali. Dan ini masih termasuk O( N ). Dalam hal ini, AVL tree, B-Tree, RB-Tree, etc-Tree tidak akan menolong. Bener gak? mohon koreksi kalau saya salah ngerti. Tapi idenya sudah bagus, menggunakan BST. Hanya perlu di-improve supaya worst-case nya dipastikan O( log N ). BTW, saya senang ada yang suka algo di milis JUG :) Felix Halim 2008/6/9 viking leon [EMAIL PROTECTED]: hehehe, maksudnya aku dapet tapi penjelasannya agak salah: kalau inputnya [1... 1] malah lebih bagus semakin lempeng ke kanan semakin bagus buat cari bilangan terkecil :-) ... karena pada dasarnya stelah ktemu struktur di kanan kita abaikan contoh kalo cari query terkecil [1...1] ktemu 1, cari di kiri null, maka langsung stop dia alhasil O(1) kalau [1 ... 1] nah ini bakal jadi big problem, bener anda bilang bukan O(log n) lagi tapi bakal jadi O(n) tuk BST-nya supaya optimal (balanced on height) saya ada ide pake self balancing BST entah mau pake AA tree, AVL tree, Red-Black Tree, dll udah lupa semua algoritmanya tapi menurut aku pre-processnya bakal less equal O(n log n) ... which is meeting the requirement. regards, yohan --- On Mon, 6/9/08, Felix Halim [EMAIL PROTECTED] wrote: From: Felix Halim [EMAIL PROTECTED] Subject: Re: [JUG-Indonesia] Kode menarik To: jug-indonesia@yahoogroups.com Date: Monday, June 9, 2008, 2:40 AM 2008/6/8 viking leon [EMAIL PROTECTED] com: 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) Good answer! BST nya bagus, tapi ada kekurangan. Kalau input saya adalah A = [ 1, 2, 3, 4, .., 100 ] Maka BST kamu akan lempeng ke kanan :P Pencarian Query nya akan jadi O ( N ) bukan O ( log N ) lagi. searchnya kira2 = O(log n) Kalau konstruksi BST nya seperti diatas, maka statement itu tidak benar. Bagaimana anda tweak BST nya supaya querynya guaranteed O ( log N ) ? Felix Halim
Re: [JUG-Indonesia] Kode menarik
2008/6/7 Hendry [EMAIL PROTECTED]: 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]: 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]: 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
Re: [JUG-Indonesia] Kode menarik
On Sat, Jun 7, 2008 at 12:03 PM, Hendry Luk [EMAIL PROTECTED] wrote:
Nope... itu bukan inner loop ;)
oopss.. my mistake. emang bukan inner loop. thx.
On Fri, Jun 6, 2008 at 6:57 PM, Jecki Sumargo [EMAIL PROTECTED] wrote:
On Fri, Jun 6, 2008 at 3:16 PM, naray citra [EMAIL PROTECTED] wrote:
Gw dapet cuplikan kode menarik neh, untuk share aja, sapa tau ada yang
butuh
:D
sumber : http://linkmingle.com/details/865
There is an array A[N+1] of N integers. You have to compose an array
Output[N+1] such that Output[i] will be equal to the productof all the
elements of A[] except A[i].
Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]
Solve it without division operator and in O(n) with out using division
import java.util.Arrays;
public class PArray {
public int[] PSub(int[] inp){
int[] out = new int[inp.length];
out[0]=1;out[1]=inp[0];
for (int i = 2; i inp.length ; i++)
out[i] = inp[i-1]*out[i-1];
int P = 1;
for(int i=inp.length-2;i=0;i--){
P*=inp[i+1];
out[i]=out[i]*P;
}
return out;
}
public static void main(String[] args) {
PArray pArray = new PArray();
int in[] = new int[]{4,3,2,1,2};
System.out.println(INPUT:+
Arrays.toString(in));
System.out.println(OUTPUT:+
Arrays.toString(pArray.PSub(in)));
}
}
Wah ini hasilnya O(n) ato ga ya? Dilihat2 sepertinya ini O(n^2)
soalnya ada inner loop yg jumlahnya mendekati n. CMIIW.
Seru juga. Masih blom ketemu caranya nih :)
Re: [JUG-Indonesia] Kode menarik
Cara itu terkenal dengan nama Dynamic Programming.
Kalo tertarik bikin code2 menarik, itu ladangnya ada di Programming Contest.
Ini ada problem yang lebih menantang:
Diberikan array of integer A (0-based index).
Saya ingin mencari bilangan integer terkecil di array A dengan index
antara [i, j] (inclusive).
Jawabannya harus dalam O ( log N )
Jelas kalo looping dari i sampai j itu gak boleh karena itu O ( N ).
Ada yang bisa?
Kalau tertarik soal2 seperti itu, anda harusnya masuk Programming Contest.
FYI, Google suka orang2 yang tahu banyak algorithms ;)
Makanya Google ngadain Google Code Jam tiap tahun.
Milis yang membahas Programming Contest di indo itu:
http://groups.yahoo.com/group/indo-algo
Tapi sepi nih... disini malah seru :D, bener2 aneh...
Felix Halim
On Fri, Jun 6, 2008 at 4:57 PM, Jecki Sumargo [EMAIL PROTECTED] wrote:
On Fri, Jun 6, 2008 at 3:16 PM, naray citra [EMAIL PROTECTED] wrote:
Gw dapet cuplikan kode menarik neh, untuk share aja, sapa tau ada yang butuh
:D
sumber : http://linkmingle.com/details/865
There is an array A[N+1] of N integers. You have to compose an array
Output[N+1] such that Output[i] will be equal to the productof all the
elements of A[] except A[i].
Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]
Solve it without division operator and in O(n) with out using division
import java.util.Arrays;
public class PArray {
public int[] PSub(int[] inp){
int[] out = new int[inp.length];
out[0]=1;out[1]=inp[0];
for (int i = 2; i inp.length ; i++)
out[i] = inp[i-1]*out[i-1];
int P = 1;
for(int i=inp.length-2;i=0;i--){
P*=inp[i+1];
out[i]=out[i]*P;
}
return out;
}
public static void main(String[] args) {
PArray pArray = new PArray();
int in[] = new int[]{4,3,2,1,2};
System.out.println(INPUT:+
Arrays.toString(in));
System.out.println(OUTPUT:+
Arrays.toString(pArray.PSub(in)));
}
}
Wah ini hasilnya O(n) ato ga ya? Dilihat2 sepertinya ini O(n^2)
soalnya ada inner loop yg jumlahnya mendekati n. CMIIW.
Seru juga. Masih blom ketemu caranya nih :)
Kalau mau keluar dari mailing list ini, caranya kirim sebuah email ke [EMAIL
PROTECTED]
Jangan lupa, website JUG Indonesia adalah http://www.jug.or.id
Yahoo! Groups Links
Re: [JUG-Indonesia] Kode menarik
O(log N) artinya apa Felix ?
Maksudnya dengan N = 10, looping harus cuma log 10 = 1 ?
Regards,
Feris
2008/6/6 Felix Halim [EMAIL PROTECTED]:
Cara itu terkenal dengan nama Dynamic Programming.
Kalo tertarik bikin code2 menarik, itu ladangnya ada di Programming
Contest.
Ini ada problem yang lebih menantang:
Diberikan array of integer A (0-based index).
Saya ingin mencari bilangan integer terkecil di array A dengan index
antara [i, j] (inclusive).
Jawabannya harus dalam O ( log N )
Jelas kalo looping dari i sampai j itu gak boleh karena itu O ( N ).
Ada yang bisa?
Kalau tertarik soal2 seperti itu, anda harusnya masuk Programming Contest.
FYI, Google suka orang2 yang tahu banyak algorithms ;)
Makanya Google ngadain Google Code Jam tiap tahun.
Milis yang membahas Programming Contest di indo itu:
http://groups.yahoo.com/group/indo-algo
Tapi sepi nih... disini malah seru :D, bener2 aneh...
Felix Halim
On Fri, Jun 6, 2008 at 4:57 PM, Jecki Sumargo [EMAIL
PROTECTED]jecki.go%40gmail.com
wrote:
On Fri, Jun 6, 2008 at 3:16 PM, naray citra [EMAIL
PROTECTED]naray_citra%40yahoo.com
wrote:
Gw dapet cuplikan kode menarik neh, untuk share aja, sapa tau ada yang
butuh
:D
sumber : http://linkmingle.com/details/865
There is an array A[N+1] of N integers. You have to compose an array
Output[N+1] such that Output[i] will be equal to the productof all the
elements of A[] except A[i].
Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]
Solve it without division operator and in O(n) with out using division
import java.util.Arrays;
public class PArray {
public int[] PSub(int[] inp){
int[] out = new int[inp.length];
out[0]=1;out[1]=inp[0];
for (int i = 2; i inp.length ; i++)
out[i] = inp[i-1]*out[i-1];
int P = 1;
for(int i=inp.length-2;i=0;i--){
P*=inp[i+1];
out[i]=out[i]*P;
}
return out;
}
public static void main(String[] args) {
PArray pArray = new PArray();
int in[] = new int[]{4,3,2,1,2};
System.out.println(INPUT:+
Arrays.toString(in));
System.out.println(OUTPUT:+
Arrays.toString(pArray.PSub(in)));
}
}
Wah ini hasilnya O(n) ato ga ya? Dilihat2 sepertinya ini O(n^2)
soalnya ada inner loop yg jumlahnya mendekati n. CMIIW.
Seru juga. Masih blom ketemu caranya nih :)
Kalau mau keluar dari mailing list ini, caranya kirim sebuah email ke
[EMAIL PROTECTED]jug-indonesia-unsubscribe%40yahoogroups.com
.
Jangan lupa, website JUG Indonesia adalah http://www.jug.or.id
Yahoo! Groups Links
--
Thanks Best Regards,
Feris
PT. Putera Handal Indotama
A Business Intelligence Company
Jl. K.H. Moh Mansyur No. 11 B 8 - 12
Jakarta - Indonesia
Phone : +6221-30119353
Fax : +6221-5513483
Mobile : +628176-474-525
http://business-intelligence.phi-integration.com
http://blog.komputasiawan.com
Re: [JUG-Indonesia] Kode menarik
Mesti banyak latian nih untuk tahun depan... Aaarrrghhh... :( -- Wilbert : IT UKDW 2006 Java Blog : http://wilbertjava.wordpress.com YM : inherit_c
Re: [JUG-Indonesia] Kode menarik
2008/6/6 Feris Thia [EMAIL PROTECTED]: O(log N) artinya apa Felix ? Maksudnya dengan N = 10, looping harus cuma log 10 = 1 ? Betul, tapi base dari log ini bisa berapapun karena base nya itu dianggep constant. Biasanya yang terpakai paling sering adalah log dengan basis 2. Jadi untuk N = 1 juta, cuma perlu sekitar 20 steps sudah dapat. Felix Halim
Re: [JUG-Indonesia] Kode menarik
Binary search kan sudah harus terurut, kalau sudah terurut tinggal ambil array ke 0 kan ? Kalau ini kan tidak terurut sama sekali :p hehehe CMIIW Regards, Feris 2008/6/6 sm96 [EMAIL PROTECTED]: O(log N) itu contohnya algoritma binary search, dan quick sort O(n log n) O(log N) cenderung lebih cepat dibanding O(n) -- Thanks Best Regards, Feris PT. Putera Handal Indotama A Business Intelligence Company Jl. K.H. Moh Mansyur No. 11 B 8 - 12 Jakarta - Indonesia Phone : +6221-30119353 Fax : +6221-5513483 Mobile : +628176-474-525 http://business-intelligence.phi-integration.com http://blog.komputasiawan.com
Re: [JUG-Indonesia] Kode menarik
O(log N) itu contohnya algoritma binary search, dan quick sort O(n log n)
O(log N) cenderung lebih cepat dibanding O(n)
2008/6/6 Felix Halim [EMAIL PROTECTED]:
Cara itu terkenal dengan nama Dynamic Programming.
Kalo tertarik bikin code2 menarik, itu ladangnya ada di Programming Contest.
Ini ada problem yang lebih menantang:
Diberikan array of integer A (0-based index).
Saya ingin mencari bilangan integer terkecil di array A dengan index
antara [i, j] (inclusive).
Jawabannya harus dalam O ( log N )
Jelas kalo looping dari i sampai j itu gak boleh karena itu O ( N ).
Ada yang bisa?
Kalau tertarik soal2 seperti itu, anda harusnya masuk Programming Contest.
FYI, Google suka orang2 yang tahu banyak algorithms ;)
Makanya Google ngadain Google Code Jam tiap tahun.
Milis yang membahas Programming Contest di indo itu:
http://groups.yahoo.com/group/indo-algo
Tapi sepi nih... disini malah seru :D, bener2 aneh...
Felix Halim
On Fri, Jun 6, 2008 at 4:57 PM, Jecki Sumargo [EMAIL PROTECTED] wrote:
On Fri, Jun 6, 2008 at 3:16 PM, naray citra [EMAIL PROTECTED] wrote:
Gw dapet cuplikan kode menarik neh, untuk share aja, sapa tau ada yang
butuh
:D
sumber : http://linkmingle.com/details/865
There is an array A[N+1] of N integers. You have to compose an array
Output[N+1] such that Output[i] will be equal to the productof all the
elements of A[] except A[i].
Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]
Solve it without division operator and in O(n) with out using division
import java.util.Arrays;
public class PArray {
public int[] PSub(int[] inp){
int[] out = new int[inp.length];
out[0]=1;out[1]=inp[0];
for (int i = 2; i inp.length ; i++)
out[i] = inp[i-1]*out[i-1];
int P = 1;
for(int i=inp.length-2;i=0;i--){
P*=inp[i+1];
out[i]=out[i]*P;
}
return out;
}
public static void main(String[] args) {
PArray pArray = new PArray();
int in[] = new int[]{4,3,2,1,2};
System.out.println(INPUT:+
Arrays.toString(in));
System.out.println(OUTPUT:+
Arrays.toString(pArray.PSub(in)));
}
}
Wah ini hasilnya O(n) ato ga ya? Dilihat2 sepertinya ini O(n^2)
soalnya ada inner loop yg jumlahnya mendekati n. CMIIW.
Seru juga. Masih blom ketemu caranya nih :)
Kalau mau keluar dari mailing list ini, caranya kirim sebuah email ke
[EMAIL PROTECTED]
Jangan lupa, website JUG Indonesia adalah http://www.jug.or.id
Yahoo! Groups Links
--
syaiful.mukhlis
gtalk:[EMAIL PROTECTED]
Re: [JUG-Indonesia] Kode menarik
Boleh pake rekursif juga ya ? 2008/6/6 Felix Halim [EMAIL PROTECTED]: -- Thanks Best Regards, Feris PT. Putera Handal Indotama A Business Intelligence Company Jl. K.H. Moh Mansyur No. 11 B 8 - 12 Jakarta - Indonesia Phone : +6221-30119353 Fax : +6221-5513483 Mobile : +628176-474-525 http://business-intelligence.phi-integration.com http://blog.komputasiawan.com
Re: [JUG-Indonesia] Kode menarik
Kalau nyari angka terkecil, harus O(log n), berarti pake cara yg sama seperti
binary search
2008/6/6 sm96 [EMAIL PROTECTED]:
O(log N) itu contohnya algoritma binary search, dan quick sort O(n log n)
O(log N) cenderung lebih cepat dibanding O(n)
2008/6/6 Felix Halim [EMAIL PROTECTED]:
Cara itu terkenal dengan nama Dynamic Programming.
Kalo tertarik bikin code2 menarik, itu ladangnya ada di Programming Contest.
Ini ada problem yang lebih menantang:
Diberikan array of integer A (0-based index).
Saya ingin mencari bilangan integer terkecil di array A dengan index
antara [i, j] (inclusive).
Jawabannya harus dalam O ( log N )
Jelas kalo looping dari i sampai j itu gak boleh karena itu O ( N ).
Ada yang bisa?
Kalau tertarik soal2 seperti itu, anda harusnya masuk Programming Contest.
FYI, Google suka orang2 yang tahu banyak algorithms ;)
Makanya Google ngadain Google Code Jam tiap tahun.
Milis yang membahas Programming Contest di indo itu:
http://groups.yahoo.com/group/indo-algo
Tapi sepi nih... disini malah seru :D, bener2 aneh...
Felix Halim
On Fri, Jun 6, 2008 at 4:57 PM, Jecki Sumargo [EMAIL PROTECTED] wrote:
On Fri, Jun 6, 2008 at 3:16 PM, naray citra [EMAIL PROTECTED] wrote:
Gw dapet cuplikan kode menarik neh, untuk share aja, sapa tau ada yang
butuh
:D
sumber : http://linkmingle.com/details/865
There is an array A[N+1] of N integers. You have to compose an array
Output[N+1] such that Output[i] will be equal to the productof all the
elements of A[] except A[i].
Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]
Solve it without division operator and in O(n) with out using division
import java.util.Arrays;
public class PArray {
public int[] PSub(int[] inp){
int[] out = new int[inp.length];
out[0]=1;out[1]=inp[0];
for (int i = 2; i inp.length ; i++)
out[i] = inp[i-1]*out[i-1];
int P = 1;
for(int i=inp.length-2;i=0;i--){
P*=inp[i+1];
out[i]=out[i]*P;
}
return out;
}
public static void main(String[] args) {
PArray pArray = new PArray();
int in[] = new int[]{4,3,2,1,2};
System.out.println(INPUT:+
Arrays.toString(in));
System.out.println(OUTPUT:+
Arrays.toString(pArray.PSub(in)));
}
}
Wah ini hasilnya O(n) ato ga ya? Dilihat2 sepertinya ini O(n^2)
soalnya ada inner loop yg jumlahnya mendekati n. CMIIW.
Seru juga. Masih blom ketemu caranya nih :)
Kalau mau keluar dari mailing list ini, caranya kirim sebuah email ke
[EMAIL PROTECTED]
Jangan lupa, website JUG Indonesia adalah http://www.jug.or.id
Yahoo! Groups Links
--
syaiful.mukhlis
gtalk:[EMAIL PROTECTED]
--
syaiful.mukhlis
gtalk:[EMAIL PROTECTED]
Re: [JUG-Indonesia] Kode menarik
2008/6/6 Felix Halim [EMAIL PROTECTED]: Diberikan array of integer A (0-based index). Saya ingin mencari bilangan integer terkecil di array A dengan index antara [i, j] (inclusive). Jawabannya harus dalam O ( log N ) FYI, datanya boleh di preprocess dulu. Tapi preprocessnya gak boleh O(N^2). Contoh: kalo datanya di sort dulu, itu boleh. Berarti preprocessing timenya O(N log N). Tapi ingat, setelah di sort, index awalnya jadi berantakan. Jadi range [i, j] nya harus disesuaikan juga supaya tetap benar. 2008/6/6 sm96 [EMAIL PROTECTED]: Kalau nyari angka terkecil, harus O(log n), berarti pake cara yg sama seperti binary search Solusinya jauh lebih kompleks daripada sekedar binary search. Datanya harus di-preprocess dahulu untuk mendapatkan structure data tertentu. Lalu baru bisa di query untuk angka terkecil antara index [i, j] inclusive. Felix Halim
Re: [JUG-Indonesia] Kode menarik
Apakah data awalnya acak..?, misal A={5,2,4,1,3}, trus disuruh cari data
terkecil.
Klo datanya blh disort dulu, bukannya
udah bs langsung ditemukan hasilnya, dengan mengambil
index ke 0...?, dengan asumsi Big O dari sortingnya ga diperhitungkan.
... setelah di sort, index awalnya jadi berantakan.
Jadi range [i, j] nya harus disesuaikan juga supaya tetap benar..
Ini maksudnya apa ya..?, bukannya hanya disuruh cari data terkecil di dalam
array,
dengan proses O (log N), jadi tidak berpengaruh sm index yg berantakan.
Tx
2008/6/6 Felix Halim [EMAIL PROTECTED]:
2008/6/6 Felix Halim [EMAIL PROTECTED] felix.halim%40gmail.com:
Diberikan array of integer A (0-based index).
Saya ingin mencari bilangan integer terkecil di array A dengan index
antara [i, j] (inclusive).
Jawabannya harus dalam O ( log N )
FYI, datanya boleh di preprocess dulu.
Tapi preprocessnya gak boleh O(N^2).
Contoh: kalo datanya di sort dulu, itu boleh.
Berarti preprocessing timenya O(N log N).
Tapi ingat, setelah di sort, index awalnya jadi berantakan.
Jadi range [i, j] nya harus disesuaikan juga supaya tetap benar.
2008/6/6 sm96 [EMAIL PROTECTED] syaiful.mukhlis%40gmail.com:
Kalau nyari angka terkecil, harus O(log n), berarti pake cara yg sama
seperti
binary search
Solusinya jauh lebih kompleks daripada sekedar binary search.
Datanya harus di-preprocess dahulu untuk mendapatkan structure data
tertentu.
Lalu baru bisa di query untuk angka terkecil antara index [i, j] inclusive.
Felix Halim
Re: [JUG-Indonesia] Kode menarik
2008/6/6 Danny [EMAIL PROTECTED]:
Apakah data awalnya acak..?, misal A={5,2,4,1,3}, trus disuruh cari data
terkecil.
Betul, A itu awalnya isinya acak.
Klo datanya blh disort dulu, bukannya
udah bs langsung ditemukan hasilnya, dengan mengambil
index ke 0...?, dengan asumsi Big O dari sortingnya ga diperhitungkan.
... setelah di sort, index awalnya jadi berantakan.
Jadi range [i, j] nya harus disesuaikan juga supaya tetap benar..
Contoh A = [ 5, 7, 3, 4, 1, 8 ]
Artinya:
index ke 0 valuenya adalah 5
index ke 1 valuenya adalah 7
index ke 2 valuenya adalah 3
index ke 3 valuenya adalah 4
index ke 4 valuenya adalah 1
index ke 5 valuenya adalah 8
Kalau saya mau cari bilangan terkecil yang berada di index antara 0
sampai 3 (inclusive - [0, 3]),
maka jawabannya adalah 3 (dengan index 2).
Kalau kamu sort dulu arraynya:
A = [ 1, 3, 4, 5, 7, 8 ]
Maka index 0 valuenya bukan lagi 5 tapi valuenya menjadi 1.
Maka index 1 valuenya bukan lagi 7 tapi valuenya menjadi 3.
dan seterusnya...
Inilah yang saya maksud berantakan.
Jadi kalau saya ingin mencari bilangan terkecil yang berada di index
antara 0 sampai 3, hasilnya akan salah.
Dalam hal ini, kamu akan bilang hasilnya adalah 1 (di index 0).
Felix Halim
Re: [JUG-Indonesia] Kode menarik
Kenapa tidak hanya sort data yang ada dr indeks 0 sampai 3 saja? SOL Regards, Hendry 2008/6/6 Felix Halim [EMAIL PROTECTED]: Contoh A = [ 5, 7, 3, 4, 1, 8 ] Artinya: index ke 0 valuenya adalah 5 index ke 1 valuenya adalah 7 index ke 2 valuenya adalah 3 index ke 3 valuenya adalah 4 index ke 4 valuenya adalah 1 index ke 5 valuenya adalah 8 Kalau saya mau cari bilangan terkecil yang berada di index antara 0 sampai 3 (inclusive - [0, 3]), maka jawabannya adalah 3 (dengan index 2). Kalau kamu sort dulu arraynya: A = [ 1, 3, 4, 5, 7, 8 ] Maka index 0 valuenya bukan lagi 5 tapi valuenya menjadi 1. Maka index 1 valuenya bukan lagi 7 tapi valuenya menjadi 3. dan seterusnya... Inilah yang saya maksud berantakan. Jadi kalau saya ingin mencari bilangan terkecil yang berada di index antara 0 sampai 3, hasilnya akan salah. Dalam hal ini, kamu akan bilang hasilnya adalah 1 (di index 0). Felix Halim
Re: [JUG-Indonesia] Kode menarik
Karena itu sudah langsung ke solution dan O(n) :p Regards, Feris 2008/6/6 Hendry [EMAIL PROTECTED]: Kenapa tidak hanya sort data yang ada dr indeks 0 sampai 3 saja? SOL Regards, Hendry -- Thanks Best Regards, Feris PT. Putera Handal Indotama A Business Intelligence Company Jl. K.H. Moh Mansyur No. 11 B 8 - 12 Jakarta - Indonesia Phone : +6221-30119353 Fax : +6221-5513483 Mobile : +628176-474-525 http://business-intelligence.phi-integration.com http://blog.komputasiawan.com
Re: [JUG-Indonesia] Kode menarik
dari saya lg cari cari rumus statistika, selain log, tapi sin, cos, juga statistika, mean, average cape jugakan buat sendiri semua ada yang tahu? F
Re: [JUG-Indonesia] Kode menarik
2008/6/7 Hendry [EMAIL PROTECTED]: Kenapa tidak hanya sort data yang ada dr indeks 0 sampai 3 saja? SOL Saya sudah tunggu pertanyaan ini :D Kalau anda sort dari 0 sampai 3, maka tiap kali saya query [i, j] anda akan melakukan sort. Solusi anda adalah O ( N log N ) Itu lebih parah daripada linear scan dari i ke j, dan cari yang minimum O ( N ). Yang saya mau adalah preprocess 1x, dengan complexity maximum O ( N log N ) Lalu untuk setiap query [ i, j ] bisa di jawab hanya dengan O ( log N ). Felix Halim
Re: [JUG-Indonesia] Kode menarik
Kalau membaca soal berikut, asumsi saya, array of integer A tersebut adalah selalu data yang baru, dan kita diminta mencari bilangan integer terkecil. Kalau permintaan nya membuat algoritma ataupun function yang selalu ready menerima data baru, mem preprocess data, lalu the next step selalu menggunakan data yang sudah di preprocess, bukankah itu sudah mem bypass satu step algoritma dari soal tersebut? CMIIW Diberikan array of integer A (0-based index). Saya ingin mencari bilangan integer terkecil di array A dengan index antara [i, j] (inclusive). Jawabannya harus dalam O ( log N ) Jelas kalo looping dari i sampai j itu gak boleh karena itu O ( N ). Ada yang bisa? Regards, Hendry 2008/6/7 Felix Halim [EMAIL PROTECTED]: Saya sudah tunggu pertanyaan ini :D Kalau anda sort dari 0 sampai 3, maka tiap kali saya query [i, j] anda akan melakukan sort. Solusi anda adalah O ( N log N ) Itu lebih parah daripada linear scan dari i ke j, dan cari yang minimum O ( N ). Yang saya mau adalah preprocess 1x, dengan complexity maximum O ( N log N ) Lalu untuk setiap query [ i, j ] bisa di jawab hanya dengan O ( log N ). Felix Halim
Re: [JUG-Indonesia] Kode menarik
Nope... itu bukan inner loop ;)
On Fri, Jun 6, 2008 at 6:57 PM, Jecki Sumargo [EMAIL PROTECTED] wrote:
On Fri, Jun 6, 2008 at 3:16 PM, naray citra [EMAIL
PROTECTED]naray_citra%40yahoo.com
wrote:
Gw dapet cuplikan kode menarik neh, untuk share aja, sapa tau ada yang
butuh
:D
sumber : http://linkmingle.com/details/865
There is an array A[N+1] of N integers. You have to compose an array
Output[N+1] such that Output[i] will be equal to the productof all the
elements of A[] except A[i].
Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]
Solve it without division operator and in O(n) with out using division
import java.util.Arrays;
public class PArray {
public int[] PSub(int[] inp){
int[] out = new int[inp.length];
out[0]=1;out[1]=inp[0];
for (int i = 2; i inp.length ; i++)
out[i] = inp[i-1]*out[i-1];
int P = 1;
for(int i=inp.length-2;i=0;i--){
P*=inp[i+1];
out[i]=out[i]*P;
}
return out;
}
public static void main(String[] args) {
PArray pArray = new PArray();
int in[] = new int[]{4,3,2,1,2};
System.out.println(INPUT:+
Arrays.toString(in));
System.out.println(OUTPUT:+
Arrays.toString(pArray.PSub(in)));
}
}
Wah ini hasilnya O(n) ato ga ya? Dilihat2 sepertinya ini O(n^2)
soalnya ada inner loop yg jumlahnya mendekati n. CMIIW.
Seru juga. Masih blom ketemu caranya nih :)
Re: [JUG-Indonesia] Kode menarik
2008/6/7 Hendry [EMAIL PROTECTED]: Kalau membaca soal berikut, asumsi saya, array of integer A tersebut adalah selalu data yang baru, dan kita diminta mencari bilangan integer terkecil. Kalau permintaan nya membuat algoritma ataupun function yang selalu ready menerima data baru, mem preprocess data, lalu the next step selalu menggunakan data yang sudah di preprocess, bukankah itu sudah mem bypass satu step algoritma dari soal tersebut? CMIIW Array A itu fixed dengan jumlah element N. Saya mempunyai banyak queries: cari bilangan terkecil antara index i dan index j (inclusive). Jadi meskipun array A itu acak, tapi array A tidak pernah berubah. Dan array A yang sama ini akan di query terus menerus. Otomatis kita harus buat query ini efisien donk? Nah, algo linearnya kan itu scan dari i ke j, cari yang minimum, lalu print. Tapi algo itu O ( N ) jalannya. Pertanyaanya, bisakah kita preprocess array A ini sedemikian sehingga setiap query [i, j] bisa diprocess hanya dengan O ( log N ). Tetapi one-time preprocessnya tidak boleh lebih dari O ( N log N ). Felix Halim
Re: [JUG-Indonesia] Kode menarik
2008/6/7 Hendry Luk [EMAIL PROTECTED]: :-O Any algorighm yg based on array yg ngacak. apa ini even possible buat less than O(N)? Tidak akan mungkin kalau tidak di-preprocess terlebih dahulu. Karena untuk ngecek-data nya saja sudah O ( N ). Preprocessnya itu digunakan untuk membuat array acak itu lebih terstruktur. Sehingga setiap query nya bisa di jawab dengan O ( log N ). Preprocess nya itu hanya boleh 1x di awal. Dan preprocessnya itu tidak boleh lebih dari O ( N log N ) steps. Felix Halim
