Jonathan Irvin Gunawan

Malam ini, 29 April 2012, gw baru saja beres mengikuti kompetisi tahunan PCS (Programming Competition Session) 2012, yang merupakan acara dari JOINTS 2012 yang diselenggarakan oleh Universitas Gajah Mada (UGM) Jogjakarta.

Hasil sangat memuaskan, gw berhasil meraih nilai (500/500) dari 5 soal yang tersedia, alias full score Gw meraih peringkat pertama.

Juara 2 diraih oleh SMAN 8 Yogyakarta, yang gw kenal ada Cakra Wishnu Wardhana (temen pelatnas TOKI 2011 dan 2012) disana, anggota tim yang lainnya gw ga kenal. Mereka dapet nilai 446. Ada satu soal yang dapet 50, dan satu soal lagi dapet 96 (mungkin bug kecil), sisanya 100.

Juara 3 diraih oleh single fighter dari SMAN 2 Purwokerto, teman yang gw udah kenal sejak 2006, Nathan Azaria (temen pelatnas TOKI 2012). Dia ngebug di suatu soal, sehinggga cuma dapet 15 di soal tersebut. Total nilainya 415.

Juara 4 diraih oleh SBBS, Alfan Nur Fauzan (temen pelatnas 2011 dan 2012, sesama anggota REPEAT 2010) dan Erwin Eko Wibowo dengan total nilai 361.

Cerita sedikit tentang suasana penutupan, kira-kira pukul 16.00 lebih, pengumuman dibacakan mulai dari peringkat keempat.

Gw + Zaky + Nathan duduk jejer bertiga pas penutupan ini (gw duduk ditengah). Kita bertiga tegang parah. Peringkat ketiga dibacakan, Nathan mulai gak tegang. Entah dia puas atau nggak. Peringkat kedua dibacakan, gw + Zaky semakin tegang. Ini berarti gw atau zaky atau dua-duanya ga dapet 4 besar. Menuju pengumuman 1st place, dibacain dulu skornya 500. Dan akhirnya diumumin ternyata gw yang dapet 1st. Yay!!!!!

Ga nyangka banget gw bisa bebas bug (at least submission terakhir gw untuk tiap soal) pada kontes kali ini. Gw sih udah testing abis2an, tapi yang T (soal shortest path) itu ga nyangka bisa bebas bug, berhubung ngetestingnya agak susah. Oke berhubung gw dapet full score, gw bakal coba bahas soal2 ini berdasarkan algo gw yang gw gunakan pas kontes (walaupun ini mungkin ga solusi optimal).

(bentar, pembahasannya nyusul aja dah :p gw baru nulis nama algonya aja :p)

J – Apple and Banana (Ariza Ramadhita, 20??)

DP Coin Change

O – Kandang Wedhus Papat (KWP) (Basith Zainurrohman, 20??)

Kombinatorik.

I – Martabak Pak Blangkon (Riza Oktavian, 20??)

Simulasi aja

N – Tak Sederhana (Basith Zainurrohman, 20??)

Euler’s totient function

T – Ulang Tahun (Bagus Seto Wiguno, 20??)

Dijkstra

Wait, ini bukan berarti April 2012 TOKI OpenContest di organize gw. Gw udah ngewrite buat Maret 2012, masa ngewrite 2 bulan berturut-turut. Kontes kali ini diwrite oleh William Gozali (IOI 2011).

Tulisan ini dibuat sejam (51 menit tepatnya) setelah kontes mulai. Gw sempet ngewrite ini karena pada saat itu gw udah full score (nilai 300). Tepatnya pada menit ke-41, gw ngesubmit soal terakhir gw (soal yang lain udah 100) dan mendapatkan nilai 100 pada Nilai Resmi (di token). Gw langsung nanya Gozali, katanya gw Pertamax, Asekkkk!!! Jadi bingung itu dua dewa Nathan Azaria + Ahmad Zaky kemana. Katanya sih dia masih 0 (belum ikutan mungkin)

Oke gw bakal coba bahas soal-soalnya secara singkat disini. Ingat bahwa ini bukan editorial resmi, jadi gw nulis pendek aja. Editorial resmi itu tanggung jawab writer :p For obvious reason, gw akan publish ini setelah kontes usai.

Oke, mari kita lihat soal-soalnya.

1. Hiasan Matriks (William Gozali, katanya sih 2012)

Untuk subtask 1 dan 2 bisa diperoleh dengan bruteforce biasa, kompleksitas O(N^2 x M^2). O(N^2) untuk bruteforce lokasi matriks yang dipilih, O(M^2) untuk ngitung jumlahnya. Obvious.

Untuk subtask berikutnya, gw pakai algo O(N ^ 2 x M). O(N ^ 2) nya masih sama, tapi ngitung jumlahnya bisa O(M). Caranya, looping tiap baris, tapi ngitung jumlah angka pada baris tersebut menggunakan prefix sum, sehingga bisa O(1).

2. Pengurutan Buram (William Gozali, katanya sih 2012)

Ga kepikir algo lain selain algo benernya. Tinggal catet isi tiap data, index ke-i itu isinya apa, dan bilangan ke-i posisinya ada dimana.

Looping dari i = 1 sampai N, kalau i tidak pada posisinya, tukar bilangan ke-i dan ke-(posisi dimana i berada). Udah gitu doang. O(N).

3. Telat Bangun (William Gozali, katanya sih 2011)

Ingat ini bukan editorial resmi, gw ga bakal nulis proofing algo greedy gw :p

Greedynya, untuk setiap kemunculan ruangan i yang ke-j (1 <= i <= K) (1 <= j <= N), maka ruangan tersebut akan digunakan untuk orang ke-j.

Ya sudah, kita bisa list semua posisi ruangan ada dimana. Contoh sample case 1

Nomor ruangan : 1 2 1 1 2 3 3 2 3

Index                    : 1 2 3 4 5 6 7 8 9

Ruangan 1 : Orang pertama : 1, orang kedua : 3, orang ketiga : 4

Ruangan 2 : Orang pertama : 2, orang kedua : 5, orang ketiga : 8

Ruangan 3 : Orang pertama : 6, orang kedua : 7, orang ketiga : 9

Tinggal cek untuk setiap orang, apakah nomor index tiap ruangannya strictly increasing atau tidak. Kompleksitas O(N*K).

Timeline:

19:00 – gw mulai buka soal

19:12 – submit soal pertama, Hiasan Matriks dan 100 (nilai resmi)

19:30 – submit soal Telat Bangun dan 100 (nilai resmi)

19:41 – submit soal Pengurutan Bilangan dan 100 (nilai resmi) sekaligus mengakhiri perjuangan di April 2012 TOKI OpenContest

19:51 – tulisan ini mulai dibuat

20:12 – tulisan ini selesai dibuat

Little Stats :

(submissions with token / submissions)

(3/3) total submissions

(3/3) AC submissions

(0/0) TLE submission

(0/0) WA submission

(0/0) RTE submission

(0/0) other verdict submission

Note : Another one-shoot perfect score contest for me Yay!!!!!! ))))

Sampai jumpa di Mei 2012 TOKI Open Contest . Mudah-mudahan gw bisa nulis ‘editorial’ (editorial resmi bakal ditulis writer, yang sampai sekarang identitas writer Mei belum diketahui) buat Mei 2012 TOKI OpenContest. Kalau gw ga bisa, pasti salah satu dari dewa Nathan + Zaky bisa bikin editorialnya kok :p

Oke gw bakal bahas secara singkat soal-soalnya disini. Pembahasan ini cukup singkat, jadi kalau ada yang kurang ngerti, jangan ragu-ragu untuk nanya, bisa comment di post ini, atau kirim e-mail ke gw

Hasil Maret TOKI OpenContest bisa dilihat disini

Soal sudah diupload di “Bundel Soal”. Klik disini

1. Menghitung Game (Jonathan Irvin Gunawan,2012)

Risan bilang ini soal paling gampang di kontes kali ini. Beliau bilang ini soal bonus buat kontesnya. Intinya kan kalau di papan ada N batu, kita bisa sisakan N/X batu di papan, dimana X adalah faktor prima dari N (N juga termasuk X). Ya sudah, tinggal hitung jumlah pangkat faktor prima dari X.

Asumsikan jumlah pangkat faktor prima dari N adalah M. Jika M ganjil, maka Anda pemain pertama jelas bisa memenangkan permainan. Sebaliknya jika M genap, pemain pertama terpaksa menyerah. Untuk M ganjil, anda hanya cukup mencari faktor prima terkecilnya.

Kompleksitas O(sqrt(N))

15 peserta mendapatkan Accepted untuk soal ini.

2. Menghitung Nilai (Jonathan Irvin Gunawan,2012)

Berbeda dengan Risan, writer menganggap ini soal bonusnya. Terus terang, ketika soal ini diketik awalnya cuma cari maksimal aja (karena pas itu writer belum kepikir nilai minimalnya gimana :p). Entah dapat ide darimana tiba-tiba writer terpikir solusi untuk nilai minimalnya, ya sudah soalnya diganti jadi minimal dan maksimal :p

Mencari nilai maksimal itu mudah sekali. Untuk tiap pilihan (anggap pilihan ke-i), kita hanya bisa memperoleh nilai sebanyak min(JawabanBenar[i],JawabanAnda[i]).

Maka, nilai maksimal dirumuskan jumlah semua minimal dari jawaban benar untuk pilihan ke-i, dan jawaban anda untuk pilihan ke-i.

Nilai minimal bisa diperoleh dari max(max(JawabanBenar[i] + JawabanAnda[i] – N),0)

Kompleksitas O(N)

15 peserta mendapatkan Accepted untuk soal ini

3. Menghitung Kata (Jonathan Irvin Gunawan,2012)

Ini adalah soal tersulit di kontes bulan ini. Hanya 6 submission yang mendapatkan verdict Accepted.

Subtask 1 dan 2 (1 <= N <= 20)

Kita bisa membruteforce segala kemungkinan string berisi ‘o’ dan ‘x’, dan tiap string yang kita peroleh, kita bisa cek apakah string tersebut berupa kata atau tidak. Pengecekan bisa me-looping dari 2,3,5,7,11,13,17,19. Kompleksitas tiap pengecekan O(N). Kompleksitas total O(2 ^ N x N).

Untuk mendapatkan nilai di subtask berikutnya, ada lemma yang harus diketahui.

Lemma : Diberikan string X. Bila untuk setiap substring dari X yang memiliki panjang 3 karakter, banyaknya ‘o’ tidak lebih sedikit dari ‘x’, maka X pasti sebuah kata.

Bukti : Jika untuk substring dengan panjang 3 karakter valid, maka substring dengan panjang 2 karakter pasti valid. Semua bilangan bulat positif lebih besar dari 1, dapat direpresentasikan dalam 2x + 3y (x dan y bilangan bulat). Sehingga, untuk semua bilangan prima lebih besar dari 3 pun pasti valid.

Asumsikan banyaknya kata yang bisa dibentuk dengan panjang N adalah f(N). Maka ada dua kemungkinan yang bisa dilakukan.

Jika kita pasang ‘o’ pada karakter pertama, maka karakter berikutnya bebas, ini akan menjadi permasalahan yang sama, namun lebih kecil, yaitu  f(N-1)

Jika kita pasang ‘x’ pada karakter pertama, maka dua karakter berikutnya harus ‘o’. Ini akan menjadi f(N-3)

Sehingga f(N) bisa dirumuskan f(N) = f(N-1) + f(N-3). Dengan basis f(0) = 1, f(1) = 2, dan f(2) = 3

Subtask 3 dan 4 (1 <= N <= 1 000 000)

Untuk mendapatkan subtask ini, Anda bisa menggunakan Dynamic Programming. Anda bisa iterasi dari 3..N.

Subtask 5 dan 6 (1 <= N <= 1 000 000 000 000)

Untuk subtask ini, kita harus menggunakan perpangkatan matriks.

Perhatikan perkalian matriks ini :

Perkalian matriks tersebut akan menghasilkan

(f(n+1)  f(n+2)  f(n) + f(n+2)) = (f(n+1)  f(n+2)  f(n+3))

Jika matriks ini kita kalikan sekali lagi, kita akan mendapatkan

(f(n+2)  f(n+3)  f(n+4))

Sehingga, bisa dirumuskan

Mencari perpangkatan matriks bisa menggunakan pangkat cepat dalam O(lg N). Total kompleksitas O(3^3 x log N)

6 peserta mendapatkan Accepted untuk soal ini

4. Menghitung Belok (Jonathan Irvin Gunawan,2011)

19.00 : Kontes dimulai

19.10 : Belum ada submission -.-

19.15 : Masih belum ada submission -.-

19.19 : Submission pertama datang dari Cakra Wishnu Wardhana (kazu) untuk soal ‘Menghitung Belok’ dan AC (100). Pada menit yang sama Teddy Budiono Hermawan (DeimonDB) mendapat nilai 12 pada soal ‘Menghitung Game’

19.26 : AC (100) pertama untuk soal Menghitung Game jatuh kepada Ammar Fathin Sabili (athin)

19.27 : AC(100) pertama untuk soal Menghitung Nilai, Fendy Kosnatha (seraph)

19.35 : Teddy Budiono Hermawan (DeimonDB) re-submit soal Menghitung Game menjadi AC (100), langsung naik ke peringkat 1 bersama (seraph),(kazu),(athin).

19.42 : Fendy Kosnatha (seraph) mendapatkan AC (100) pada soal Menghitung Game. Menduduki peringkat 1 sementara dengan nilai 200.

20.02 : Satu jam kontes berlalu. Peringkat satu diduduki oleh Fendy Kosnatha (seraph) dengan 200 poin. Peringkat dua diduduki oleh (athin) dengan 112 poin. Terdapat 9 orang di peringkat ketiga dengan nilai 100.

20.06 : AC pertama untuk soal tersulit, Menghitung Kata dari Cakra Wishnu Wardhana (kazu). Menyusul Fendy Kosnatha (seraph) di peringkat pertama dengan nilai 200.

20.28 : Cakra Wishnu Wardhana (kazu) mendapatkan AC (100) untuk soal Menghitung Nilai, sekaligus menduduki peringkat pertama dengan nilai 300

20.30 : Kontes telah berlalu satu setengah jam (setengah lamanya kontes). Peringkat pertama diduduki Cakra (kazu), peringkat kedua diduduki Ammar (athin) dengan nilai 212, dan terdapat 4 peserta menduduki peringkat ketiga dengan nilai 200.

20.45 : Submission aneh muncul. Mendapatkan nilai 0 pada testcase sample, tapi mendapatkan AC pada testcase asli. Writer pun terkejut langsung mengambil tindakan broadcast pengumuman. Sampai tulisan ini dibuat, writer tidak tahu mengapa masalah ini timbul. -.-

20.48 : Badak Liar (badakliar) mendapatkan AC untuk soal Menghitung Game, sekaligus meengakhiri perjuangannya di TOKI OpenContest Maret 2012 dengan nilai 400 (full score).

20.57 : Juara bertahan TOKI OpenContest Februari 2012, Ahmad Zaky mengirim message FB kepada writer bahwa ia baru mulai mengerjakan soal. Hmmmm. Bisakah ia mengejar ketertinggalan hanya dalam sejam?

21.04 : Dua jam kontes, peringkat 1 diduduki oleh Badak Liar (badakliar), Alfan Nur Fauzan (bariqlana), dan Cakra Wishnu (kazu) dengan nilai 400 (full score).

21.26 : Belum ada yang full score lagi, writer mulai bosan. Beberapa situs selain tokilearning.org yang tidak penting mulai dibuka. 9gag, dll. Untung gak ada klarifikasi :p

21.32 : Kondisi scoreboard masih sama. 3 peringkat teratas diduduki oleh (badakliar), (bariqlana), dan (kazu) dengan full score. Diikuti Fariskhi Vidyan (FVD) dengan nilai 366. 300 + 66 poin di soal Menghitung Belok.

21.37 : Juara bertahan, Ahmad Zaky berhasil memperoleh nilai 300 dalam waktu 40 menit. Bisakah dia menyelesaikan soal yang tersisa (Menghitung Kata) dalam 23 menit tersisa?

21.51 : 9 menit menuju usai kontes, entah udah pasrah atau apa, writer diberi klarifikasi aneh : “Apakah Jonathan Irvin Gunawan benar-benar ganteng?”. Padahal kan jawabannya udah jelas iya -.-

21.53 : Ahmad Zaky mendapat nilai 47 pada soal terakhirnya, Menghitung Kata

21.58 : Menit-menit terakhir menjelang akhir kontes. Peringkat 1 masih diduduki oleh (badakliar), (bariqlana), dan (kazu)

Sudah sejak lama gw mau ngewrite soal buat Open Contest, tapi baru kesampaian sekarang. Bulan Desember yang lalu gw ngomong ke kak Adin, katanya Jan-Feb udah penuh, ya udah bersabar sampai Maret 2012. Lumayan juga, ada waktu sekitar 3 bulan untuk ngewrite soal.

Event March 2012 TOKI Open Contest on Facebook

March 2012 TOKI Open Contest on tokilearning.org

Oke deh, post ini bakal gw update lagi setelah kontes (editorial dan kejadian seru yang bisa diceritakan selama kontes )

Ini lanjutan dari postingan “Ganti HP“. Akhirnya gw memutuskan bahwa identitas HP baru gw bisa diketahui.

Beberapa foto “unboxing” my new phone

My New Phone

iPhone 4 16 GB Black – Apple

Spesifikasi

(kebanyakan info diambil dari Apple.com)

1. Size and Weight

2. Seperti yang bisa dilihat dari fisik luar, gw pakai iPhone 4. Itu berarti gw bisa menggunakan FaceTime. buat yang pakai Mac atau iPhone 4 (atau iPhone 4S) atau iPod 4th generation, kalau kalian mau FaceTime ama gw (kangen ama muka gw ) silahkan aja. Bisa ke nomor HP gw atau Apple ID gw : jonathan.irvin@yahoo.com

3. Seperti yang bisa dilihat dari ‘Welcome Screen’, I’m using iOS 5. Which means, I’m using iMessage. Silahkan iMessage gw pakai Apple ID gw : jonathan.irvin@yahoo.com

Lima hari yang lalu gw baru aja ganti HP. Jadi gw udah ga pake BlackBerry lagi. PIN 21B4A5E9 itu bukan punya gw lagi, jadi jangan pernah kirim message kesitu :p

Identitas HP baru gw masih dirahasiakan , tapi beberapa isi dari post ini mungkin memberi petunjuk apa HP baru gw.

Gw ganti hp karena beberapa alasan :

1. BlackBerry Gemini gw ga 3G (petunjuk : HP baru gw 3G)

2. Kamera BlackBerry Gemini busuk, cuma 2MP (petunjuk : HP baru gw kameranya >2MP)

3. BlackBerry boros batere

Udah lah itu aja, ga usah panjang-panjang. Post tentang hp baru gw (termasuk unboxing, dsb.) akan gw post kalau identitasnya sudah bisa disebarluaskan

Pertama kali melihat judul, mungkin banyak yang heran. Apa maksudnya kompetisi pertama? Bukankah gw sudah sering ikut kompetisi?

Well, post ini ga ada hubungannya ama programming. Yang gw maksud kompetisi pertama itu kompetisi rubik :p

Sebulan yang lalu, 26 – 27 November 2011, gw baru aja ikut kompetisi rubik di Bandung, tepatnya di Balubur Town Square. Kompetisinya bernama “Bandung Dua Tujuh 2011″. Dan baru hari ini gw sempet nulis storynya. Maklum, “sibuk” banget sih (sok sibuk :p)

Berikut storynya

Hari Pertama

Gw cuma ikut dua event, Rubik’s Clock dan Rubik’s Cube (3x3x3). Rubik’s Cube itu jadwalnya di hari kedua (First, Second, Final Round semuanya di hari kedua). Terus Rubik’s Clock itu jadwalnya hari pertama, tapi sore. Jadi dari pagi sampai sore gw ga ngapa-ngapain

Inget kata temen gw, Nathan Azaria : “ngejudge seru loh vin”. Yaudah dari pagi sampai sore gw banyak banget ngejudge :p. Terutama si Vincent, kan tiap dia main direkamin, enak ngejudge dia pasti masuk video.

Ini video Average 4x4x4 Vincent, tuh kan judgenya gw semua :p

Rubik’s Clock

Sore hari, tibalah saatnya event Rubik’s Clock. Gw lumayan gugup pas di panggung (pas main), baru kali ini main rubik dipanggung ginian :p Singkat kata, hasil lumayan baik mengingat gw baru belajar 3 minggu sebelum kompetisi, diajarin ama Nathan pas Pelatnas 1 TOKI 2012 :p

Rubik’s Clock : (15.06)   11.90   (9.90)   12.21   13.75   (Ao5 = 12.62) rank #6

Gak nyangka bisa dapet sub 10 single di kompetisi ini, jadi pas dapet sub 10 seneng banget, sampai minta difotoin :p

Hari Kedua

Hari kedua, gw ikut event Rubik’s Cube. Pertama first round.

Rubik’s Cube – First Round

Solve pertama gw fail banget, dapet 31.18. WTF! padahal pas kompetisi ini gw udah sub30, dan gw targetin bisa sub27. eh malah dapet 31 – -a. Ya udah lah, paling jadi worst time dan ga counting (udah tahu kan aturan average rubik itu main lima kali, buang worst dan best time, jumlahin sisanya, bagi 3)

Solve kedua, gw harap bisa sub27. Ternyata gw main dengan memikirkan solve pertama yang fail tadi, akibatnya malah nervous dan tambah fail. Dapet 32.97. ASTAGA ITU APAAN? gw udah dapet counting 31.18 deh (gara-gara dapet yang worse, pasti 31nya kehitung, istilahnya counting).

Di solve-solve berikutnya untung gw masih bisa bangkit. Dengan melupakan dua solve pertama dan mengganti strategi, di solve ketiga gw dapet 21.06. Oke, gw mulai semangat lagi mengejar Avg sub 27

Ets jangan salah, mengganti strategi itu bukan mengganti method yang gw gunakan. Sebenarnya bukan strategi juga sih, tapi yang gw ganti itu :

1. HP gw masukin tas, dua solve pertama HP gw masukin kantong celana, dan itu cukup nganggu.

2. Berdiri, dua solve pertama gw duduk.

3. Lepas jaket (yang coklat itu loh, jaket khas gw :p). Lengan panjang nganggu buat main rubik’s cube.

Solve keempat dan kelima menggunakan “strategi” yang gw gunakan di solve ketiga, hasilnya 26.68   28.59.

Rubik’s Cube First Round : 31.18   (32.97)   (21.06)   26.68   28.59   = (Ao5 = 28.82) Rank #22.

Tibalah pengumuman siapa yang berhak menuju Second Round. Diumumkan yang lolos ke Second Round ada 21. WTF gw ga hoki banget, pas di perbatasan ga lolos (gw rank #22)

Walaupun gw ga ada kompetisi lagi, gw tetap di tempat kompetisi. Berhubung ga ada kerjaan hari itu (ngoding juga males :p) ya udah gw di tempat sampai kompetisi berakhir aja.

Rubik’s Cube – Second Round

Tiba Second Round Rubik’s Cube. Dipanggil 21 orang yang lolos First Round. eh hoki parah, satu orang dipanggil ga datang, entah kemana. Akhirnya delegate memutuskan mengambil Rank #22 (gw). YIPPPIE, gw masih ada kesempatan memperbaiki WCA Profile gw di Rubik’s Cube yang ancur :p

Di second round entah kenapa gw beda banget dengan pas di first round. Udah hoki masuk second round, di second round juga hoki. Dua kali SKIP PLL . Hoki parah. Sampai pas itu judgenya nanya “skip lagi ya?” :p. Tentu saja di second round ini gw berdiri, HP masukin tas, ga pakai jaket.

(Note : tapi walaupun SKIP PLL, gw masih 2-Look-OLL sih, jadi sama aja -___-)

Rubik’s Cube Second Round : (26.44)   21.77   22.38   (20.66)   22.59 = (Ao5 = 22.25) Rank #20

Diambil 12 untuk ke Final Round. Ya udah, emang dari awal ga ada keinginan untuk masuk Final sih. masuk ke second roundnya aja udah hoki gitu. Gugur di Second Round, sampai sore gw ga ngapa”in, selain ngejudge :p

Akhir

Seperti kompetisi biasanya, tiap event diumumkan juara 1-3 naik ke podium. Gw ga dapet apa-apa, clock gw cuma rank #6, rubik’s cube ga masuk final. Ya emang ini kompetisi pertama, itu udah lebih dari cukup buat gw. Emang dari awal gw ikut ini cuma supaya gw punya WCA ID sih.

Beberapa hari kemudian jadilah WCA ID gw, dengan ID 2011GUNA02