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
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
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
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
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]:
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
wah engga kepikiran dibikin BSTnya kayak gitu gt;.lt;, jempolan deh struktur
treenya .
regards
- yohan -
--- On Tue, 6/10/08, Felix Halim lt;[EMAIL PROTECTED]gt; wrote:
From: Felix Halim lt;[EMAIL PROTECTED]gt;
Subject: Re: [JUG-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com
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
Sekedar info.., dari hasil googling... :)
http://www.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor
Felix Halim wrote:
2008/6/10 Andrian Kurniady [EMAIL PROTECTED]
mailto:andrian%40kurniady.net:
Pake RMQ yang O(log N) bisa dapet segini :
Preprocess Time: 0.372
100
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
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
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
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
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
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
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
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
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
stelah node ktemu bisa cari berdasar index melulu.
--- On Mon, 6/9/08, Felix Halim lt;[EMAIL PROTECTED]gt; wrote:
From: Felix Halim lt;[EMAIL PROTECTED]gt;
Subject: Re: [JUG-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com
Date: Monday, June 9, 2008, 12:09 PM
Di email
ow soalnya ada dua yah, maapkan engga kebaca yang awal, jaid engga tau .
regards,
yohan
--- On Mon, 6/9/08, Jecki Sumargo lt;[EMAIL PROTECTED]gt; wrote:
From: Jecki Sumargo lt;[EMAIL PROTECTED]gt;
Subject: Re: [JUG-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com
Date: Monday
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
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
;nbsp;
/
nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;
nbsp;nbsp; 3
BST indexnya:
--- On Sat, 6/7/08, Felix Halim lt;[EMAIL PROTECTED]gt; wrote:
From: Felix Halim lt;[EMAIL PROTECTED]gt;
Subject: Re: [JUG-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com
Date
, Felix Halim lt;[EMAIL PROTECTED]gt; wrote:
From: Felix Halim lt;[EMAIL PROTECTED]gt;
Subject: Re: [JUG-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com
Date: Saturday, June 7, 2008, 1:45 PM
2008/6/7 Hendry lt;[EMAIL PROTECTED] comgt;:
gt; soal ini kamu yang
[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
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
-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com
Date: Monday, June 9, 2008, 2:40 AM
2008/6/8 viking leon lt;[EMAIL PROTECTED] comgt;:
gt; preprocess bikin:
gt; - binary search tree (left selalu lebih kecil dari parent, kanan selalu
gt; lebih gede dari parent
:
From: Adelwin Handoyo lt;[EMAIL PROTECTED]gt;
Subject: Re: [JUG-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com
Date: Monday, June 9, 2008, 1:08 AM
eh maaf nih...
cuma agak penasaran..
henry luk kenal gue kah?
gue punya temen kantor dulu namanya henry luk juga
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
, selanjutnya
indexnya perlu di lookup ke arraynya untuk mengetahui bilangan sesungguhnya.
--- On Mon, 6/9/08, Frans Thamura lt;[EMAIL PROTECTED]gt; wrote:
From: Frans Thamura lt;[EMAIL PROTECTED]gt;
Subject: Re: [JUG-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com
Date: Monday, June 9, 2008
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
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
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
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
searchnya kira2 = O(log n)
regards,
yohan
--- On Sat, 6/7/08, Felix Halim [EMAIL PROTECTED]felix.halim%40gmail.com
wrote:
From: Felix Halim [EMAIL PROTECTED] felix.halim%40gmail.com
Subject: Re: [JUG-Indonesia] Kode menarik
To: jug-indonesia@yahoogroups.com jug-indonesia
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
) ... 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
.
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
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
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:
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]
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
Mesti banyak latian nih untuk tahun depan...
Aaarrrghhh... :(
--
Wilbert : IT UKDW 2006
Java Blog : http://wilbertjava.wordpress.com
YM : inherit_c
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
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
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
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
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
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).
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
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
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
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.
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
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
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
Nope... itu bukan inner loop ;)
On Fri, Jun 6, 2008 at 6:57 PM, Jecki Sumargo [EMAIL PROTECTED] wrote:
On Fri, Jun 6, 2008 at 3:16 PM, naray citra [EMAIL
PROTECTED]naray_citra%40yahoo.com
wrote:
Gw dapet cuplikan kode menarik neh, untuk share aja, sapa tau ada yang
butuh
:D
sumber :
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
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
59 matches
Mail list logo
