Problem Setting in ACM-ICPC 2014

This year I prepared problems for ACM-ICPC regional Asia Jakarta 2014. I have been creating problems for competitive programming, let say since 2010 for national level. But this was the first time I prepared for international level competition. I submitted 3 problems and 2 of them were accepted. One problem called Lagged Speed was for INC (National level selection before go to ACM-ICPC) and Maze Mayhem for ACM-ICPC regional Asia Jakarta.

Problem links
Lagged Speed : TOKI Learning
Maze Mayhem : UVa Live Archive

Lagged Speed is a problem about pattern. The best way to solve this problem is to code brute-force solution and interpolate the output. You should find constant O(1) solution in no time. I got inspiration for this problem while taking a bath. You know, sometimes you want to set your shower’s temperature to certain amount, but you ended up set it too hot (or too cold). Then you change it a little bit, but after a while you realised you changed too much, and had the temperature too cold. Then you change it again, and so on. You repeat that steps (change, wait, change, wait) until finally you are satisfied with the temperature. Now, change the shower with a car, change the temperature with the car’s speed, and add some (not so) random math function. Voila, You have an ACM-ICPC problem :D

In Maze Mayhem problem, we must compute all N x M grid-maze configurations with at most K obstacles placed where there is no valid path from top-left panel to bottom-right panel. We can simply calculate it via dynamic programming approach. By the time I created the problem, I was thinking that there might exists O(NM) dynamic programming solution. The idea should be similar to 2D DP sum problem. However after 2 days full with sketching, coding, and testing, those approach is impossible (at least I can’t find it in 2 days :D). So I decided that the O(2(N+M)) approach is the expected solution. This problem become somewhat standard DP bitmasking problem, with some tweaking on its DP-state formulation. Shockingly, only 4 teams managed to solve the problem during the competition.

One thing about this problem is, initially there was no K (total obstacles) constraint. However, because NxM were too small ( 1 <= N,M <= 100), one can precompute the solutions using slower approach, as there are only 100 different maze size. Contestant then simply use 100 if-cases based on pre-computed solution. Thus, new constraint K is added.

Overall, I am happy to be able to contribute in ACM-ICPC as problem setter. After 4 years participating as contestant, I myself found that take a role as problem setter is fun. Looking forward for next problem setting opportunity.

OSN Informatika 2014

Di OSN Tahun ini saya kembali iseng-iseng jadi problem setter (pembuat soal). Kali ini saya siapkan 2 soal untuk OSN Informatika. Soal tersebut adalah Reduksi Pesan dan Pelontar Bebek, dimana keduanya disiapkan di hari pertama OSN. Di tulisan kali ini, saya akan bahas solusi dari kedua soal tersebut.

Reduksi Pesan

Soal Reduksi Pesan ini adalah soal yang seharusnya cukup mudah. Solusi untuk soal ini pun cukup bervariasi, mulai dari ad-hoc sampai binary search yang (cukup) rumit. Solusi ad-hoc yang paling sederhana adalah, kita konversi untaian pesan S menjadi deret bilangan. Kita siapkan D[i], bilangan yang merepresentasikan karakter ke-i pada S dengan aturan:

D[1] = 1
D[i] = D[i-1], jika karakter ke i pada S sama dengan karakter ke i-1
D[i] = D[i-1] + 1, jika karakter ke i pada S berbeda dengan karakter ke i-1

*perhatikan bahwa index dimulai dari 1.

Dengan kata lain, kita mengumpulkan tiap karakter yang sama dan bersebelahan pada string S untuk dinomori dengan suatu bilangan yang berurutan.  Selanjutnya adalah, untuk setiap pertanyaan reduksi dari karakter ke-i sampai ke-j, kita dapat mengetahui panjang pesan tereduksi dengan menghitung nilai dari D[j] – D[i – 1]. Jika panjang pesan lebih kecil dari 10, kita cetak pesan tersebut. Untuk melakukannya, kita siapkan suatu array of char terpisah, sebut saja Convert. Nilai Convert[p] adalah karakter dari representasi bilangan p. Hasil reduksi pesan tidak lain adalah karakter-karakter pada Convert[D[i-1]] sampai Convert[D[j]]. Kita bisa mencetak semuanya menggunakan loop sederhana.

Sebagai contoh, perhatikan ilustrasi berikut:

S = A A A B B B A C C D D
D = 1 1 1 2 2 2 3 4 4 5 5

Covert
1 -> A
2 -> B
3 -> A
4 -> C
5 -> D

Intinya, untuk mengerjakan soal ini tidak perlu pengetahuan algoritma aneh-aneh, cukup mahir programming dan logika yang terasah saja. Ini dasar untuk bisa berkompetisi di OSN, dan olimpiade informatika lainnya.

Pelontar Bebek

Soal ini diselesaikan menggunakan dynamic programming. DP[S] adalah nilai kecepatan maksimal yang dapat diperoleh dengan sudut tembak S. Pada awalnya kita atur base-case DP[0] = 0, dan nilai DP lainnya dengan angka yang sangat kecil. Kita bisa melengkapi nilai DP menggunakan formulasi berikut:

DP[ j ] = max(DP[ j ] , DP[ j - s[i] ],  v[i])

dimana i adalah semua index roda gigi yang tersedia. s[i] adalah nilai sudut roda gigi ke-i dan v[i] merupakan kecepatan tembaknya.

Untuk mendapatkan nilai tembak terjauh, kita cukup melakukan percobaan tembak dengan setiap konfigurasi sudut dari 0.1 derajat sampai 180 derajat. Nilai kecepatan tembak terbesar tiap sudut bisa diperoleh dari formula dynamic programming diatas.

Jika kita perhatikan, nilai S paling tinggi adalah 1800, dan akan ada 500.000 buah roda gigi. Kompleksitas DP tersebut adalah O(SN), dan masih terlalu besar untuk mencapai nilai penuh. Untuk memperkecil kompleksitas, kita harus sadar bahwa total besaran sudut tidak mungkin melebihi 1800. Artinya, kita tidak perlu menyimpan seluruh roda gigi yang ada! Untuk roda gigi dengan besaran sudut 1, kita hanya perlu menyimpan 1800 roda gigi terbaik (dengan nilai kecepatan terbesar). Untuk roda gigi dengan besaran sudut 2, kita cukup menyimpan 900 roda gigi saja. Lebih umumnya, untuk roda gigi dengan besaran sudut k, kita hanya perlu menyimpan 1800/k roda gigi. Artinya secara total, kita hanya perlu menyimpan 1800/1 + 1800/2 + … + 1800/1800 roda gigi. Berdasarkan rumus deret harmonis, kita cukup menyimpan 3600 roda gigi, atau setara dengan 2S. Dengan begitu, komputasi dynamic programming dapat diperoleh dengan kompleksitas O(S2) saja. Untuk mencari roda gigi terbaik, pendekatan greedy dengan melakukan sort bisa dilakukan. Dengan demikian, kompleksitas total untuk menyelesaikan permasalahan ini adalah O(N log N + S2).

Sejauh pengamatan saya sebagai peserta OSN dahulu kala (tahun 2008), serta pengalaman sebagai pembuat soal OSN 2 tahun terakhir, tingkat kesulitan OSN semakin meningkat. Bagi yang ingin bertanding di OSN 2015, persiapkan sebaik mungkin. Kuasai teknik-teknik yang kemungkinan besar keluar di OSN, seperti: sorting, graph traversing (BFS dan DFS), dynamic programming, teknik geometri, manipulasi string, atau teknik lainnya. Perbanyak belajar, latihan, dan tentu saja do’a!

Re-Hello world!

Something happened (technically) with my previous site, so I decided to re-create a new one. However, this blog will be focused on my competitive programming related stories and experiences.