Re: [JUG-Indonesia] Kode menarik

[Andrian Kurniady]

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=Static&d1=tutorials&d2=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

[Felix Halim]

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=Static&d1=tutorials&d2=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

[Feris Thia]

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

[Kong Putra]

Sekedar info.., dari hasil googling... :)

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

Felix Halim wrote:


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

[Felix Halim]

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

[viking leon]

wah engga kepikiran dibikin BSTnya kayak gitu >.<, jempolan deh struktur 
treenya . 

regards
- yohan -

--- On Tue, 6/10/08, Felix Halim <[EMAIL PROTECTED]> wrote:
From: Felix Halim <[EMAIL PROTECTED]>
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

[Frans Thamura]

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

[Andrian Kurniady]

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

[Felix Halim]

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

[Felix Halim]

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

[Andrian Kurniady]

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

[Felix Halim]

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

[viking leon]

ow soalnya ada dua yah, maapkan engga kebaca yang awal, jaid engga tau .

regards,
yohan

--- On Mon, 6/9/08, Jecki Sumargo <[EMAIL PROTECTED]> wrote:
From: Jecki Sumargo <[EMAIL PROTECTED]>
Subject: Re: [JUG-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com
Date: Monday, June 9, 2008, 8:56 AM











2008/6/9 Adelwin Handoyo <[EMAIL PROTECTED] com>:

> 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

[viking leon]

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:

>> BST value-nya:

>> 2

>> / \

>> 1 4

>>   /

>> 3

>> BST indexnya:

>> 0

>> / \

>> 2 1

>>   /

>>  3
jadinya
  i:0|v:2
 /   \
  i:2|v:1   i:1|v:4
              /
    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
3>2
cari di kanan ktemu node 4

4>3
cari di kiri ktemu 3, 

selanjutnya stelah node ktemu bisa cari berdasar index melulu.

--- 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, 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 <[EMAIL PROTECTED] com>:

> 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] com>:

> 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 <felix.halim@ gmail.com> wrote:

>

> From: Felix Halim <felix.halim@ gmail.com>

> 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

[Feris Thia]

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]
> >:
> > 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
>  
>



-- 
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

[Adelwin Handoyo]

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

[Felix Halim]

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

[Adelwin Handoyo]

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

[Felix Halim]

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

[Adelwin Handoyo]

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

[Eko Wibowo]

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

[Felix Halim]

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

[Eko Wibowo]

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

[Felix Halim]

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

[Adelwin Handoyo]

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 d

Re: [JUG-Indonesia] Kode menarik

[Hendry Luk]

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 

Re: [JUG-Indonesia] Kode menarik

[Jecki Sumargo]

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

[Frans Thamura]

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

[viking leon]

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
   
/ \
 
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)

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>:












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

[Frans Thamura]

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

[viking leon]

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 <[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: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

[Frans Thamura]

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

[viking leon]

ralat salah itung:

preprocess log 1jt=6
(n log n ): 1jt x 6 = 6jt

2000 x search 
1search = log n = log 1 jt = 6
2000x 6= 12.000

total: 6.012.000


--- On Mon, 6/9/08, viking leon <[EMAIL PROTECTED]> wrote:
From: viking leon <[EMAIL PROTECTED]>
Subject: Re: [JUG-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com
Date: Monday, June 9, 2008, 5:26 AM











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
 =  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 <[EMAIL PROTECTED] com> wrote:
From: Adelwin Handoyo <[EMAIL PROTECTED] com>
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 <[EMAIL PROTECTED] 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

>/ \

>  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 <felix.halim@ gmail.com> wrote:

>

> From: Felix Halim <felix.halim@ gmail.com>

> Subject: Re: [JUG-Indonesia] Kode menarik

> To: jug-indonesia@ yahoogroups. com

> Date: Saturday, June 7, 2008, 1:45 PM

>

> 2008/6/7 Hendry <hendry.htc@ gmail. 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 pape

Re: [JUG-Indonesia] Kode menarik

[viking leon]

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 =  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 <[EMAIL PROTECTED]> wrote:
From: Adelwin Handoyo <[EMAIL PROTECTED]>
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 <[EMAIL PROTECTED] 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

>/ \

>  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 <felix.halim@ gmail.com> wrote:

>

> From: Felix Halim <felix.halim@ gmail.com>

> Subject: Re: [JUG-Indonesia] Kode menarik

> To: jug-indonesia@ yahoogroups. com

> Date: Saturday, June 7, 2008, 1:45 PM

>

> 2008/6/7 Hendry <hendry.htc@ gmail. 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).

>

&

Re: [JUG-Indonesia] Kode menarik

[viking leon]

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

>/ \

>  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

[Felix Halim]

2008/6/9 Adelwin Handoyo <[EMAIL PROTECTED]>:
> 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..

Preprocess O ( N ) itu termasuk optimal.
Karena untuk baca semua element saja sudah O ( N ).
Tidak ada preprocess yang bisa lebih kecil dari O ( N ).

> gue ada idea lebih bagus :p
> preprocess nya 1 langkah doang..
> yaitu mengalikan semua angka nya..

Sayang sekali, Ini juga O ( N ), bukan O ( 1 ).
Kalau angkanya ada 1 juta, kamu akan looping 1 juta.
Itulah yang dimaksud O ( N ).

Kalau O ( 1 ) artinya: kalau datanya 1 juta atau berapapun,
kamu cuma looping 1 kali.

O ( 1 ) adalah constant, tidak tergantung jumlah / besarnya input.


> lalu output array nya tinggal angka hasil preprocess di bagi dengan
> input[i] sendiri..

Angka hasil preprocess bisa 0 kalau salah satu element di A adalah 0.
Dan perlu diingat, hasil perkalian ini bisa lebih dari 1 juta digit.
Algoritma perkalian yang tercepat sekalipun akan lama memprocess 1
digit perkalian.


> 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?

Apalagi permbagian, ini lebih lambat dari perkalian.

Kecuali kamu bisa membuat perkalian dan pembagian yang efficient,
cara ini tidak bisa dipakai.

FYI, operasi BigInteger itu sendiri pun adalah problem yang sangat populer.

Felix Halim

Re: [JUG-Indonesia] Kode menarik

[Felix Halim]

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

[Adelwin Handoyo]

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 batas

Re: [JUG-Indonesia] Kode menarik

[viking leon]

sory double posting keteken send waktu gambar2 BStnya

preprocess bikin:
- binary search tree (left selalu lebih kecil dari parent, kanan selalu lebih 
gede dari parent)
tapi yang disimpan dalam binary tree adalah indexnya bkan valuenya

untuk array ini: [2,4,1,3]
BST value-nya:
  
2 
   
/  \
    1  
    4
 
 /
  
   3
BST indexnya:
  0
   
/ \
 
2    1
 
 /
   
 3
tuk bikin BST dari array yang sudah ada kira2: O(n)



searchnya pake algo kira2 begini:
- search on left, 
kalo belum ktemu search on right
kalo udah ktemu terus search on left (cari terus ke node left  paling 
dalam yang bisa ditemukan note: node right engga usah disearch)

jadi tuk search:

queryMin( 0, 3 ) = 
- ktemu 0, keep on searching left
- ktemu 2 keep on searching left which is null 
so hasilnya = 2


queryMin( 1, 1 ) = 
- 0, belum ktemu cari kiri
- 2 belum ktemu kiri, kanan ga ada
- recursif back to 0, kanannya 1
- 1 ktemu, cari kiri null
hasil = 1


queryMin( 1, 2 ) = 1 
- 0 belum ktemu, cari kiri
- 2 ktemu cari kiri, null
hasil=2


queryMin( 0, 1 ) = 2 
- 0 ktemu, keep kiri
- kiri = 2, tidak ada di index balek ke parent
hasil = 0


queryMin( 3, 3 ) = 
- 0 belum ktemu cari kiri
- kiri =2 tidak ada di index balek parent search kanan
- 1 belum ktemu cari kiri = null
- cari kanan, ktemu =3, keep kiri = null
- hasil = 3


searchnya kira2 = O(log n)

regards,
yohan



--- On Sat, 6/7/08, Felix Halim <[EMAIL PROTECTED]> wrote:
From: Felix Halim <[EMAIL PROTECTED]>
Subject: Re: [JUG-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com
Date: Saturday, June 7, 2008, 1:45 PM











2008/6/7 Hendry <[EMAIL PROTECTED] com>:

> soal ini kamu yang bikin? atau penjelasan berikut ini based on your 
assumption?

> kalau kamu yang bikin, i got no further questions, tapi kalau hanya

> based on assumption, seperti nya arti dan maksud dari soal dan

> penjelasan yang diberikan berikut sudah berbeda.



Soal ini adalah soal classic (sudah ada dari jaman dahulu), jadi bukan

saya yang bikin.

Yang research solusinya juga banyak (banyak scientific paper ttg problem ini).



Hmm... saya tulis ulang deh problemnya, sepertinya kurang jelas:



Diberikan array of integer A yang isinya adalah bilangan integer acak

sebanyak N elements.

Saya ingin query bilangan integer terkecil dari array A yang index nya

antara i dan j (inclusive).

Index dari array adalah 0-based (index dimulai dari angka 0).



Untuk memprocess tiap query, harus tidak lebih dari O ( log N ) steps.

Tapi query ini bisa banyak kali (querynya bukan cuman satu kali).

Dan anda diperbolehkan untuk preprocess array A terlebih dahulu tapi

tidak lebih dari O ( N log N ) steps.



Semoga tidak ada keambiguan lagi.



2008/6/7 viking leon <[EMAIL PROTECTED] com>:

> preprocessnya pake

> - merge sort = O(n log n)



Begitu kamu sort, array indexnya berantakan.



> selanjutnya search bilangan pake

> - binary search = O (log n)

> kalo mau ambil bilangan terkecil atau terbesar malah bisa constant time 
O(1)



Querynya adalah "cari bilangan terkecil antara index i dan index j di array A"

Kalau kamu sort, maka index i dan j nya sudah berantakan, maka

hasilnya akan salah.

Apakah masih blum jelas tentang hal ini?



2008/6/7 Hendry Luk <[EMAIL PROTECTED] com>:

> napa gak preprocessnya langsung swap bilangan terkecil ke paling depan?

> O(n), lebih efisien drpd merge sort O(n log n).

>

> Selanjutnya. .. searchnya... .. array[0] ;)   O(1)

>

> Gw gak ngerti nih batasan preprocessingnya



Ok, contoh berikut mungkin akan lebih jelas:



A = [ 2, 4, 1, 3 ]



queryMin( 0, 3 ) = 1   // nilai terkecil di array A antara index 0..3

adalah 1 (dengan index 3)

queryMin( 1, 1 ) = 4   // nilai terkecil di array A antara index 1..1

adalah 4 (dengan index 1)

queryMin( 1, 2 ) = 1   // nilai terkecil di array A antara index 1..2

adalah 1 (dengan index 3)

queryMin( 0, 1 ) = 2   // nilai terkecil di array A antara index 0..1

adalah 2 (dengan index 0)

queryMin( 3, 3 ) = 3   // nilai terkecil di array A antara index 3..3

adalah 3 (dengan index 3)



Kalau kamu sort array A, maka indexnya semua akan berantakan, dan

hasilnya akan salah:



A = [ 1, 2, 3, 4 ]



queryMin( 0, 3 ) = 1   // nilai terkecil di array A antara index 0..3

adalah 1 (dengan index 3)  (ok ini benar)

queryMin( 1, 1 ) = 2   // nilai terkecil di array A antara index 1..1

adalah 2 (dengan index 1)  (ini SALAH)

queryMin( 1, 2 ) = 1   // nilai terkecil di array A antara index 1..2

adalah 2 (dengan index 1)  (ini SALAH)

queryMin( 0, 1 ) = 2   // nilai terkecil di array A antara index 0..1

adalah 1 (dengan index 0)  (ini SALAH)

queryMin( 3, 3 ) = 3   // nilai terkecil di array A antara index 3..3

adalah 4 (dengan index 3)  (ini SALAH)



Query pertama mungkin benar, tapi query ke dua dan seter

Re: [JUG-Indonesia] Kode menarik

[viking leon]

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:
  
2 
   
/  \
    1  
    4
 
 /
  
   3
BST indexnya:




--- On Sat, 6/7/08, Felix Halim <[EMAIL PROTECTED]> wrote:
From: Felix Halim <[EMAIL PROTECTED]>
Subject: Re: [JUG-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com
Date: Saturday, June 7, 2008, 1:45 PM











2008/6/7 Hendry <[EMAIL PROTECTED] com>:

> soal ini kamu yang bikin? atau penjelasan berikut ini based on your 
assumption?

> kalau kamu yang bikin, i got no further questions, tapi kalau hanya

> based on assumption, seperti nya arti dan maksud dari soal dan

> penjelasan yang diberikan berikut sudah berbeda.



Soal ini adalah soal classic (sudah ada dari jaman dahulu), jadi bukan

saya yang bikin.

Yang research solusinya juga banyak (banyak scientific paper ttg problem ini).



Hmm... saya tulis ulang deh problemnya, sepertinya kurang jelas:



Diberikan array of integer A yang isinya adalah bilangan integer acak

sebanyak N elements.

Saya ingin query bilangan integer terkecil dari array A yang index nya

antara i dan j (inclusive).

Index dari array adalah 0-based (index dimulai dari angka 0).



Untuk memprocess tiap query, harus tidak lebih dari O ( log N ) steps.

Tapi query ini bisa banyak kali (querynya bukan cuman satu kali).

Dan anda diperbolehkan untuk preprocess array A terlebih dahulu tapi

tidak lebih dari O ( N log N ) steps.



Semoga tidak ada keambiguan lagi.



2008/6/7 viking leon <[EMAIL PROTECTED] com>:

> preprocessnya pake

> - merge sort = O(n log n)



Begitu kamu sort, array indexnya berantakan.



> selanjutnya search bilangan pake

> - binary search = O (log n)

> kalo mau ambil bilangan terkecil atau terbesar malah bisa constant time 
O(1)



Querynya adalah "cari bilangan terkecil antara index i dan index j di array A"

Kalau kamu sort, maka index i dan j nya sudah berantakan, maka

hasilnya akan salah.

Apakah masih blum jelas tentang hal ini?



2008/6/7 Hendry Luk <[EMAIL PROTECTED] com>:

> napa gak preprocessnya langsung swap bilangan terkecil ke paling depan?

> O(n), lebih efisien drpd merge sort O(n log n).

>

> Selanjutnya. .. searchnya... .. array[0] ;)   O(1)

>

> Gw gak ngerti nih batasan preprocessingnya



Ok, contoh berikut mungkin akan lebih jelas:



A = [ 2, 4, 1, 3 ]



queryMin( 0, 3 ) = 1   // nilai terkecil di array A antara index 0..3

adalah 1 (dengan index 3)

queryMin( 1, 1 ) = 4   // nilai terkecil di array A antara index 1..1

adalah 4 (dengan index 1)

queryMin( 1, 2 ) = 1   // nilai terkecil di array A antara index 1..2

adalah 1 (dengan index 3)

queryMin( 0, 1 ) = 2   // nilai terkecil di array A antara index 0..1

adalah 2 (dengan index 0)

queryMin( 3, 3 ) = 3   // nilai terkecil di array A antara index 3..3

adalah 3 (dengan index 3)



Kalau kamu sort array A, maka indexnya semua akan berantakan, dan

hasilnya akan salah:



A = [ 1, 2, 3, 4 ]



queryMin( 0, 3 ) = 1   // nilai terkecil di array A antara index 0..3

adalah 1 (dengan index 3)  (ok ini benar)

queryMin( 1, 1 ) = 2   // nilai terkecil di array A antara index 1..1

adalah 2 (dengan index 1)  (ini SALAH)

queryMin( 1, 2 ) = 1   // nilai terkecil di array A antara index 1..2

adalah 2 (dengan index 1)  (ini SALAH)

queryMin( 0, 1 ) = 2   // nilai terkecil di array A antara index 0..1

adalah 1 (dengan index 0)  (ini SALAH)

queryMin( 3, 3 ) = 3   // nilai terkecil di array A antara index 3..3

adalah 4 (dengan index 3)  (ini SALAH)



Query pertama mungkin benar, tapi query ke dua dan seterusnya akan salah.

Karena indexnya setelah disort, bukan lagi index AWAL dari array A semula.

Sedangkan query yang diminta adalah index AWAL dari array A.



Felix Halim


  




 

















  

Re: [JUG-Indonesia] Kode menarik

[Jecki Sumargo]

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 > > 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

[Felix Halim]

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

[Hendry Luk]

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

2008/6/7 viking leon <[EMAIL PROTECTED]>:

>   preprocessnya pake
> - merge sort = O(n log n)
>
> selanjutnya search bilangan pake
> - binary search = O (log n)
> kalo mau ambil bilangan terkecil atau terbesar malah bisa constant time
> O(1)
>
> --- On *Sat, 6/7/08, Hendry <[EMAIL PROTECTED]>* wrote:
>
> From: Hendry <[EMAIL PROTECTED]>
> Subject: Re: [JUG-Indonesia] Kode menarik
> To: jug-indonesia@yahoogroups.com
> Date: Saturday, June 7, 2008, 12:44 PM
>
>  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.
>
> Regards,
> Hendry
>
> 2008/6/7 Felix Halim >:
> >
> > 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

[viking leon]

preprocessnya pake 
- merge sort = O(n log n)

selanjutnya search bilangan pake 
- binary search = O (log n)
kalo mau ambil bilangan terkecil atau terbesar malah bisa constant time O(1)

--- On Sat, 6/7/08, Hendry <[EMAIL PROTECTED]> wrote:
From: Hendry <[EMAIL PROTECTED]>
Subject: Re: [JUG-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com
Date: Saturday, June 7, 2008, 12:44 PM











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.



Regards,

Hendry



2008/6/7 Felix Halim <felix.halim@ gmail.com>:

>

> 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

[Hendry]

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.

Regards,
Hendry

2008/6/7 Felix Halim <[EMAIL PROTECTED]>:
>
> 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

[Felix Halim]

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

Re: [JUG-Indonesia] Kode menarik

[Felix Halim]

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

[Hendry Luk]

:-O  Any algorighm yg based on array yg ngacak. apa ini even possible
buat less than 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  >> 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

[Hendry Luk]

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]>
> 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  > 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

[Hendry]

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

[Felix Halim]

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

[Frans Thamura]

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

[Feris Thia]

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

[Hendry]

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

[Felix Halim]

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

[Danny]

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] >:
> > 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

[Felix Halim]

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

[Feris Thia]

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

[sm96]

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 >>> 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

[sm96]

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 >> 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

[Feris Thia]

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

[Wilbert]

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

[Felix Halim]

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

[Feris Thia]

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]>
> 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  >> 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
> >
> >
> >
> >
>  
>



-- 
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

[Felix Halim]

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 >  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

[Jecki Sumargo]

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   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 :)

[JUG-Indonesia] Kode menarik

[naray citra]

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 =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)));
}
}