Wednesday, 31 December 2014

Akhir tahun 2014

Akhirnya tahun 2014 pun berakhir. Rasanya hampir sepanjang tahun ini saya memiliki kesibukan, bahkan di hari liburnya. Mulai dari awal tahun, saya mengurus berbagai hal yang berkaitan dengan TOKI, seperti rapat, menyusun panduan membuat soal, dan sebagainya. Kemudian masuk kuliah, sambil disibukkan dengan latihan untuk ACM-ICPC WF, organisasi, lalu selesai kuliah langsung pergi ke WF, pulang mengurus Pelatnas dan mulai magang, lalu izin untuk ke IOI 2014, pulang magang lagi, selesai magang bolos kuliah untuk OSN 2014, lalu masuk kuliah, lalu izin untuk ACM-ICPC Regional Bangkok, lalu masuk kuliah lagi, lalu izin untuk Gemastik, izin untuk ACM-ICPC Regional Jakarta, dan diakhiri dengan ujian.

Syukurlah dalam tahun 2014, dicapai beberapa hal:
  • Masuk ke WF ACM-ICPC 2014!
  • Menjadi anggota delegasi untuk IOI 2014, bukan sebagai peserta :)
  • Menjadi anggota panitia OSN 2014 yang sangat membuat saya nostalgia :)
  • Menjadi ketua kontingen UI untuk Gemastik, dan Tim UI berhasil menjadi juara umum untuk tahun kedua berturut-turut :)

Dalam hal blogging, saya memang masih belum memenuhi target yang baik. Sampai saat ini, baru terkumpul 24 tulisan pada tahun 2014. Namun, akhirnya saya berhasil menuliskan seluruh kisah perjalanan saya di TOKI, mulai dari OSK sampai IOI. Hal ini sudah saya wacanakan sejak seusai IOI, dan baru terlaksana tiga tahun kemudian :)) Oh ya, saya juga menuliskan berbagai pengalaman saya ketika WF ACM-ICPC 2014, IOI 2014, dan OSN 2014. Ketiga hal itu menjadi pengalaman paling berharga pada tahun 2014 bagi saya.

Dalam hal ICPC, kemungkinan untuk masuk ke WF memang kecil. Saya gagal pada Regional Bangkok, dan pada Regional Jakarta kalah dari Singapura, Korea, dan Vietnam, sehingga berada di peringkat empat. Cukup sedih jika nantinya tidak masuk WF, meskipun saya sudah berusaha sebaik mungkin. Namun, saya berharap pengalaman setim dengan Ammar dan Soko bisa membuat mereka lebih membara lagi untuk berjuang di Regional 2015.

Untuk tahun 2015, saya akan menghadapi berbagai tantangan di dunia nyata. Kuliah tinggal satu semester lagi, diisi dengan tugas akhir dan kerja sambilan. Setelah lulus, saya harus mulai bekerja juga. Banyak hal baru yang menanti, dan saya akan tetap berusaha untuk menjadi lebih baik lagi!

Foto oleh Pak Yugo

TOKI Open Contest: Desember 2014

Sudah lama sekali sejak saya menulis soal untuk TOKI Open Contest, mungkin sekitar tiga tahun lamanya. Bulan Oktober yang lalu, saya ditawarkan untuk menulis soal untuk TOKI Open Contest Desember dengan tema geometri. Solusi untuk semua soal di bawah ini bisa Anda unduh dari sini. Langsung saja saya bahas soalnya satu per satu.

Catatan: tulisan ini mengandung istilah dalam computational geometry, seperti vektor, cross product, convex hull, dan sebagainya. Anda diharapkan sudah memahaminya terlebih dahulu. Oh ya, ini juga menginspirasi saya untuk menulis tentang dasar-dasar dalam computational geometry. Kemungkinan besar akan saya tulis di kemudian hari.


Dua Gelang

Perhatikan setiap kemungkinan kasus yang ada, dan hubungkan dengan jarak antar titik pusat dan jari-jari lingkarannya.
Misalkan d menyatakan jarak antar titik pusat lingkaran, R1 menyatakan jari-jari lingkaran yang lebih besar, dan R2 menyatakan jari-jari lingkaran yang lainnya. Kemungkinan-kemungkinannya adalah:
  1. Kedua lingkaran saling lepas. Hubungannya adalah R1+R2 < d.
  2. Kedua lingkaran bertemu di satu titik, dan kedua lingkaran tidak saling mengandung (yang satu berada di dalam yang lainnya). Hubungannya adalah R1+R2 = d.
  3. Kedua lingkaran bertemu di dua titik. Hubungannya adalah R1+R2 > d.
  4. Kedua lingkaran bertemu di satu titik, dan lingkaran yang besar mengandung lingkaran yang kecil. Hubungannya adalah R1 = d+R2.
  5. Kedua lingkaran saling lepas, dan lingkaran yang besar mengandung lingkaran yang kecil. Hubungannya adalah R1 > d+R2.
  6. Kedua lingkaran bertemu di tak hingga banyaknya titik, artinya kedua lingkaran identik dan memiliki titik pusat yang sama. Hubungannya adalah R1 = R2 dan d = 0. Kasus ini sebenarnya bisa ditangani juga oleh hubungan pada kasus (4).

Saturday, 6 December 2014

Persistent Data Structure

Kali ini saya akan memperkenalkan suatu struktur data yang sangat menarik, yaitu persistent data structure. Struktur data ini sebenarnya adalah modifikasi dari struktur data yang sudah ada, seperti segment tree atau BST. Saya akan menerangkannya mulai dari permasalahan.

Permasalahan Motivasi

Diberikan sebuah array A berisi N bilangan. Indeks dari A dinomori dari 0 sampai N-1. Diberikan pula Q operasi yang bisa berupa:
  • Update x y, yang artinya laksanakan A[x] = y
  • Query x y z, yang artinya cari min(A[x], A[x+1], A[x+2], ..., A[y]) pada array A sebelum operasi update ke-z dilaksanakan

Nah lho, bagaimana jika N dan Q bisa sampai 100.000? Tidak mungkin kita menyimpan setiap versi dari array A kan?

Persistent Segment Tree

Seandainya setiap query dilaksanakan pada array A versi terakhir, maka kita bisa menerapkan struktur data segment tree seperti biasa.

Coba perhatikan versi pertama dari array A. Saya sebut versi ini sebagai "versi 0".

Jika dilakukan update pada A[5], didapatkan versi 1 dari array A. Perhatikan segmen-segmen yang di-update:

Saturday, 25 October 2014

Manipulasi Segmen pada BIT & Segment Tree

Kali ini saya akan berbagi suatu teknik yang lucu, yaitu mengoprek "jeroan" segment tree dan BIT. Kadang-kadang, dengan mengetahui struktur dalam suatu objek dan langsung memanipulasinya, kita bisa melakukan berbagai hal dengan lebih efisien. Misalnya kalau Anda paham struktur dalam televisi, mungkin Anda bisa mengatur supaya televisinya otomatis mati pada jam-jam tertentu.

Saya akan memberikan beberapa contoh yang umum.

Contoh umum

Misalkan diberikan soal:
Terdapat sebuah array A yang awalnya kosong dan N operasi, yang bisa berupa:
  1. tambah x, artinya tambahkan x ke dalam array A. Dijamin tidak nilai-nilai di dalam array A akan selalu unik
  2. tanya k, artinya cetak bilangan terkecil ke-k di dalam array A pada saat itu
Batasan:
  1. 1 ≤ N ≤ 100.000
  2. Pada setiap operasi tambah, 1 ≤ x ≤ N
  3. Pada setiap operasi tanya, 1 ≤ k ≤ N
Salah satu cara yang mungkin langsung terpikir adalah dengan BST. Namun BST relatif sulit untuk di-coding, lagipula tidak ada operasi menghapus. Oleh karena itu, marilah kita coba kerjakan dengan segment tree.

Thursday, 16 October 2014

IOI 2011 - Pattaya, Thailand (Bagian 1)

Akhirnya tiba saatnya untuk menyelesaikan "perjalanan akhir" yang dimulai sejak OSK. Sudah bertahun-tahun berlalu, tetapi ingatan saya akan IOI ini masih melekat. Memang, seperti kata teman-teman IOI 2011, IOI ini merupakan salah satu yang paling berkesan.

Tulisan ini akan membahas hari-hari saya di Thailand saat IOI 2011. Untuk foto-foto, saya tidak banyak mengambil momen karena masih belum sadar bertapa pentingnya momen tersebut :') oleh karena itu saya mengumpulkan foto dari berbagai pembina TOKI, Brian, Jessica, guide di sana, dan foto saya sendiri. Dengan tulisan ini, lengkaplah tulisan IOI 2011 dari sudut pandang empat besar TOKI 2011, karena saya yang terakhir menulis tentang ini.

Keadaan

Anggota tim yang berangkat:
  • Bu Inge - delegation leader
  • Pak Rully - deputy leader
  • Gang of Four (GoF) - contestant (termasuk saya)
  • Brian - guest (membantu anggota delegasi)

IOI 2011 - Pattaya, Thailand (Bagian 2)

Hari 4

Hari kontes kedua telah tiba. Paginya saya makan biasa saja, dan sedikit minum. Untungnya tidak ada masalah apapun untuk masuk ke dalam ruangan kontes. Sesaat sebelum kontes dimulai, "contestants, please shake hand with the the other contestant". Saya dan teman-teman sebangku saling menatap bingung satu sama lain, lalu mulai bersalaman. Rasanya saya lebih percaya diri, dan merasa mampu mengerjakan soal hari kedua ini. Oh ya, apapun yang saya kerjakan hari ini toh tidak akan merubah hasil di hari pertama saya.

Saya mulai kontes dengan mengemut cokelat 99% cocoa, lalu membaca soal dengan tenang. Soal hari ini adalah parrot, elephant, dan crocodile. Saya mulai memikirkan solusi crocodile. Selama 2 jam, akhirnya saya berhasil mengerjakannya sampai sebelum 1 subtask terakhir. Karena sudah 2 jam, maka saya pindah ke soal lain, parrot. Untuk soal ini, nilai saya juga lumayan bagus. Saya sudah memikirkan berbagai macam cara, dan tidak bisa meningkatkan nilai itu lagi. Hingga akhirnya tinggal 1 jam terakhir, saya gunakan untuk mengerjakan elephant. Sisa waktu saya gunakan lagi untuk mengejar solusi soal crocodile. Oh ya, selama hampir 3 jam pertama, cokelat yang saya emut itu tetap di mulut (tidak tertelan atau meleleh!), dan menjaga konsentrasi saya.

IOI 2011 - Pattaya, Thailand (Bagian 3)

Hari 6

Pagi ini kami diajak Yura dan Yegar untuk mengikuti kegiatan "variety for fun" (waktunya panitia hiperaktif beraksi). Kali ini, peserta dipisahkan menjadi sekitar 4 grup. Kami GoF mendapati di tim kuning. Ada seorang panitia hiperaktif yang menjadi provokator sekaligus pemimpin grup kuning. Dia membawa pengeras suara dan memanas-manasi seluruh peserta. Tidak lama kemudian kita diajari yel-yel, dan mulai bermain.

Provokasi (foto oleh Yegar)!

Saturday, 11 October 2014

Kisah Perjalanan di TOKI: Persiapan IOI

Masa Rehat

Kembali dari Pelatnas, saya menghadiri acara kelulusan sekolah. Secara tidak menyangka pula saya mendapatkan nilai ujian yang memuaskan, setelah berjuang belajar kilat selama dua minggu seusai Pelatnas 2. Saya juga dikejutkan dengan pengumuman SNMPTN undangan bahwa saya TIDAK DITERIMA. Oke, saya harus belajar untuk SNMPTN tertulis :'(

Saya mulai membeli buku sejenis kumpulan soal untuk SNMPTN dan belajar kembali, padahal dikira sesudah ujian nasional, bisa fokus IOI. Saya juga mengikuti kompetisi lokal yang segera dilaksanakan seperti COMPFEST 2011, tetapi akhirnya tidak masuk ke final karena saat penyisihan perut saya sakit dan tidak sempat menyelesaikan satu soal lagi :(

Namun untungnya, saya menerima email dari humas Fasilkom UI bahwa pihak Fasilkom menawarkan beasiswa untuk peraih medali OSN. Namun, masih diperlukan seleksi. Jelas saya senang dengan informasi ini. Sebenarnya masih ada keraguan juga pada diri saya, mau kuliah di mana. Kandidat saya adalah UI atau NTU/NUS. Namun, untuk berkuliah di NTU/NUS saya membutuhkan medali IOI dalam memperlancar proses masuk. Saya tidak ingin bertaruh pada sesuatu yang belum terjadi. Akhirnya setelah melalui pemikiran panjang, saya memutuskan untuk mendaftarkan diri ke UI lewat jalur masuk peraih medali OSN tersebut.

Thursday, 9 October 2014

OSN 2014 - Mataram, Lombok

Lima tahun telah berlalu sejak saya mengikuti OSN 2009. Saya yang dulu duduk sebagai peserta, kini duduk sebagai juri. Lebih tepatnya, saya berada di bawah SC (Scientific Committee), yaitu panitia yang mengurus segala hal yang berkaitan dengan soal. Sungguh suatu kehormatan besar saya bisa menjadi juri bagi OSN komputer/informatika 2014.


Lima tahun berlalu

Kegiatan sebagai juri sudah dimulai sejak lama sebelum OSN. Kami mulai mengumpulkan soal, menyeleksi soal, dan memproses soal hingga dijadikan soal yang siap pakai. Apakah hanya itu? Tidak! Kami juga mengurus sebagian kecil PJJ dan open OSN. Kebetulan tahun ini (2014), Open OSN akan dibuka untuk kalangan internasional. Banyaknya yang harus dikerjakan menjadi mengganda. Untungnya selalu ada pembina TOKI yang siap menasihati dan membantu.

Saya lebih menceritakan tentang apa yang terjadi saat OSN secara garis besar. Sehingga tulisan berikut akan dimulai dari hari pertama OSN.

Saturday, 9 August 2014

IOI 2014 - Taipei (Bagian 1)

Sesuai pengumuman akhir Pelatnas 3 TOKI 2014, peserta berbincang-bincang tentang masa depan dan masa lalu (simulasi terakhir yang mereka hadapi). Tiba-tiba, Pak Yugo bilang ke saya:

"Kamu tahu?"
"Apa Pak?", jawab saya
"Kamu ikut"

Ternyata saya dipercayai pembina TOKI untuk mendampingi 4 besar TOKI di IOI 2014, Taipei - Taiwan. Menurut informasi, seharusnya yang berangkat adalah Ashar. Namun karena dia berhalangan pada tanggal tersebut, saya yang diminta tolong.

Entah sejak kapan, ada alumni TOKI yang ikut ke IOI untuk membantu anggota delegasi Indonesia. Misalnya tahun 2011 Brian dan 2012 Risan. Tugasnya membantu translasi soal, ikut rapat teknis, menyerap ilmu untuk diterapkan di OSN, dan sebagainya. Rasanya senang sekali saya mendapatkan kepercayaan seperti ini, dan saya akan melakukannya sebaik mungkin!

Persiapan

Sebagai langkah awal menjadi pendamping, kita harus dekat dulu dengan peserta. Oleh karena itu saya mulai dengan mengirimkan email-email terkait Pelatnas 4. Saya memanggil mereka dengan "GoF - Gang of Four". Panggilan ini juga diberikan kepada 4 besar TOKI 2011 (zaman saya). Saya juga mengamati kemampuan mereka, kuat-lemahnya, dan kebiasaan-kebiasaan mereka saat kontes. Saya juga membaca silabus IOI, untuk persiapan rapat delegasi nantinya. Harapannya apa yang saya persiapkan saat itu bisa berguna saat IOI nanti.

IOI 2014 - Taipei (Bagian 2)

Pastikan Anda membaca bagian 1.

Hari 4

Hari ini adalah waktunya ekskursi. Kami akan pergi ke National Center of Traditional Art (NCTA) Taiwan. Awalnya saya kira hanya seperti museum saja, tetapi ternyata jauh berbeda! Tempatnya seperti replika kecil suasana Taiwan, seperti TMII di Jakarta. Ada pertokoan Cina, yang tiap tokonya menjual suvenir berupa kerajinan tangan, makanan, permen, gasing, payung, kuas, dan barang-barang Cina lainnya. Kami juga bisa membuat suvenir kita sendiri, seperti membeli payung kertas yang polos, lalu melukis di payung itu sesuka hati. Jalanan di pertokoan ini juga dilalui penari dengan musik-musik tradisional. Suasananya benar-benar seperti chinatown yang di film-film.

Suasana NCTA

Sunday, 3 August 2014

ACM ICPC 2014 World Final - Ekaterinburg (Bagian 1)

Memasuki pertengahan tahun 2014, saya banyak berpergian yang ada kaitannya dengan competitive programming: Ekaterinburg (Russia) pada akhir Juni untuk WF ICPC, Taipei (Taiwan) pada minggu ke-3 Juli untuk menjadi anggota delegasi Indonesia pada IOI, dan Mataram (Lombok) awal September untuk menjadi juri OSN 2014. Ketiganya adalah pengalaman yang sangat berharga, oleh karena itu akan saya tuliskan ceritanya. Tentunya untuk tulisan ini, saya akan membahas tentang WF di Ekaterinburg.

Keadaan

Setelah 15 tahun perjuangan, akhirnya UI berhasil terkualifikasi ke ACM-ICPC World Final. Kami menduduki peringkat 6 pada ACM-ICPC Regional Phuket pada tahun 2013 yang lalu, dan berkat itu kami lolos. Tim UI yang berangkat untuk ke WF adalah Pak Denny (coach), Ashar, Aji, dan saya.

ACM ICPC 2014 World Final - Ekaterinburg (Bagian 2)

Pastikan Anda membaca juga bagian 1.

Hari 4

Saya bangun jam 5.30 pagi, lalu ke kamar Ashar untuk merencanakan sarapan. Masalahnya adalah kita harus berangkat jam 7.30 dari stasiun kereta untuk ke airport, padahal sarapan baru disediakan jam 7.30. Akhirnya kita minum/makan energen dan sozzis yang Ashar bawa. Setelah itu kita berberes-beres, dan langsung menuju ke stasiun kereta.

Kereta di Moscow ke bandara

ACM ICPC 2014 World Final - Ekaterinburg (Bagian 3)

Pastikan Anda membaca juga bagian 1 dan bagian 2.

Hari 8

Pagi ini saya telat bangun, dan dibangunkan oleh Aji jam 7. Kami segera turun dan sarapan. Keadaan sudah berubah, ruang makan sangat sepi. Barangkali para peserta masih tidur.

Setelah selesai sarapan, saya memutuskan untuk membagi-bagi suvenir kepada para orang-orang baik, yaitu mereka yang ramah atau sudah bekerja keras, seperti tim ICPC lain dan panitia. Suvenir ini sebenarnya sisa suvenir saat IOI, yang bentuknya pembatas buku dan gantungan kunci wayang. Sebenarnya saya sudah ingin membagikannya kemarin, tetapi tidak kesampaian karena kita tidak ikut acara penutupannya sampai selesai. Pagi ini, hanya ada 4 orang panitia yang terlihat di hotel. Saya membagikan 1 kepada panitia helpdesk yang sudah datang dari pagi, dan dia sangat senang. Dia bahkan meminta saya menuliskan pesan di balik suvenir yang saya bawa. Saya mencoba menitipkan suvenir itu kepadanya untuk diberikan kepada Vika, sayangnya dia tidak mengenal Vika.

Friday, 4 July 2014

Kisah Perjalanan di TOKI: Saya dan Akhir Pelatnas

Pelatnas 3 TOKI 2011

Kali ini Pelatnas dilaksanakan di Universitas Indonesia, kampus Depok. Kami menginap di Pusat Studi Jepang, Fakultas Ilmu Budaya. Tempatnya sangat hijau, banyak pohon karet dan dekat danau. Jauh lebih baik dibandingkan dengan pusat kota yang biasa saya tempati. Rasanya benar-benar kagum, sekitar 2 tahun yang lalu tempat inilah yang menjadi awal perjuangan saya di OSN, dan kini menjadi pertandingan akhir dalam merebut posisi 4 besar TOKI 2011.

Kamar yang saya tempati menjadi basecamp, setiap harinya menjadi tempat berkumpul untuk makan malam atau bermain.

Saat berkumpul

Tuesday, 1 July 2014

Kisah Perjalanan di TOKI: Saya dan Pelatnas Kedua

Pelatnas 1 TOKI 2011

Setelah membangun tekad yang kuat, saya mulai berjuang kembali di Pelatnas 1 TOKI 2011. Suasananya tidak berbeda jauh dengan tahun lalu. Sayangnya tidak banyak veteran yang hadir, hanya ada Tracy, Hudi, Abit, Febrian, dan Reinhart. Sebagian dari mereka mengundurkan diri untuk alasan akademis. Selain itu, teman-teman Pelatnas 1 TOKI 2010 saya sudah menjadi asisten, di antaranya: Yozef, Martha, Roshyid, Mirza, dan Jordan. Rasanya lucu juga diasuh oleh orang yang dulunya adalah sesama peserta.

Namun, terdapat perbedaan drastis dalam diri saya. Pada tahun sebelumnya, Pelatnas saya suram. Kali ini tidak demikian, saya selalu berusaha menghabisi soal-soal yang dikeluarkan. Untungnya dengan peningkatan kemampuan selama ini, saya dapat menghadapi Pelatnas I dengan lancar.

Sunday, 1 June 2014

Ternary Search

Kuliah di semester enam memang bukan main-main, setiap waktu luang yang saya miliki harus digunakan untuk mengerjakan proyek perangkat lunak. Akibatnya blog ini menjadi kurang terurus. Syukur-syukur kesibukan mengurus proyek itu sudah mulai menurun, dan saya bisa kembali menulis.

Topik yang dibahas kali ini adalah ternary search. Bagi coder pemula, pastinya pernah mendengar istilah binary search. Anda juga mungkin pernah mendengar bahwa jika binary menyatakan dua, maka ternary menyatakan tiga. Jadi yang akan dibahas ini adalah pencarian ternary, yaitu dengan membagi tiga daerah. Kira-kira seperti ini:

Saturday, 1 March 2014

Fixed Size RMQ

Pada kesempatan kali ini saya ingin memperkenalkan struktur data yang saya pelajari dari Brian Marshal. Entah apa nama struktur data ini, sehingga akan saya sebut sebagai "fixed segment array" saja. Struktur data ini bisa jadi sangat membantu dalam optimisasi algoritma, misalnya pada DP. Simak penjelasan berikut dan cobalah untuk mengerjakan soalnya :)


Permasalahan

Diberikan sebuah array bernama A yang berisi N bilangan, dan sebuah bilangan L. Terdapat Q buah pertanyaan yang berbunyi:
Dari indeks X sampai indeks X+L-1, bilangan apa yang paling kecil?

Sepintas, persoalan ini sangat mirip dengan RMQ (Range Minimum Query). Oleh karena itu, struktur data seperti segment tree atau sparse table seharusnya dapat melayani pertanyaan-pertanyaan tersebut dengan efisien.

Struktur data Kompleksitas membangun Kompleksitas per pertanyaan
Segment tree O(N) O(log N)
Sparse table O(N log N) O(1)

Namun, solusi dengan struktur data tersebut terlalu overkill. Perhatikan bahwa terdapat karakteristik khusus pada masalah di atas, yaitu besar rentang yang diberikan selalu L. Ada struktur data yang lebih efisien untuk menyelesaikannya, yaitu fixed segment array. Kompleksitas untuk membangunnya hanya O(N) dan setiap pertanyaan dapat dijawab dalam O(1).

Monday, 10 February 2014

Bekerja dengan Logaritma

Persoalan motivasi:
  1. Diberikan dua bilangan bulat a dan b (1 ≤ a, b ≤ 108). Apa tiga digit pertama dari ab?
  2. Diberikan sebuah bilangan bulat N (1 ≤ N ≤ 105). Tentukan banyaknya digit dari N faktorial!
  3. Diberikan sebuah bilangan bulat N. Tentukan K, sedemikian sehingga NK lebih kecil dari K faktorial!
  4. Diberikan sebuah bilangan genap n. Tentukan \(\displaystyle \frac{C^{N}_{N/2}}{2^N}\)!
Bagaimana melakukan komputasi semacam itu? Sesuai dengan judulnya, solusinya adalah dengan logaritma.

Dalam pemrograman kompetitif, logaritma memang jarang digunakan. Bila diperlukan, biasanya bukan sebagai inti soal/algoritma utama. Artinya, logaritma bisa jadi seperti perkakas yang dibutuhkan untuk menyelesaikan soal. Tanpa perkakas itu, soal tidak dapat terselesaikan meskipun kita tahu algoritma utamanya. Oleh karena itu saya harap tulisan ini dapat membekali Anda :)

Tuesday, 4 February 2014

Kisah Perjalanan di TOKI: Bangkit dari Keterbelakangan

Setelah OSN berakhir, hari-hari kembali berlangsung seperti biasa. Kembali ke lingkungan sekolah, menghafal tata nama senyawa karbon, menggunakan mikroskop, dsb. Bedanya hanya saya harus ekstra usaha untuk mengejar segala ketinggalan pelajaran karena ikut OSN. Tidak terlalu bermasalah, karena saya hanya bolos sekitar seminggu saja.

Pelatnas

Tidak lama kemudian, datang surat ke kantor tata usaha, berisi undangan menghadiri Pelatihan Nasional (Pelatnas) 1 TOKI 2010 di Bandung. Pelatnas ini durasinya tiga minggu, yang artinya saya harus bolos kembali. Rasanya lumayan senang karena bisa bertemu lagi dengan teman-teman OSN.

Sesampai di Bandung, ternyata suasana kompetisinya terasa sekali. Ada beberapa orang yang tidak pernah saya jumpai di OSN, mendadak muncul. Mereka dikenal sebagai VETERAN. Jadi orang-orang yang sebelumnya sudah pernah mengikuti Pelatnas, tetapi gagal di suatu tingkat atau berhasil ke IOI, tahun depannya dapat ikut Pelatnas lagi tanpa melalui OSN (tentunya bila mereka masih belum lulus SMA).

Monday, 3 February 2014

SPOJ DOSA - Lalith Dosa

Soal ini sama sekali tidak ada hubungannya dengan "dosa" dari "berdosa". Jangan tanya saya mengapa judul soalnya seperti itu :)

Soal kali ini tergolong baru ditambahkan di SPOJ dan cukup populer. Terlihat sebagai soal yang mudah, tetapi sebenarnya tidak. Banyak orang yang terjebak dan mendapatkan WA, lalu bertanya-tanya di mana letak kesalahannya kepada sang pembuat soal. Saya sangat merekomentasikan bagi kalian untuk mencobanya terlebih dahulu.

Salah satu kasus uji mautnya adalah:
12
10 11 12 10 9 15 16 22 21 19 20 21 
Jawaban seharusnya adalah 4.

Saturday, 1 February 2014

SPOJ PERIOD - Period

Kebiasaan saya kalau sedang mau mengerjakan soal-soal di SPOJ adalah menatapi halaman status. Jika melihat ada orang melakukan pengumpulan untuk soal yang kodenya menarik, akan saya coba lihat soalnya. Kali ini saya mendapati soal sederhana yang menyenangkan untuk didiskusikan, yaitu tentang string. Sepengalaman saya bertanding, soal string jarang keluar di perlombaan (kecuali ICPC Jakarta).

Inti soalnya sederhana, Anda dapat langsung mengaksesnya di sini. Saya sangat merekomentasikan bagi kalian untuk mencobanya terlebih dahulu.

Solusi paling naif adalah dengan mencoba semua kemungkinan prefix, lalu untuk masing-masing prefix dicari periodenya. Seperti biasa, cara ini akan TLE. Untuk mencoba semua kemungkinan prefix saja sudah ada N kemungkinan. Oleh karena itu, untuk mempercepat pendekatan ini setidaknya untuk menghitung periode harus dilakukan dalam O(1).

Saturday, 18 January 2014

Teknik Optimisasi Konstanta

Akhir-akhir ini saya sering berlatih di SPOJ, dan seringkali sudah menggunakan algoritma optimal, tetapi tetap TLE. Akibatnya saya harus melakukan optimisasi konstanta habis-habisan hingga akhirnya mendapat AC.

Pada competitive programming, konstanta sering dianggap menjadi hal yang kecil. Karena kecil, dianggap tidak mempengaruhi performa secara keseluruhan. Memang benar, saya termasuk yang berpikiran seperti itu. Namun hal ini tidak selalu berlaku apabila konstanta yang kecil itu ada dalam jumlah yang besar. Bayangkan jika harga beras awalnya Rp 1,00 per butir, lalu tiba-tiba naik menjadi Rp 1,12 per butir. Mungkin memang kenaikannya hanya Rp 0.12, tetapi bila kita membeli 1 ton beras yang isinya ada 36.590.000 butir beras, kenaikannya menjadi Rp 4.390.800,00. Hal yang sama juga berlaku pada program, bila konstanta yang kecil itu muncul pada looping yang bisa dilakukan ratusan ribu kali, bisa saja akan mempengaruhi performa program secara signifikan.

Biasanya, Anda hanya memerlukan optimisasi konstanta pada kompetisi ACM-ICPC (biasanya bukan Jakarta) atau mengerjakan soal di online judge. Untuk kompetisi seperti OSN atau IOI, sang pembuat soal sudah menentukan time limit secara bijaksana sehingga solusi dengan perbedaan konstanta yang bisa dimaklumi tetap mendapatkan AC. Bisa jadi time limit yang ditentukan berasal dari 10 dikali waktu eksekusi solusi si pembuat soal.

Pengalaman saya dalam pemrograman terus menambah pengetahuan dalam melakukan optimisasi konstanta. Berikut ini saya jabarkan teknik-teknik yang saya ketahui, dan siapa tahu dapat membantu Anda di kemudian hari. Sebagai catatan, berkat optimisasi konstanta (dan keberuntungan) saya berhasil menyelesaikan soal Alien Abduction Again, soal ICPC Jakarta 2013 dan berkat itu tim saya (Vidina 2.0) berhasil menjadi best local team :)

Tuesday, 14 January 2014

SPOJ FSHEEP - Fencing in the Sheep

Soal ini saya hadapi pada saat latihan Pelatnas 2 TOKI 2011. Saya benar-benar tidak bisa mengerjakannya pada saat itu. Akhirnya saya kembali pada saat Pelatnas 4 TOKI 2011, dan berhasil membalas dendam dengan menyelesaikan soal ini >:-)
Dari deskripsi soalnya, terlihat bahwa soal ini cukup sederhana: diberikan sebuah poligon yang mungkin tidak konveks dan sejumlah titik. Tentukan banyaknya titik yang ada di dalam poligon!

Memeriksa apakah suatu titik berada di dalam poligon bisa dilakukan dengan algoritma ray casting, yaitu dengan membuat segmen garis imajiner dari titik tersebut ke suatu arah sembarang, lalu hitung berapa kali garis itu berpotongan dengan poligon. Bila genap, artinya titik berada di luar poligon dan bila ganjil, artinya titik berada di dalam poligon (tidak percaya? Cobalah!). Sayangnya algoritma ini agak repot dilakukan karena garis imajiner yang dibuat tidak boleh menyentuh titik sudut pada poligon. Lagipula kompleksitas untuk sekali pemeriksaan adalah O(N), padahal poligon yang diberikan bisa memiliki sisi sebanyak 100.000, dan banyaknya titik juga bisa sampai 100.000.

Bila tidak ada properti khusus pada soal ini, maka sepertinya soal ini mustahil untuk diselesaikan. Beruntungnya, ada sebuah kalimat yang sangat penting pada soal: "Exhausted, he moves to a place within the pen from which he can see the whole interior of the pen (without any fence getting in the way) and begins to count the sheep which are within it."

Artinya, dijamin ada sebuah titik yang mana bila seseorang berdiri di sana, dia bisa melihat seluruh isi poligon (kemudian diberitahu bahwa titik tersebut ada di (0,0)). Berikut ini gambar yang memberi ilustrasi jenis poligon tersebut. Poligon di sebelah kiri merupakan poligon yang valid, dan yang kanan tidak karena daerah yang berwarna coklat tidak bisa dilihat:

Friday, 3 January 2014

Komposisi Struktur Data Dynamic Range Query

Sejauh ini saya sudah pernah membahas struktur data:
  • Disjoint-set
  • Segment tree[2] [3]
  • Binary Indexed Tree
  • Treap [1]

Ada juga struktur data yang menarik untuk digunakan:
  • BBST (AVL tree atau Red-Black Tree)
  • Segment array [1]
  • Range tree [1] (sering diimplementasikan sebagai segment tree dengan nilai agregat berupa vector)

Dan ada juga struktur data yang lebih jarang digunakan:
  • Kd Tree
  • Quad Tree
  • Interval Tree

Masing-masing struktur data tersebut memiliki peran dan kegunaan masing-masing. Oleh karena itu, ketika sedang mengerjakan soal dynamic range query non-klasik, pertanyaan yang muncul adalah "dikerjakan pakai struktur data apa ya?"