Jumat, 04 Juli 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

Selasa, 01 Juli 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.

Minggu, 01 Juni 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:

Sabtu, 01 Maret 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).

Senin, 10 Februari 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 :)

Selasa, 04 Februari 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).

Senin, 03 Februari 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.

Sabtu, 01 Februari 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).

Sabtu, 18 Januari 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 :)

Selasa, 14 Januari 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: