ACM ICPC World Final 2015 - Morocco (Bagian 3)

Daftar bagian tulisan:

• Bagian 1
• Bagian 2
• Bagian 3 (tulisan ini)

Hari 7

Hari ini sudah tidak ada agenda resmi dari ICPC. Karena kita sudah jauh-jauh ke Afrika, Pak Denny sudah booking tur ke gurun Zagora. Kami akan naik mobil bersama seorang supir dari Marrakesh ke Zagora (~260 km), kemudian naik unta ke lokasi kemah (di padang pasir), melihat matahari terbenam, berkemah, tidur, melihat matahari terbit, naik unta lagi ke jalan raya, lalu pulang ke Marrakesh.

Kami bangun 06.00, siap-siap sarapan. Sambil siap-siap, saya membaca soal OSN hari 2. Rasanya senang karena 2 soal buatan saya keluar pada hari ke-2 ini :)
Soal saya yang tidak keluar merupakan soal tersulit. Jadi ternyata tim juri OSN tahun ini masih punya belas kasihan >:)

Untuk sarapan, saya makan sebanyak yang saya bisa dan menikmati croissant terakhir. Berikutnya kami checkout, dan naik mobil tur. Pengemudi kita bernama Mohammed, dan Bahasa Inggrisnya bagus. Sepanjang perjalanan kami berbincang-bincang dengan Mohammed seputar Maroko dan Indonesia.

Croissant dan pain au chocolat :"

Merencanakan strategi perang

TOKI Training Gate - Generasi Baru

Memperkenalkan: Materi TOKI Training Gate!

Akses di: https://github.com/ia-toki/training-gate-id

Inilah sebab saya jarang menulis blog pada awal tahun 2015 :))

Sejarah TOKI Training Gate

Training Gate (akan saya singkat menjadi TG) pertama yang ada adalah teks PJJ zaman Ranau. Tahu Ranau? Jika Anda tahu, Anda tua.

Ranau bisa dianggap grader TOKI yang lama, dikembangkan oleh Pak Suryana dari UI, dan digunakan sampai OSN 2010. Sejak saya ikut OSN 2009, ada PJJ pra-OSN. Pada PJJ tersebut, terdapat teks-teks materi untuk mengajarkan pemrograman dasar. Contohnya memperkenalkan readln, writeln, array, string, dsb. Materi yang diajarkan sampai pada merge sort, quick sort, BFS & DFS, dan geometri.

ICPC Wold Final 2014 - Messenger

Beberapa minggu terakhir ini saya sedang "balas dendam" soal-soal ICPC World Final tahun lalu (2014). Di antara beberapa soal yang telah saya selesaikan, ada sebuah soal yang sangat berkesan, yaitu yang berjudul Messenger. Oleh karena itu saya akan membahasnya.

Ringkasan Soal

Ada dua orang, sebut saja si-A dan si-B. Masing-masing dari mereka berjalan pada polyline (pada bidang 2 dimensi) dengan kecepatan 1 unit per detik. Polyline rute perjalanan mereka tidak harus sama. Si-A hendak mengirimkan paket ke si-B dengan cara menggunakan kurir. Kurir akan dilepas, lalu berjalan dengan kecepatan 1 unit per detik untuk bertemu si-B. Biaya kurir adalah jarak yang ditempuh si kurir. Perhatikan bahwa si-A dan si-B selalu berjalan tanpa henti, sehingga kurir harus tepat bertemu dengan si-B di suatu titik memberikan paketnya.

Pembahasan

Yang membuat soal ini sulit adalah si-A, si-B, dan kurir berjalan dengan kecepatan 1 unit per detik. Jika si kurir ini begitu dilepas si-A secara instan langsung bertemu si-B, soal menjadi lebih mudah!

Bagaimana pun juga, soal ini memiliki aroma binary search yang kuat. Jadi saya memulai dengan menembak suatu angka, misalkan R, yang menunjukkan jarak tempuh si kurir. Jika kurir berhasil mengirimkan paket ini, kurangi R. Jika tidak berhasil, tambahkan R.

Mari kita sederhanakan soalnya. Anggap polyline si-A dan si-B hanya berupa sebuah segmen garis.

Misalkan:
A(x): posisi si-A pada detik ke-x
B(x): posisi si-B pada detik ke-x

Observasi 1:
Jika si-A mengirimkan paket pada detik t, maka si-B harus menerima paket itu sebelum atau pada detik (t+R). Dengan kata lain, paket dikirim di posisi A(t) dan berhasil diterima di posisi B(t+R) jika jarak A(t) dengan B(t+R) kurang dari atau sama dengan R.

Dengan observasi 1, kita bisa membuang R unit pertama dari pergerakan si-B.

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, R₁ menyatakan jari-jari lingkaran yang lebih besar, dan R₂ menyatakan jari-jari lingkaran yang lainnya. Kemungkinan-kemungkinannya adalah:

1. Kedua lingkaran saling lepas. Hubungannya adalah R₁+R₂ < d.
2. Kedua lingkaran bertemu di satu titik, dan kedua lingkaran tidak saling mengandung (yang satu berada di dalam yang lainnya). Hubungannya adalah R₁+R₂ = d.
3. Kedua lingkaran bertemu di dua titik. Hubungannya adalah R₁+R₂ > d.
4. Kedua lingkaran bertemu di satu titik, dan lingkaran yang besar mengandung lingkaran yang kecil. Hubungannya adalah R₁ = d+R₂.
5. Kedua lingkaran saling lepas, dan lingkaran yang besar mengandung lingkaran yang kecil. Hubungannya adalah R₁ > d+R₂.
6. Kedua lingkaran bertemu di tak hingga banyaknya titik, artinya kedua lingkaran identik dan memiliki titik pusat yang sama. Hubungannya adalah R₁ = R₂ dan d = 0. Kasus ini sebenarnya bisa ditangani juga oleh hubungan pada kasus (4).

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:

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.

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.

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)!