Strategi Belajar CP

Kalau diingat-ingat, saya menghabiskan waktu cukup lama di pemrograman kompetitif (alias Competitive Programming/CP). Mulai dari 2009 sampai dengan 2015, yang mana sesudah itu saya pensiun. Selama 7 tahun tersebut saya menghabiskan banyak waktu untuk berlatih.

Dari beberapa cara berlatih, ada yang lebih efisien atau kurang. Mungkin bisa dianggap seperti sistem "experience" atau exp pada game. Misalnya pada game pokemon, mengalahkan dragonite memberikan exp jauh lebih banyak dari magikarp. Seandainya sejak awal saya tahu cara berlatih yang paling efisien, mungkin dengan 7 tahun saya bisa lebih jago dari saya yang sekarang.

Melalui tulisan ini, saya akan berbagi informasi cara berlatih berdasarkan pengalaman saya. Cara berlatih ini tidak saling lepas, jadi bisa dikombinasikan sesuai kebutuhan. Semoga dapat membantu kalian yang sedang menempuh perjalanan menuju OSN, IOI, regional ICPC, atau ICPC world final.

---

Latihan NonKontes (UVa, SPOJ)

Saya memulai pembelajaran CP dari latihan UVa. Setiap harinya, saya memilih beberapa soal secara acak lalu dikerjakan. Biasanya saya dapat menyelesaikan 3 soal dalam sehari. Setelah mengenal SPOJ, saya mulai berlatih di sana dengan menonton papan submission, dan memilih soal yang berkode menarik.

Ciri utama dari latihan nonkontes adalah tidak adanya batas waktu dan kebebasan dalam memilih soal. Anda boleh memilih soal sendiri, dan dikerjakan dalam jangka waktu yang ditentukan sendiri pula.

Lazy Segment Tree (Bukan Lazy Propagation)

Belakangan ini saya jadi sering menulis tentang segment tree. Berhubung masih terpikirkan, saya akan terus membagikan ilmu-ilmu aneh tentang segment tree.

Yang kali ini adalah lazy segment tree, yang berbeda dengan lazy propagation. Saya pernah menghadapi soal semacam ini, seingat saya di codeforces. Namun sayangnya tidak bisa saya temukan lagi padahal sudah mengorek-ngorek submission lama.

Inti soalnya adalah:

• Terdapat sebuah array dengan M elemen, yang mana M bisa sebesar 2 milyar.
• Pada awalnya setiap elemen bernilai 0.
• Terdapat N operasi berupa:
• U x y: artinya ubah elemen array di posisi ke-x menjadi y.
• Q x y: artinya cari elemen terbesar yang berada di antara elemen ke-x dan ke-y.
• Anda diwajibkan untuk mengerjakan operasi secara online (operasi berikutnya tidak dapat dibaca sebelum operasi saat ini dikerjakan) 

Untuk menjamin soal diselesaikan secara online, si pembuat soal mengenkripsi operasi selanjutnya dengan jawaban dari operasi 'Q' yang terakhir ditanyakan (atau 0, apabila tidak ada operasi 'Q' sebelumnya).

Seandainya soal ini boleh dikerjakan secara offline, solusinya sesederhana membaca seluruh query terlebih dahulu lalu grid compression. Meskipun terdapat 2 milyar elemen, sebenarnya hanya paling banyak 2N elemen yang mungkin disebut dalam operasi-operasinya.

---

Solusi Binary Search Tree

Solusi langsung terpikirkan adalah menggunakan BST.

Cukup simpan elemen BST berupa pasangan data <indeks, nilai>. BST ini terurut berdasarkan indeks elemen. Setiap node perlu menyimpan nilai agregat berupa nilai terbesar antar elemen-elemen subtreenya. Kini seluruh operasi dapat dilakukan dalam O(log N).

Apabila Anda belum tahu apa itu BST, cek tulisan saya sebelumnya tentang treap.

---

Solusi Lazy Segment Tree

Solusi alternatifnya adalah dengan segment tree yang node-nya bersifat "lazy". Setiap node hanya dibuat apabila dia akan diakses. Nilai agregat dari segment tree ini adalah nilai terbesar yang diwakilkan oleh suatu segmen.

Pada awalnya, kita hanya memiliki sebuah node yang mencakup elemen 1 sampai dengan M. Kita tidak perlu membuat anak kiri dan kanannya untuk saat ini. 

Kemudian untuk operasi "U x y", lakukan perubahan pada elemen ke-x seperti segment tree pada umumnya. Berhubung bisa saja terdapat node yang belum dibuat, inilah waktunya untuk membuat node tersebut. Setiap kali kita mengunjungi sebuah node yang belum memiliki anak kiri dan kanan, buat kedua anak tersebut, lalu lanjutkan operasi ke salah satu anak yang bersangkutan.

Struktur Data Range Tree Bagian 2: RMQ

Tulisan ini adalah kelanjutan dari bagian pertama tentang pengenalan range tree.

Kini kita mampu menghitung banyaknya elemen di suatu daerah persegi panjang. Operasi lainnya yang sering dibutuhkan adalah pencarian nilai terbesar, terkecil, atau bahkan jumlahan elemennya. Kita akan menggunakan contoh soal berikut:

Pada suatu lahan, terdapat N titik yang mengandung sejumlah emas. Lahan ini dapat dianggap suatu bidang 2 dimensi. Titik ke-i memiliki koordinat (xi, yi), dan memiliki kandungan emas sebanyak vi kg. Tugas kita adalah menjawab sejumlah pertanyaan berupa:

"Pada daerah yang bermula di (x1, y1) sampai (x2, y2), berapa kandungan emas terbanyak yang ada pada suatu titik di daerah tersebut?"

---

Ide Penyelesaian

Dengan ide pada tulisan sebelumnya, kita dapat membagi-bagi daerah berdasarkan sumbu x. Kemudian untuk setiap suatu rentang x, kita bagi berdasarkan sumbu y.

Untuk mendapatkan nilai terbesar di suatu daerah persegi panjang, lakukan query range tree seperti cara sebelumnya. Nilai terbesar sebenarnya sesederhana nilai terbesar dari tiap-tiap nilai terbesar di setiap daerah yang kita cari. Dengan struktur yang telah kita pelajari, pencarian nilai terbesar di suatu node range tree perlu dilakukan melalui linear search, sehingga kompleksitasnya O(N) dan kurang efisien.

Sebetulnya pencarian nilai terbesar di suatu node range tree ini mengingatkan kita pada masalah klasik, yaitu mencari nilai terbesar dari subbarisan di array alias RMQ (Range Maximum Query).

Strategi Kontes ICPC

Sepanjang berkompetisi ICPC, saya menyadari bahwa dinamika antar anggota tim penting untuk memaksimalkan performa tim. Maksimal di sini berarti berkompetisi sebaik mungkin, sehingga apapun hasil yang didapatkan, tidak ada kekecewaan. Tulisan ini akan membagikan pengalaman saya sepanjang 4 tahun berkompetisi di ACM ICPC.

Perlu diingat bahwa tulisan ini sangat subjektif, yaitu berdasarkan pengalaman saya. Yang Anda alami mungkin berbeda, dan yang saya tuliskan hanya sebagai referensi saja.

---

Komposisi Tim

Tim yang ideal adalah tim yang anggotanya saling melengkapi. Ada anggota yang mampu mengerjakan soal tipe X, ada yang mengerjakan soal tipe Y, dan sebagainya. Namun setiap anggota sebaiknya menguasai seluruh ilmu dasar.

Storm, earth, dan fire dari warcraft (https://blizzardwatch.com)

Ilmu yang setidaknya harus dimiliki setiap anggota adalah coding. Jelas bahwa setiap anggota pasti sudah bisa coding, tetapi yang saya maksud di sini adalah setiap anggota mampu menuliskan kode dengan lancar, minim bug, dan mudah dibaca anggota lainnya. Bila tim membebankan pekerjaan coding ke seorang anggota, maka ia kemungkinan besar akan jenuh, lelah, dan hanya berperan sebagai kuli. Tanpa berperan dalam berpikir mencari solusi, anggota ini bisa saja merasa tidak dihargai...

Buku Pemrograman Kompetitif Dasar Dirilis!

Seperti yang sudah saya sempat bocorkan sebelumnya, saya dan teman-teman dari IA TOKI mempersiapkan materi pembelajaran yang baru.

Materi ini adalah buku yang berjudul "Pemrograman Kompetitif Dasar", atau disingkat PKD.

PKD ini dibuat dengan bahan dasar berupa slide-slide materi di TLX Training Gate yang sebelumnya telah ditulis. Slide-slide ini tidak hanya sekedar dibukukan, sebab banyak bagian yang sebelumnya sulit dipaparkan lewat slide kini dijelaskan lebih mendalam lewat narasi. Terdapat pula 2 bab tambahan, yaitu struktur data nonlinear dan algoritma graf.

 

Tampilan dalam PKD

Buku ini sekarang tersedia dalam bentuk elektronik, Anda dapat mengunduhnya secara gratis di link pada akhir tulisan. Apakah akan ada versi cetaknya? Saya belum tahu. Untuk hal itu mungkin perlu menanti perkembangan yang lebih lanjut, berhubung mencetak dan mendistribusikan buku terlihat seperti pekerjaan yang tidak mudah.

Bagi kalian yang haus akan ilmu dan sedang dalam persiapan OSN komputer, silakan membaca buku ini dan jangan lupa untuk disebarluaskan kepada siapapun yang juga membutuhkan buku ini. Semoga bermanfaat!

[baca selengkapnya di sini]

Riset Belajar OSN Komputer

Beberapa bulan yang lalu, saya sempat kembali aktif menulis. Namun kemudian saya kembali menghilang. Sebenarnya selama saya menghilang, banyak yang saya kerjakan berkaitan dengan competitive programming.

Jadi sekitar bulan September, saya menjadi panitia Gemastik 2017 bagian lomba pemrograman, yang kala itu tuan rumahnya di Universitas Indonesia. Tahun 2016 juga tuan rumahnya UI, tetapi saya sedang mengerjakan proyek dan sibuk membantu seleksi tim inti ACM-ICPC untuk UI. Jadilah saya tidak membantu. Tahun 2017, berhubung saya sudah lebih luang dan sekaligus balas budi kepada UI, saya ikutlah menjadi panitia.

Setelah Gemastik berakhir, saya diajak Aji yang tiba-tiba mau mengurus konten untuk TOKI. Sejauh ini konten TOKI yang saya kerjakan adalah materi TLX Training Gate, yang sudah dimulai sejak 2014. Aji mengajak saya untuk melakukan riset apakah sebenarnya materi dan soal latihan TLX Training Gate ini benar-benar bermanfaat. Sebelumnya saya tidak pernah terpikirkan tentang aspek ini, jadi hanya sekedar menulis saja.

Setelah mendapat hasil kuesioner di grup Facebook Olimpiade Informatika Indonesia, kami menyimpulkan bahwa masih banyak orang yang tidak tahu tentang pembelajaran pemrograman kompetitif di Indonesia. Solusinya adalah dengan membuat 1 halaman situs berisi kumpulan informasi pembelajaran yang singkat, padat, jelas, dan sistematis.

Bersama-sama dengan Mamat dan Fairuzi, kami akhirnya membuat:

https://osn.toki.id/

Seperti yang telah dijelaskan, situs ini adalah 1 halaman berisi kumpulan informasi untuk mulai belajar menuju OSN komputer. Belajar ini maksudnya mulai dari OSK, OSP, sampai OSN komputer. Yang terpenting adalah tulisannya disusun dengan sistematis, jadi tidak bingung dengan sumber pembelajaran yang saat ini berceceran. Seluruh sumber pembelajaran yang dicantumkan dapat diakses secara gratis.

Selain pembuatan situs itu, kami juga menyiapkan konten baru untuk pembelajaran OSN. Konten ini disesuaikan juga dengan hasil riset sebelumnya. Informasi lebih lanjut akan saya berikan ketika konten ini sudah selesai.

Selamat memulai belajar menuju OSN komputer!