Senin, 14 September 2015

Seni Hashing

Setelah mempelajari hashing, Anda mungkin perlu tahu tentang teknik-teknik khusus hashing. Teknik ini saya dapatkan melalui pengalaman, dan telah berkali-kali "menyelamatkan" peringkat tim pada kompetisi. Semoga berguna juga untuk Anda :)

Oh ya, selain rolling hash, nama-nama yang tercantum merupakan nama ciptaan saya. 

Rolling Hash

Teknik ini sangat umum digunakan. Saya mempelajarinya dari tutorial Topcoder.

Ceritanya adalah diberikan sebuah string S.
Bagaimana kita mendapatkan nilai hash dari semua substring S yang memiliki panjang k?
Fungsi hash yang digunakan pada rolling hash adalah menganggap string sebagai bilangan basis 26. Lebih umum lagi, basis ini sebenarnya boleh berapa saja. Misalkan basis yang dipilih adalah B.

Anggap S = "ayamxzc" dan k=4. Jika h[i] menyatakan nilai hash untuk S[i..i+k-1], maka bisa digambarkan nilai h[0] sampai h[3] sebagai berikut:

Jumat, 04 September 2015

Tentang Hashing

Saya akan menjelaskan sebuah teknik yang bernama hashing. Hashing merupakan teknik yang sering digunakan dalam pemrograman pada umumnya. Untuk pemrograman kompetitif, hashing dapat membantu menyelesaikan persoalan secara tidak terduga.


Permasalahan

Dalam sebuah universitas, terdapat banyak mahasiswa. Setiap mahasiswa memiliki nilai IPK dan bisa berubah sewaktu-waktu.
Diberikan sejumlah nama orang dan nilai IPK mereka. Selanjutnya, terdapat banyak operasi berupa:
  1. Mengubah IPK seorang mahasiswa bernama X menjadi Y.
  2. Bertanya "berapa nilai IPK dari mahasiswa yang bernama X?"
Cara paling sederhana untuk menyelesaikan persoalan itu adalah menyimpan daftar nama dan nilai IPK dalam array, lalu melakukan linear search untuk setiap pertanyaan. Sayangnya cara ini tidak efisien.

Cara yang lebih baik adalah dengan struktur data Binary Search Tree (BST). Dengan BST, kompleksitas untuk setiap operasi adalah O(log N) (tentunya ada dikalikan dengan konstanta untuk membandingkan string, tetapi tidak saya tulis). Memang cukup cepat, tetapi cara ini bukan yang terbaik.

Lalu bagaimana?

Seandainya yang diberikan bukan nama, tetapi nomor mahasiswa yang kisarannya antara 000000 sampai 999999, apakah cara lebih baik yang bisa dilakukan?

Senin, 03 Agustus 2015

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.

Rabu, 29 Juli 2015

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.

Senin, 27 Juli 2015

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:

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:

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

Kamis, 26 Maret 2015

TOKI Training Gate - Generasi Baru

Memperkenalkan: Materi TOKI Training Gate!


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.

Kamis, 26 Februari 2015

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.