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: