Terasi (bagian 1): Proyek Analitik Transjakarta

Seri tulisan kali ini tidak ada hubungannya langsung dengan pemrograman kompetitif. Namun, saya menggunakan sejumlah ilmunya dalam perjalanan yang akan saya ceritakan berikut.

Setelah lulus dari perguruan tinggi, saya kerja di Cermati. Kantornya di dekat mall Central Park, Jakarta Barat. Kebetulan lokasinya sangat strategis, terdapat halte Transjakarta di dekatnya. Saya pikir untuk pergi dan pulang ke kantor menjadi sesederhana naik Transjakarta saja. Namun sebenarnya tidak sesederhana itu...

Waktu itu adalah tahun 2015. Saya tidak tahu apakah sekarang situasinya sudah membaik, tetapi kondisi lalu lintas tahun itu cukup mengenaskan. Daerah Jalan S. Parman terkenal sangat macet pada jam masuk atau pulang kantor. Awalnya saya pikir ada busway (jalur Transjakarta), yang membuat Transjakarta kebal kemacetan. Sayangnya, ternyata di Jalan S. Parman terdapat penyatuan busway dengan jalan raya yang membuat bus ikut kena macet...

Akibat dari kemacetan ini adalah:

1. Pergerakan bus menjadi lambat, sehingga...
2. Frekuensi kedatangan bus menjadi rendah, sehingga...
3. Orang yang mengantre di halte menjadi ramai, sehingga...
4. Begitu bus sampai di halte, tidak semua orang kedapatan menaiki bus, sehingga...
5. Harus menunggu kedatangan bus berikutnya, sehingga...
6. ... tekanan darah saya meningkat karena perjalanan dari rumah ke kantor menjadi lama.

Seluruh akibat itu saya rasakan setiap hari, ditambah dengan setiap kali naik TJ (Transjakarta) untuk jalan-jalan di Jakarta. Hingga suatu ketika saya muak, dan menjadi marah. Bagaimana mungkin fasilitas umum untuk masa depan beroperasi seperti ini?

Akhirnya energi amarah yang meluap-luap itu saya alirkan ke ide untuk membuat sistem yang dapat menghitung metrik-metrik Transjakarta, seperti waktu tunggu, waktu perjalanan dari halte ke halte, rata-rata kedatangan bus, dan sebagainya. Dengan metrik tersebut, saya dapat mengukur apakah untuk suatu perjalanan saya akan menggunakan Transjakarta. Apabila ternyata data menunjukkan perjalanannya akan memakan waktu lama, lebih baik saya naik ojek.

Struktur Data Dynamic Range Query

Tanpa terasa saya sudah membahas banyak struktur data dynamic range query. Tulisan ini akan menjadi rangkuman semuanya dan menjadi peta bagi kalian yang hendak mempelajarinya.

---

Technology Tree

Intermezzo:

Kalau kalian pernah bermain game berjenis Real Time Strategy (RTS), mungkin tahu tentang konsep "technology tree". Biasanya Anda akan memainkan satu peradaban yang dimulai dengan teknologi seadanya. Seiring dengan berjalannya waktu, Anda dapat melakukan riset untuk memajukan teknologi dan meningkatkan produktivitas. Ditemukannya suatu teknologi juga memungkinkan pembuatan sejumlah teknologi lain. Contohnya pada game Age of Empires, pembuatan kandang hewan akan memungkinkan dibuatnya cavalry dan pemanah berkuda.

Oke cukup dengan cerita game. Pembelajaran struktur data pun dapat digambarkan seperti sebuah technology tree. Mempelajari suatu struktur data memungkinkan Anda untuk belajar sejumlah struktur data lainnya. Berikut adalah gambarannya:

Klik untuk memperbesar gambar.

Semuanya dimulai dengan array. Dengan array polos, kita dapat melakukan apa saja walaupun secara kurang efektif. Lalu saya tidak mengikutkan keluarga struktur data linear seperti stack/queue/deque, dan juga keluarga heap.

Anak panah menunjukkan bahwa setelah mempelajari suatu konsep (struktur data/teknik), Anda dapat beranjak ke konsep yang lebih lanjut.

Petunjuk Coding: Segment Tree Lazy Propagation

Setelah menguasai penulisan kode segment tree yang melayani update sebuah elemen dan range query, kini waktunya beranjak ke operasi yang lebih sulit: range update.

Perkenalan tentang penanganan range update dengan lazy propagation pernah saya bahas di tulisan yang lalu. Pada tulisan ini, kita akan fokus ke implementasinya.

---

Konsep

Lazy propagation dapat diimplementasikan ketika:

1. Apabila seluruh elemen yang dicakupi sebuah segmen mendapatkan update, maka update harus disangkutkan pada segmen tersebut dengan efisien & tanpa menyentuh anak-anaknya.
2. Apabila seluruh elemen yang dicakupi suatu segmen diperlukan dalam query, maka informasi asli dari segmen itu harus bisa didapatkan dengan efisien & tanpa menyentuh anak-anaknya.

Apabila kedua syarat itu dipenuhi, maka lazy propagation dapat diterapkan. Setiap range update atau query dapat dilaksanakan dalam O(log N).

Untuk keperluan penjelasan, nilai yang disangkutkan akan saya sebut "nilai lazy".

Penjelasan tentang cara implementasi akan dijelaskan melalui studi kasus 1 pada bagian selanjutnya. Kita juga akan mengambil abstraksi kode lazy propagation dari sana, untuk diterapkan pada studi kasus seterusnya.

Petunjuk Coding: Segment Tree

Sebenarnya tulisan ini mau difokuskan ke implementasi segment tree. Tapi karena tulisan saya sebelumnya di ristekfasilkom.com sudah musnah (hosting-annya habis), jadinya saya kembalikan back-up tulisannya ke sini.

Segment tree merupakan struktur data yang biasa dipakai untuk menjawab dynamic range
query, yaitu sejumlah operasi yang dilakukan dengan rentang yang bervariasi. Selama tidak ada penyisipan atau penghapusan elemen, segment tree hampir selalu bisa digunakan. Tulisan ini akan membahas tentang konsep struktur data ini dan cara implementasinya.

---

Permasalahan Motivasi

Diberikan sebuah array integer dan serangkaian operasi.
Sebut saja array itu adalah ar. Operasi-operasi yang diberikan bisa berupa:

• update(x, v), yang artinya mengubah isi ar[x] menjadi v.
• query(x, y), yang artinya mencari nilai minimum dari ar[x], ar[x+1], ..., ar[y].

Dengan cara naif, update dapat dilaksanakan dalam O(1). Sementara query dapat dilaksanakan dalam O(N), dengan N adalah panjang array. Tentunya cara ini kurang efisien, khususnya jika N cukup besar dan operasi yang diberikan cukup banyak.

Dengan segment tree, kita dapat melakukannya dengan lebih baik.

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!