[JUG-Indonesia] Re: Kode menarik
--- In jug-indonesia@yahoogroups.com, "Frans Thamura" <[EMAIL PROTECTED]> wrote: > > 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 > bro.. http://commons.apache.org/math/userguide/stat.html buat tugas Statistical Computing enak tuh... tinggal... array.getMeans() hehehehhehe :) Kiki Ahmadi jug-bonek
[JUG-Indonesia] Re: Kode menarik
ikutan ah, sepertinya rame :-D
code yang dibawah kayaknya belum ada yg bahas cara kerjanya.
(buat yang bingung aja):
OUTPUT[i]: output pada elemen ke-i (hasil perkalian semua A[] kecuali
A[i])
KIRI[i]: partial-multiplication dari A[1] s/d A[i] (maju)
KANAN[i]: partial-multiplication dari A[N] s/d A[i] (mundur)
contoh..
INPUT:[4, 3, 2, 1, 2]
KIRI:[4, 12, 24, 24, 48]
KANAN:[48, 12, 4, 2, 2]
maka...
OUTPUT[i] = KIRI[i-1] * KANAN[i+1]
baca: OUTPUT[i] adalah hasil kali semua elemen yang di kiri i, dengan
semua elemen yang di kanan i.
KIRI[] bisa dikomputasi dalam O(n) -> sekali looping
KANAN[] juga bisa dikomputasi dalam O(n) -> sekali looping juga.
setelah KIRI[] dan KANAN[] di pre-compute, maka OUTPUT[] juga bisa
diselesaikan dalam O(n) :-D
jadi total kompleksitasnya O(n)
pseudocode:
FOR i := 1 to n -> KIRI[i] = KIRI[i-1] * INPUT[i]
FOR i := n downto 1 -> KANAN[i] = KANAN[i+1] * INPUT[i]
FOR i := 1 to n -> OUTPUT[i] = KIRI[i-1] * KANAN[i+1]
Suhendry Effendy
--- In jug-indonesia@yahoogroups.com, 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)));
> }
> }
>
[JUG-Indonesia] Re: Kode menarik
boleh jelasin list of "turning point" nya itu gimana? kalau datanya saya bikin berinterpolasi besar/kecil gimana? 25 65 10 60 30 55 20 50 35 45 15 40 Suhendry Effendy --- In jug-indonesia@yahoogroups.com, "Feris Thia" <[EMAIL PROTECTED]> wrote: > > 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 >
[JUG-Indonesia] Re: Kode menarik
menarik sih menarik, tapi aku butuh waktu lammaaa utk mengertinya, sol --- In jug-indonesia@yahoogroups.com, "Felix Halim" <[EMAIL PROTECTED]> 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] Re: Kode menarik
Maka array TP pointnya (1 ascending, -1 descending) adalah sebagai berikut : idx = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 direction = 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1 Contoh yang diberikan benar-benar worst case ya ? naik turun melulu tiap index ? hehehe Regards, Feris 2008/6/9 Suhendry Effendy <[EMAIL PROTECTED]>: > boleh jelasin list of "turning point" nya itu gimana? > > kalau datanya saya bikin berinterpolasi besar/kecil gimana? > > 25 65 10 60 30 55 20 50 35 45 15 40 > > Suhendry Effendy > > > -- 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] Re: Kode menarik
Ups... sori, harusnya : idx = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 direction = 1, -1, 1, -1, 1, -1, 1, -1, 1, -1 2008/6/9 Feris Thia <[EMAIL PROTECTED]>: > Maka array TP pointnya (1 ascending, -1 descending) adalah sebagai berikut > : > > idx = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 > direction = 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1 > > Contoh yang diberikan benar-benar worst case ya ? naik turun melulu tiap > index ? hehehe > > Regards, > > Feris > > 2008/6/9 Suhendry Effendy <[EMAIL PROTECTED]>: > >> boleh jelasin list of "turning point" nya itu gimana? >> >> kalau datanya saya bikin berinterpolasi besar/kecil gimana? >> >> 25 65 10 60 30 55 20 50 35 45 15 40 >> >> Suhendry Effendy >> >> >> > > > > -- > 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 > -- 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] Re: Kode menarik
Wow... sama :p Tapi senang banget jago2 komputasi bisa nimbrung disini dan memberikan teknik2 aneh nan berguna. hehehe Salut.. salut .. ! Regards, Feris 2008/6/11 imam baihaqi <[EMAIL PROTECTED]>: > menarik sih menarik, tapi aku butuh waktu lammaaa utk mengertinya, sol > > --- In jug-indonesia@yahoogroups.com , > "Felix Halim" <[EMAIL PROTECTED]> > 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 > > > > > -- 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
