Tentang Pembuatan Soal Competitive Programming

Pada kesempatan kali ini, saya akan membagikan bagaimana cara pembuatan soal menurut pengalaman-pengalaman yang saya saksikan atau saya alami sendiri. Karena pengalaman itu tidak saya dokumentasikan, saya tidak bisa menyebutkan sumbernya satu per satu. Orang yang mungkin terlibat dalam tulisan ini adalah Ashar, Brian, Chris, Felix, Karol, Suhendry, Reinhart, atau Risan.

Perlu diperhatikan bahwa tulisan ini tidak menyatakan hal yang wajib Anda lakukan, karena tulisan ini hanya didasarkan pada pengalaman pribadi saya.

Fokus utama dari tulisan ini adalah jenis soal batch. Bila Anda belum tahu apa itu soal batch, coba perhatikan jenis-jenis soal berikut:

1. Batch: diberikan berkas masukan yang sifatnya rahasia, rancang algoritma sehingga menghasilkan keluaran seperti yang diinginkan soal. Algoritma harus memenuhi batasan tertentu seperti batas waktu dan memori.
2. Interactive: rancang algoritma untuk berinteraksi dengan program grader untuk suatu tujuan tertentu. Misalnya tebak angka, bermain game, atau adu strategi.
3. Output only: diberikan berkas masukan. Rancang algoritma untuk menghasilkan keluaran seperti yang diinginkan soal. Yang kita kumpulkan adalah berkas keluaran yang dihasilkan. Bedanya dengan batch adalah sifat testcase yang tidak rahasia dan tidak ada batasan waktu atau memori (karena yang dikumpulkan adalah berkas keluarannya).

Bagaimana Kriteria Soal yang Bagus?
Saya tidak tahu jawaban pastinya. Menurut saya, ketika seseorang yang berhasil menyelesaikan soal itu mampu mengatakan "soal ini keren!", maka soal itu bagus. Soal yang bagus biasanya memerlukan analisis mendalam, tidak straight-forward, dan tidak menimbulkan rasa malas bagi peserta untuk mengerjakannya.
Soal yang bagus tidak harus sulit. Soal mudah sendiri juga bisa menjadi bagus apabila algoritma atau analisis yang diperlukan tidak "membosankan". Sebagai contoh, perhatikan dua soal berikut:

1. Diberikan dua buah array. Temukan nilai terkecil dan nilai terbesar untuk setiap array!
2. Diberikan sejumlah kambing di posisi (xi, yi). Kita hendak membuat sebuah kandang berbentuk persegi panjang dengan sisi sejajar sumbu x atau y yang sekecil mungkin untuk melingkupi semua kambing. Tentukan di mana saja kita perlu meletakkan titik sudut persegi panjang itu!

Kedua soal itu memerlukan algoritma yang sama, yaitu mencari nilai terkecil dan terbesar untuk setiap array. Meskipun sama-sama mudah, soal kedua lebih menarik daripada soal pertama.
Biasanya, soal-soal yang keluar di USACO contest atau kontes ACM-ICPC regional Jakarta merupakan soal yang bagus. Saya sendiri selalu mengagumi soal-soal yang dikeluarkan mereka.

Tahap 1: Ide Soal
Bagaimana mendapatkan ide soal? Anda butuh inspirasi. Memang tidak mudah untuk mendapatkan inspirasi, tetapi inspirasi bisa datang dari mana saja. Coba lihat kondisi sekitar Anda, mungkin Anda bisa mendapatkannya. Sebagai contoh, ketika saya sedang berada di kendaraan umum dan ingin mencari inspirasi, saya akan mendengarkan percakapan orang atau barang-barang yang mereka bawa. Anda juga dapat melakukan brain-storming entah dengan menuliskan ide-ide di kertas, menggambar, atau membayangkannya.

Seringkali ada pertanyaan: "Mulai dari solusi dulu bari dibuat soal, atau dari soal dulu baru dicari solusinya?"
Pertanyaan semacam ini juga pernah hinggap di pikiran saya. Pada masa-masa awal "lulus" dari TOKI, saya menggunakan teknik yang pertama: solusi dulu, soal kemudian. Saya berusaha memadukan beberapa algoritma untuk menghasilkan sebuah solusi, lalu merancangnya menjadi sebuah soal. Misalnya, saya berpikir "ah pengen bikin soal binary search, trus pake BFS". Kemudian saya berpikir apa yang bisa di-binary search. Apakah bobot dari suatu edge? Apakah banyaknya node yang boleh dilewati? Baru setelah diputuskan, soal dapat dibuat. Beberapa soal TOKI Open Contest yang saya buat menggunakan metode ini.
Setelah membuat beberapa soal tersebut, saya menyadari ada "lubang" dari soal-soal itu. Yaitu solusinya yang straight-forward. Entah karena alasan apa, tetapi soal-soal itu mudah untuk dikerjakan dan algoritmanya bisa langsung ketahuan tepat setelah selesai membaca soal. Mungkin penyebabnya adalah pada saat pembuatan soal, kita sudah memikirkan "pakai algo ini, lalu algo itu". Akibatnya saat dituangkan ke soal, pikiran kita sudah terarahkan untuk "algo ini, lalu algo itu".
Memasuki akhir tahun 2012, saya mencoba metode yang kedua: soal dulu, solusi kemudian. Saya mulai memikirkan "bagaimana kalau ada soal kayak gini ya, hmm. mungkin solusinya adalah ..."
Di dalam pemikiran tersebut, proses brain-storming benar-benar terjadi. Kita berusaha mencari jawaban atas permasalahan yang kita buat sendiri. Bisa saja muncul pemikiran seperti "eh kalau soalnya diubah dikit jadi begini, rasanya lebih enak dikerjain, soalnya lemma ini bisa berlaku ...". Sambil mengutak-atik soal itu, kita sedang merancang soal yang memerlukan analisis mendalam. Oleh karena itu, menurut saya soal yang dihasilkan dari metode ini biasanya tidak straight-forward (bahkan kita sendiri saja sedang menganalisisnya).
Mengenai bagaimana cara menghasilkan soal, rasanya setiap orang memiliki preferensinya masing-masing. Sama halnya dengan DP, apakah Anda hendak mengimplementasikannya secara top-down? Atau bottom-up? Oleh karena itu gunakan cara yang menurut Anda nyaman.

Tahap 2: Penulisan Solusi
Jika persoalan sudah dibuat, saatnya kita membuat solusinya. Isu yang biasanya dikhawatirkan bagi pembuat soal adalah "apakah solusi saya benar?".
Untuk mengatasinya, kita dapat menggunakan alternatif berikut:

1. Buat beberapa berkas masukan, lalu gunakan algoritma brute force yang pasti menghasilkan jawaban benar untuk menghasilkan berkas keluarannya. Bandingkan berkas keluaran dari algoritma brute force dengan algoritma Anda. Jika hasilnya sama, kemungkinan besar algoritma Anda benar.
2. Meminta orang lain yang bisa menjaga rahasia untuk mengerjakan soal Anda. Bandingkan bagaimana algoritma yang dia gunakan dengan yang Anda gunakan.
3. Cari alternatif solusi lain yang juga benar, lalu bandingkan keluarannya.

Tahap 3: Penulisan Soal
Setelah mendapatkan inspirasi soal, analisis, dan solusinya (yang pasti benar), kita bisa mulai menuliskannya ke dalam soal.
Komponen utama dari soal batch adalah:

1. Berkas soal, terdiri dari:
   
   1. Batasan waktu/memori
      Batasan ini harus ada, terutama untuk waktu (kadang-kadang tidak ada batas memori). Tanpa ini, peserta tidak tahu apakah algoritma yang mereka gunakan bisa berjalan di bawah batas waktu.
   2. Deskripsi soal
      Merupakan bagian vital dari soal. Deskripsi soal dapat Anda tuliskan dengan gaya menulis masing-masing, entah gaya matematis, gaya humoris, atau mungkin gaya serius. Hal yang perlu diperhatikan adalah:
      
      1. Tujuan dari deskripsi soal adalah memberikan gambaran kepada peserta persoalan apa yang perlu dia selesaikan. Oleh karena itu menggunakan kalimat yang berbelit-belit atau menyembunyikan suatu informasi dari deskripsi soal rasanya kurang bijak untuk dilakukan.
      2. Setiap kalimat dalam soal hendaknya bermakna dan menyimpan suatu informasi. Hindari tambahan kalimat yang sifatnya nyampah, tidak berguna, dan membuat peserta membuang-buang waktunya hanya untuk membaca bagian tersebut.
      3. Bila Anda memerlukan terminologi seperti graph atau matrix di dalam soal, padahal target peserta untuk soal ini kemungkinan besar belum mempelajarinya, Anda dapat menyembunyikan kata-kata tersebut. Misalnya graph menjadi kota dan jalan, matrix menjadi petak-petak sawah, tree menjadi struktur atasan-bawahan dalam perusahaan, atau semacamnya.
      4. Definisikan setiap informasi yang tidak umum dalam soal Anda. Misalkan Anda meminta peserta untuk menghitung berapa banyak kejadian "mengintip". Anda harus mendefinisikan kejadian "mengintip" itu terjadi saat kondisi apa saja dengan jelas.
      5. Deskripsi soal hendaknya mengikuti aturan tata bahasa yang benar dan dirancang sedemikian rupa sehingga dalam sekali membaca, peserta mengerti maksud soalnya.
      6. Deskripsi soal hendaknya bermoral. Hindari adanya unsur-unsur seperti perjudian, minuman keras, obat-obatan terlarang, amukan, mengandung isu SARA. Hindari juga unsur-unsur yang dapat memicu persoalan seperti hal-hal berbau politis. Jangan sampai hanya karena soal kita disangka melakukan kampanye terselubung.
   3. Format masukan dan keluaran
      Bertujuan untuk menjelaskan bagaimana Anda menyajikan berkas masukan dan keluaran. Jelaskan sebagaimana Anda rasa orang dapat mengerti penjelasan Anda. Bila Anda berbaik hati, sajikan berkas masukan dalam format yang "ramah" sehingga peserta tidak perlu melakukan parsing yang merepotkan.
   4. Contoh masukan dan keluaran
      Bertujuan untuk memperlihatkan bagaimana masukan dan keluaran disajikan dan memberikan klarifikasi atas format yang diberikan. Jika pembuat soal berbaik hati, kasus-kasus tricky juga diberikan melalui contoh ini. Sementara itu, jika si pembuat soal tidak bermurah hati, persiapkan peserta untuk melihat contoh masukan-keluaran yang "sangat" membantu.
      Bagian ini mungkin disertakan juga dengan penjelasan contoh masukan - keluaran
   5. Batasan
      Setiap variabel yang Anda sampaikan di bagian deskripsi perlu dijelaskan batasannya. Tujuannya agar peserta dapat mendeklarasikan array sesuai yang dibutuhkan, mengukur runtime program, dan mengukur penggunaan memori. Kadang-kadang bagian ini disatukan dengan deskripsi soal.
2. Berkas kasus uji, biasa disebut dengan testcase. Terdiri dari pasangan-pasangan testcase input dan output.
   Berkas kasus uji Anda diharapkan dapat mencakup keseluruhan kasus yang mungkin ada. Setidaknya, diperlukan input untuk ukuran maksimal, minimal, acak, dan beberapa kasus tricky yang bisa dibuat secara manual.
   Berkas ini harus Anda periksa kebenaran format penyajiannya, terutama berkas masukan. Anda dapat membuat program untuk memverifikasi apakah penyajiannya sudah sesuai dengan format masukan dan mematuhi batasan yang diberikan. Sekali lagi, bagian ini wajib untuk dikerjakan.
   Ukuran dari kasus uji perlu Anda sesuaikan dengan peluang soal itu akan dikerjakan oleh peserta, batas waktu, dan kemampuan server/grader. Bila soal itu akan sering dikerjakan oleh peserta (karena mudah) dan kemampuan server sangat terbatas, jangan buat berkas yang besar (misalnya lebih dari 10 MB). Dikhawatirkan server akan down karena terlalu berat melakukan grading.
   Kadang kala berkas masukan kita terpaksa harus besar, karena memang batasan pada soal menuntut masukan yang banyak. Untuk menghemat ukuran berkas, Anda dapat melakukan kompresi. Misalnya untuk masukan berupa matriks yang berisi hanya angka 1 atau 0, gunakan segmentasi setiap 8 angka menjadi sebuah karakter.

Tahap 4: Waktu Kontes
Selama kontes berlangsung, Anda harus mewaspadai adanya masalah dalam soal. Sebenarnya bagian ini sifatnya tidak wajib. Lagipula, seorang pembuat soal yang baik seharusnya dapat memastikan bahwa tidak ada masalah dalam soalnya. Namun tidak menutup kemungkinan bahwa soal-soal yang dibuat mengalami kesalahan. Oleh karena itu tahapan ini mungkin diperlukan untuk mengatasi kesalahan-kesalahan itu.
Setiap pengumpulan baik yang accepted, wrong answer, time limit, atau yang lainnya perlu Anda periksa. Berikut penanganannya:

• accepted, pastikan solusi yang digunakan oleh peserta memang benar. Jika ternyata solusi peserta seharusnya salah, maka Anda mungkin berpikir untuk menambah berkas kasus uji yang dapat mengacaukan solusi peserta itu.
• wrong answer, pastikan berkas kasus uji memang benar. Mungkin saja ada salah format, salah batasan, atau bahkan solusi Anda memang menghasilkan jawaban yang salah. Yang dikhawatirkan adalah solusi peserta seharusnya benar, tetapi solusi Anda yang salah.
• time limit, periksa apakah kasus ujinya terlalu "kejam", hingga perbedaan konstanta kecil yang seharusnya tidak signifikan malah berakibat fatal.
• runtime error, perksa apakah ada kesalahan batasan pada kasus uji Anda.

Tahap 5: Selesai Kontes
Setelah kontes berakhir, Anda dapat memutuskan untuk menyimpan soal tersebut atau mempublikasikannya. Menyimpan soal bertujuan untuk menggunakannya kembali beberapa periode mendatang. Perilaku ini berguna, salah satunya ketika Anda adalah pengajar. Karena membuat soal bagus merupakan pekerjaan yang tidak mudah, Anda dapat mempersingkat waktu dengan menggunakan kembali soal-soal lama.
Soal yang telah dibuat ini juga memiliki kemungkinan untuk dimodifikasi dan menghasilkan soal baru yang lebih baik lagi.

NB: tulisan ini bisa berubah sewaktu-waktu. Terakhir direvisi 19 Februari 2015.