TLX Training Gate - Dibuka!

Sebagai kelanjutan dari dari pengerjaan materi TOKI Training Gate generasi baru, kini training gate-nya telah dirlis!

Dengan kerja keras dari TOKI Fellowship, platform untuk training gate generasi baru telah hadir. Kali ini platform ini diberi nama TLX, sehingga namanya menjadi TLX Training Gate.

Anda dapat membaca lebih lengkapnya perkenalan tentang TLX Training Gate di blog IA TOKI.

Saya sangat merekomendasikan rekan-rekan yang masih pemula untuk mencoba mengerjakannya. Latihannya tidak hanya untuk soal pemrograman, tetapi ada juga untuk pemahaman konsep dan latihan untuk OSK/OSP.

Sumber: https://blog.ia-toki.org/2016/03/materi-pemrograman-kompetitif-dasar-toki-training-gate-untuk-umum/

Selamat mencoba dan langsung ke TKP!

Efisiensi Penggunaan Waktu

Berkali-kali dalam hidup, saya harus menghadapi banyak hal dalam jangka waktu yang sempit dan terbatas. Contohnya adalah pada tahun 2013, yang mana saya harus:

1. Menjadi ketua panitia programming competition CompFest 2013.
2. Menjadi ketua Fun Programming Club di Fasilkom.
3. Menjadi ketua departemen di suatu bagian pada KMBUI.
4. Belajar untuk ICPC Regional 2013.
5. Menjadi asisten dosen untuk perkuliahan yang melelahkan karena banyak sesi lab dan asistensi (struktur data & algoritma).
6. Kuliah!

Mungkin kalian bertanya, kenapa saya "gila" mau memiliki aktivitas sebanyak itu. Sebagian besar alasannya adalah tidak ada orang lain yang mau mengemban tugas tersebut. Berhubung saya salah satu yang berpotensi, akhirnya saya terima saja pekerjaan itu, daripada tidak ada yang menjalankan.

Pada akhirnya saya berhasil melewati hal-hal tersebut, dan ternyata pada tahun 2014 hal sejenis itu terulang lagi. Perlahan-lahan, saya mempelajari bagaimana kiat-kiat menggunakan waktu secara efisien. Hal ini lah yang akan saya bagikan pada tulisan ini.

Penting!
Tulisan ini berdasarkan pengalaman saya. Efek yang dialami atau cara yang digunakan orang lain bisa jadi berbeda.

---

Pekerjaan Boleh Jadi Banyak,
Tetapi Stress Karena Banyak Kerjaan Tidak Boleh

Misalkan suatu pekerjaan bisa diselesaikan dalam 5 jam. Namun karena stress, bisa jadi pekerjaan itu selesai dalam 7 jam. Ada waktu lebih yang digunakan untuk pusing-pusing dan tidur-tiduran karena tidak bisa menerima kenyataan. Yang harus disadari adalah hal-hal seperti ini tidak memberi keuntungan. Jika kita mampu mengatasi stress dan bekerja seperti biasanya, pekerjaan bisa jadi lebih cepat selesai.

Mungkin penyebab utama dari stress ini adalah rasa panik karena ada terlalu banyak pekerjaan dan khawatir tidak bisa selesai tepat waktu. Ada beberapa cara yang dapat digunakan untuk mengatasi stress tersebut (ada saya jelaskan di bawah). Percayalah bahwa jika pekerjaan yang banyak itu diselesaikan sedikit demi sedikit, lama-lama akan selesai juga.

---

Rencanakan Pekerjaan yang Harus Selesai Hari Ini

Menurut saya perencanaan ini harus realistis. Tidak perlu "pokoknya hari ini harus selesai tugas A, tugas B, tugas C, presentasi X, sama project Z". Sebab kalau tidak mungkin selesai, bisa jadi hari esoknya juga "pokoknya hari ini harus selesai tugas B, tugas C, presentasi X, sama project Z". Ujung-ujungnya sama saja dengan tidak ada perencanaan per hari, hanya bekerja semampunya untuk menyelesaikan tugas per hari.

Biasanya rencana harian saya seperti gambar berikut:

Batangan hitam menyatakan istirahat

Jadi diharapkan dalam sehari 3-4 pekerjaan besar bisa selesai.

Penjelasan Algoritma Euclidean untuk GCD

Motivasi

Setiap orang yang pernah belajar untuk OSK/OSP komputer kemungkinan besar mengenal fungsi berikut:

Fungsi yang pendek ini adalah Algoritma Euclidean untuk mencari GCD. Entah mengapa cukup dengan operasi modulo, tiba-tiba didapatkan GCD dari dua bilangan. Padahal jika kita mencari GCD menurut cara anak SD, diperlukan faktorisasi bilangan terlebih dahulu. Bagaimana sebenarnya fungsi ini bekerja?

Ada pembuktian matematis mengapa algoritma ini benar. Sayangnya pembuktian ini bisa jadi sulit dicerna bagi beberapa orang. Ada pendekatan lain untuk memahami bagaimana fungsi ini bekerja, dan akan saya jelaskan pada tulisan ini.

GCD = Memotong Kue

Kita ganti persoalan GCD(a, b) sebagai berikut:
Diberikan kue berbentuk persegi panjang, dengan panjang a dan lebar b. Kue ini hendak dipotong menjadi sejumlah persegi. Tidak boleh ada potongan yang tidak persegi. Tentukan sisi persegi terbesar yang mungkin digunakan!

Sebagai contoh, jika a=30 dan b=21, maka jawabannya adalah 3. Gambar berikut menunjukkan cara pemotongannya:

Jawaban dari masalah ini sama saja dengan GCD(a, b). Sebab kita berusaha mencari nilai terbesar yang habis membagi a dan b.

ACM ICPC World Final 2015 - Morocco (Bagian 1)

Tim BerinGAS mendapat peringkat 4 pada ICPC Regional Jakarta 2014 yang lalu. Saya sudah putus harapan untuk bisa lolos ke World Final (WF), mengingat biasanya hanya 3 besar yang mendapat tiket ke WF. Namun pada awal tahun 2015, saya sedikit penasaran juga apakah tim kita mendapat slot WF. Saya sering-sering cek blog CJ Hwang, berharap infonya segera muncul.

Suatu hari, saya sangat mengantuk dan sudah tidur sekitar 21.30. Pagi-pagi jam 05.00 saya bangun dan dikagetkan dengan notifikasi di HP. Setelah saya cek, banyak yang memberi selamat karena tim BerinGAS BERHASIL MASUK KE WF 2015! Saya yang tadinya sudah siap-siap pensiun jadi kembali harus latihan. Saya juga harus mengatur ulang rencana hidup selama 6 bulan ke depan yang sebelumnya sudah dirancang dengan asumsi tanpa WF. Saya langsung mundur dari kerja paruh waktu, memilih topik skripsi yang ringan, dan mengalokasikan waktu untuk latihan.

Keadaan

Setelah 15 tahun berjuang di ACM ICPC, tim UI akhirnya masuk ke WF pada tahun 2014. Tahun ini, UI masuk lagi untuk kedua kalinya. Tim UI yang berangkat untuk ke WF adalah Pak Denny (coach), Ammar, Soko, dan saya.

Lokasi WF tahun ini adalah di kota Marrakesh, Maroko. Lokasinya di Afrika utara, dekat dengan Eropa barat.

Sumber: http://www.freeworldmaps.net/africa/morocco/location.gif

ACM ICPC World Final 2015 - Morocco (Bagian 2)

Daftar bagian tulisan:

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

Hari 3

Akhirnya tidur pulas dan saya bangun pukul 07.30. Ternyata nama hotelnya adalah Hotel Palmerie yang sempat salah saya baca sebagai "Palmerah". Kami pergi sarapan ke restoran, dan saya makan banyak roti dan buah. Roti di sini sangat enak, terutama yang teksturnya lembut atau renyah. Kalau dari Pak Denny, mungkin rotinya bisa enak karena Maroko mendapat banyak pengaruh dari Prancis. Yang saya suka adalah croissant dan pain au chocolat. Namun saya kurang suka dengan roti varian lain yang teksturnya keras.

Musik yang seperti di acara TV buka puasa ternyata alat musik senar

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