Goal Setting 2010

Happy New Year 2010 !

Tahun 2009 baru saja berlalu, ngga terasa waktu berjalan begitu cepat, sudah 5 tahun berlalu sejak saya pertama kali mengenal ACM dan berlatih ilmu2 coding & algoritma. Di tahun 2009 yang lalu, saya tidak mendapatkan suatu ‘pencapaian’ sama sekali, karena saya tidak punya target apa2 pada waktu awal tahun lalu. Supaya hasil tahun ini jauh lebih baik dari tahun lalu, maka saya menetapkan 3 goal berikut untuk tahun 2010 ini.

1. Menulis buku “Panduan Kompetisi Algoritma”, buku ini akan berisi semua ‘jutsu’ yang sudah saya pelajari selama 5 tahun :p.

2. Rating merah TopCoder, saat ini rating saya 15xx, masih kurang 700 pts lagi. Rating merah TopCoder saya yakin akan memberikan ‘nilai lebih’ untuk buku yang saya tulis :p.

3. Solve 100 Soal di SPOJ, saat ini saya sudah Solve 60 soal. Online Judge ini berisi banyak soal2 medium dan hard dari ACM/ICPC. Beberapa soal di SPOJ akan saya gunakan sebagai materi di buku saya.

Review Harta’s Challenge

Kemaren malam saya mengikuti Harta’s Challenge di Z-Trening. Saya sangat senang sekali dengan hasil kompetisi ini karena saya berhasil melakukan NoMoreAC (No More Accepted) alias sapu bersih semua soal . Berikut adalah hasil ranking sampai 10 besar di Harta’s Challenge.

#	User	A	B	C	Total	Time
1.	algoboy	100	100	100	300	1:49 (3)
2.	stjepang	100	100	100	300	1:49 (9)
3.	thocevar	100	100	100	300	3:00 (3)
4.	syntax_error	100	92	100	292	3:34 (8)
5.	pr0ton	40	88	100	228	0:53 (4)
6.	AhmedKamel	40	88	100	228	3:55 (3)
7.	Adamka	30	88	100	218	2:32 (8)
8.	Amtrix	10	100	100	210	3:58 (6)
9.	carlosjoa	-	100	100	200	1:16 (3)
10.	hosam_samy	0	100	100	200	3:33 (7)

Soal-soal yang ada di Harta’s Challenge menurut saya cukup menarik, tapi sayang jumlah soalnya hanya ada 3.

Berikut pembahasan dari saya untuk masing2 soal:

Weekly Solving (12/12/2009 – 19/12/2009)

Minggu ini saya kembali berlatih di Online Judge untuk meningkatkan kemampuan problem solving. Berikut adalah soal-soal yang saya solve dalam minggu ini:

TJU – 1754 – Circular Area ==> Easy Math (Trigonometry), saya solve soal ini karena ada seseorang di BINUS yang  menantang saya untuk mengerjakan soal ini wkwkwkw =)). Dia terlalu meremehkan kemampuan math saya :p.

TJU – 3312 – Traversal ==> Easy DP + Advanced Data Structure. Untuk soal ini, karena menggunakan jurus super, saya berhasil jadi rank 1:  http://acm.tju.edu.cn/toj/problem_stat.php?pid=3312

1

2009-12-15 13:16:43

26 / 46

C++

1.7K

0′00.20″

3836K

Timotius Sakti

TJU – 3313 – Calculation ==> Number Theory. Soal ini sangat sulit menurut saya, sebaiknya bagi yang blum tau jurus2 ini:  Euler’s Theory, Chinese Remainder Theory, Integer Factorization, Euler’s Phi Function, Fast Pow. Jangan coba2 mengerjakan soal ini :p.

TJU – 3314 – Cow Sorting ==> Advanced Data Structure. Lagi2 karena menggunakan jurus super, saya berhasil jadi rank 1 :

1

2009-12-16 21:27:59

5 / 10

C++

1.0K

0′00.07″

2960K

Timotius Sakti

TJU – 3320 – Coins ==> Easy DP.

TJU – 3354 – Continuous Digit ==> DP Digit + Binary Search.

TJU – 3460 – A Coin Game ==> Medium DP. Supaya ngga TLE, kita musti reduce kompleksitas dari O(n^3) menjadi O(n^2).

Weekly Solving 02/10/2009 – 08/11/2009)

SPOJ – MARBLES ==> Combinatoric.

SPOJ – ELDORADO ==> Dynamic Programming.

SPOJ – CZ_PROB3 ==> Probability.

SPOJ – TOE2 ==> BFS.

Minggu ini soal yg saya solve sedikit, karena saya sibuk mengerjakan proyek dan tugas2 dari kantor .

Weekly Solving (26/10/2009 – 01/11/2009)

SPOJ – JEDNAKOST => Dynamic Programming.

SPOJ – MBIPALIN => Dynamic Programming.

SPOJ – PARTPALI => Dynamic Programming.

SPOJ – MARBLES => Combinatoric, Sieve.

SPOJ – STREDUCE => Dynamic Programming.

SPOJ – SIZECON => Ad Hoc.

Saya ingin memperkenalkan 1 tools bagus utk latihan di SPOJ : http://vnoi.info/index.php?option=com_voj&task=classify&site=spoj. Tool ini akan membantu kita untuk mencari problem di SPOJ berdasarkan category problem tersebut. Makanya kalo diperhatikan soal2 yang saya solve di SPOJ kebanyakan adalah Dynamic Programming. Saya dapat mencari dengan mudah soal2 DP menggunakan tools tersebut .

Minggu ini saya banyak berlatih di Sphere Online Judge. Menurut saya OJ ini sangat bagus untuk latihan berpikir, karena soal2 yang ada disini kebanyakan adalah soal2 medium sampai very hard. Selain itu testcase disini sangat bagus, kalo algo kita ngga betul2 bener bakalan dapet Wrong Answer. Contohnya soal STREDUCE itu pake algo mendekati benar (hoki2an) saya bisa AC di TJU Online Judge dan PKU Online Judge. Tapi kalo disini dapet WA, musti rubah jadi algo yg betul2 benar baru bisa AC. Selain itu soal MBIPALIN musti AC sampe “berdarah-darah” pake algo bagus tapi kalo implementasinya jelek bisa kena TLE, hal itu yg saya dapatkan waktu ngerjain MBIPALIN.

Weekly Solving (19/10/2009 – 26/10/2009)

SPOJ – DAGCNT2 => DAG, DFS/BFS.

UVA 538 => Greedy.

Sabtu kemaren saya sempet ikutan COCI dan hampir saja full score :p, tapi sayang soal dobra ngebug dan soal aladin tidak sempat saya submit .

Score	Name	note	domino	dobra	mali	genijalac	aladin
314	Timotius Sakti	30	50	14	100	120	0

note => ad hoc

domino => simple math

dobra => dynamic programming

mali => greedy

genijalac => finding cycle + math

aladin => segment tree

Additional News:

ACM/ICPC Jakarta yang diselenggarakan di BINUS University kemaren sangat seru, team Dongskar Pedongi dari ITB yang dimotori oleh Irvan Jahja (peraih medali emas IOI 2008) hampir saja menjadi juara 1, tapi sayang mereka disalip 2 team lain (1 china, 1 taiwan) pada 1 jam terakhir sehingga mereka harus puas dengan peringkat 3. Sementara itu team tuan rumah Aeon yang diperkuat oleh Eko Wibowo, Eko Mirhard dan Ricky Winata gagal meraih top 5.

Final Ranklist : http://competition.binus.ac.id/icpc2009/result/final.html

Problem Set : http://competition.binus.ac.id/icpc2009/icpc09jak-probs-publish.pdf

Weekly Solving (12/10/2009 – 18/10/2009)

Supaya blog ini terus terupdate, mulai sekarang saya memutuskan untuk posting nama problem2 yang saya solve tiap minggu. Siapa tau ada yg tertarik mengikuti jejak saya solve problem2 tersebut .

SPOJ – PAINTBLK => DP, Combinatoric.

SPOJ – MUL => Fast Multiply BigInteger, Karatsuba Algorithm.

UVA – 11610 – Reverse Prime => Segment Array, Segment Tree.

TJU – 3446 – Money Matters => DFS/BFS.

TJU – 3445 – Soda Surpler => Ad Hoc, Simple Math.

Additional News:

Tiga hari lagi yaitu Rabu, 21 Oktober 2009 bertempat di BINUS University akan diadakan perlombaan ACM/ICPC tingkat Asia. Ini adalah yang kedua kalinya BINUS menjadi host.

Baru2 ini saya menemukan suatu website yang bagus untuk baca2 artikel tentang algoritma: http://programmersdream.com/

Soda SurplerS

Sudah lama ngga update blog

Sudah lama sekali saya ngga update blog ini. Sejak oktober 2008 saya sudah ngga maen algoritma lagi. Saya sudah mulai bekerja menjadi Java Programmer. Minggu2 ini saya mengalami masalah yang berat sekali dalam hidup saya. Saya menemukan bahwa saya menderita kelainan obsessive compulsive disorder. Kelainan ini mengakibatkan produktivitas coding dan waktu saya terbuang sia2.

Panduan ACM-ICPC Programming Contest (part II)

Tips lolos ke World Final

Untuk lolos ke World Final adalah hal yang sulit, karena selain kita harus berlatih dengan giat setiap hari, kita juga perlu unsur keberuntungan.  Pemilihan tempat regional, soal2 yang akan muncul, team2 lawan yang akan dihadapi juga merupakan faktor apakah kita bisa lolos menuju World Final.

Saya menyarankan untuk tidak mengikuti regional ditempat2 berikut: Beijing, Chengdu, Hangzhou, Harbin dan Hefei .. Mengapa ? semua tempat yang saya sebutkan berlokasi di Cina, itu artinya banyak team2 dari Cina yang akan mengikuti kontes tersebut. Lihat hasil Olimpiade Beijing 2008 dan hasil IOI 2008 , Cina begitu mendominasi hasil pertandingan, begitupun di ACM-ICPC, karena itu akan sangat sulit untuk bisa mendapat tiket World Final dari Regional Cina.

Tiket World Final akan diberikan kepada juara 1 (100% pasti) dan juara 2(tidak 100% pasti). Juara 3,4 dan 5 juga berpeluang untuk bisa masuk World Final kalo beruntung (Wildcard). Pada tahun lalu team kami(YoiMon) berhasil mendapatkan tiket untuk pergi ke World Final, disitu kami mendapat rank 4, padahal kalo dilihat ada banyak sekali team diatas kami. Kami beruntung karena beberapa team diatas kami berasal dari universitas yang sama, jadinya rank kami naik . Ini hasil perlombaannya : Hasil ACM Regional Taipei 2007

Tiket World Final yang saya bicarakan disini bukanlah tiket pesawat untuk pergi ke World Final. Kalo saya tidak salah untuk tiket pesawat menuju World Final itu ditanggung oleh pihak universitas. Pihak sponsor utama ACM ICPC yaitu IBM, hanya menanggung biaya hotel + makan selama mengikuti acara World Final.

Ketika berhasil masuk World Final

Ketika berhasil masuk world final, itu adalah suatu peristiwa yang sangat mengembirakan . Kita bertanding di level teratas dan akan bertemu dengan mahasiswa-mahasiswa (mahasiswinya jarang :p) cerdas di bidang computer science dari seluruh belahan dunia. Selain itu di World Final juga banyak  acara-acara yang menarik (dari makan2 sampe jalan2), berbeda dengan Regional yang hanya 2 hari saja, World Final akan berlangsung selama 4 hari.

Kira2 susunan acaranya gini secara garis besar :
Hari 1: pendaftaran team (ambil kaos dsb) + makan malam (buffet) + cybercafe.
Hari 2: seminar dari IBM + jalan2 + makan buffet (pagi,siang,malam) + cybercafe.
Hari 3: pesta pembukaan + practice session + jalan2 + makan buffet (pagi,siang,malam) + cybercafe.
Hari 4: acara lomba + pesta penutupan + “surprise” + makan buffet (pagi,siang,malam).

Cybercafe-nya sangat menarik , selain kita bisa internet gratis, disana juga ada game2 yg menarik (DDR, Wii Tenis, dll..) , disana kita bisa ngobrol2 sama peserta yg lain. Pada World Final yang kemaren, saya bertemu dengan Petr Mitrichev (rank 1 topcoder) dan kami bermain game bersama . Ternyata saya bisa menang juga lawan Petr kalo maen game :p (soalnya kalo SRM hampir ngga mungkin menang).

Demikian panduan ini saya tulis, kalo ada yg salah mohon dimaafkan . Semoga bisa memberikan gambaran tentang perlombaan ACM ICPC bagi peserta yang baru ikutan.

Panduan ACM-ICPC Programming Contest (part I)

ACM-ICPC Programming Contest tahun ini akan segera dimulai, melalui post ini saya ingin membagi pengalaman saya mengikuti ACM-ICPC Programming Contest pada tahun-tahun sebelumnya.

Apa itu ACM-ICPC

ACM-ICPC Programming Contest adalah suatu ajang perlombaan yang mengadu kemampuan algoritma dan pemrograman mahasiswa untuk membuat program yang dapat menghasilkan output yang benar dari input yang diberikan oleh juri. Perlombaan ini dibagi menjadi 2 tingkat, yaitu Regional dan World Final.

Untuk bisa mengikuti perlombaan Regional harus merupakan perwakilan dari universitas. Universitas dapat mengirimkan sebanyak mungkin team untuk mengikuti Regional yang ada. Karena kita kuliah di Indonesia, maka kita dapat mengikuti Regional Asia, dimana pada tahun ini perlombaannya ada di :