Kisah Perjalanan di TOKI: Saya dan OSN 2009

Hingga pada waktunya liburan, saya mendapatkan informasi bahwa hasil OSP sudah dipublikasikan melalui internet. Penasaran, saya langsung memeriksanya. Hasilnya, saya berada di peringkat tiga Jakarta! Nama saya muncul di antara Rolandi, Ericko, Edrick, David, Vilberto (Vito), Gerry, Beatrice, dan Geraldi. Saya tahu mereka siapa, karena sambil pelatihan saya juga mengumpulkan informasi tentang pesaing-pesaing tangguh, tetapi mereka mungkin tidak tahu saya siapa. Saya sudah mengenal Ericko sebelumnya karena dia pernah mengajak saya makan kwetiaw (alias "ngetiaw") di belakang SMAN 112, dan Vito karena saya terkaget dia mampu menyelesaikan kubus rubik dengan cepat (waktu itu rubik belum trend).

Hari yang Semakin Mengganas
Tidak lama kemudian, datanglah email dari petinggi TOKI untuk mengikuti Pelatihan Jarak Jauh (PJJ). Pada zaman itu, PJJ masih dilaksanakan di ranau (sebelum ada tokilearning). Mulai di PJJ, saya menghadapi soal-soal pemrograman yang belum pernah saya coba sebelumnya. Beruntung karena ada bekal pengetahuan pemrograman yang saya dapat saat SMP, saya mampu bertahan hingga chapter 3 (materinya tentang rekursi) tanpa bantuan. Sesampai di chapter itu, saya diutus untuk mengikuti pelatihan daerah (pelatda) bersama dengan 8 nama lain yang saya sebutkan sebelumnya.

Kisah Perjalanan di TOKI: Saya, OSK, dan OSP

Pengalaman Ikut OSN Komputer...

Tahun demi tahun berlangsung begitu cepat. Saya yang dulu mengikuti OSN 2009 bidang komputer telah menyaksikan begitu banyak medalis dan wajah-wajah baru anggota TOKI 201#. Seperti judul di atas, saya ingin berbagi cerita tentang kisah saya di TOKI. Tulisan ini rasanya akan menjadi panjang dan berseri, karena saya menikmati pengetikannya.

Tentang Saya
Ketika mampir ke rumah teman, biasanya ada sebuah rak berisi sejumlah piala yang kelihatannya adalah bukti dari prestasi mereka. Hmm kalau yang saya ingat, beberapa di antaranya adalah lomba cerdas cermat, menyanyi, membaca puisi, atau yang lainnya.

Bagaimana dengan saya? Saya bukan orang yang rumit. Masa kecil saya banyak digunakan untuk menggambar, mencorat-coret kalender bekas tahun lalu, dan bermain nintendo. Saya tidak mengikuti kursus bernyanyi, bermain musik, melukis, matematika, atau keterampilan lainnya seperti kebanyakan teman-teman saya. Di kala teman-teman sering mendapat nilai 100, biasanya saya mendapatkan nilai 70-an. Secara rata-rata, kemampuan saya merata (lho).

Bertemu dengan Pemrograman
Pada saat saya kelas SMP 2 akhir, guru komputer di sekolah saya menyeleweng mengajarkan pemrograman Visual Basic. Alasannya karena kurikulum komputer saat itu adalah penggunaan Ms Office, yang mana sudah cukup diajarkan saat SD dan SMP 1. Hasilnya, banyak teman-teman yang protes karena bingung tentang pemrograman. Terlepas dari itu, saya menemukan bahwa pemrograman begitu menarik. Rasanya sangat alami ketika saya merancang dan menuliskan alur algoritma (meskipun saat itu hanya if, for, dsb).

Tentang Segment Tree: Variasi Nilai Agregat

Bagian yang sebelumnya menunjukkan bahwa setiap node dalam segment tree bisa saja menyimpan lebih dari satu nilai. Nilai-nilai yang disimpan dalam suatu node seperti sum dan prop pada contoh di atas disebut dengan nilai agregat.

Hal yang membuat segment tree menjadi struktur data yang serba bisa sebenarnya adalah nilai agregat ini, digabungkan dengan prinsip pembagian pertanggungjawaban. Nilai agregat ini bisa berupa apa saja, nilai maksimum, jumlahan elemennya, hasil perkalian, banyaknya pola tertentu yang muncul, subsekuens konsekutif dengan jumlahan maksimal, sebuah himpunan, dan sebagainya. Bandingkan dengan struktur data untuk menjawab dynamic range query lainnya seperti BIT, yang nilai agregatnya cukup terbatas.

Contoh berikut akan menunjukkan bagaimana nilai agregat pada node menjadikan segment tree sangat berguna. Diberikan sebuah array A. Terdapat dua macam operasi:

1. update(a, b), artinya mengubah elemen di indeks ke-a menjadi b.
2. query(a, b), artinya mencari jumlahan maksimum sekuens konsekutif yang ada di antara indeks a sampai indeks b (inklusif). Misalnya untuk [1, 4, -9, 3, 2, -1, 3, -7], jumlahan maksimum sekuens konsekutifnya ada pada [3, 2, -1, 3], yaitu 7. Kita akan menyebut subsekuens konsekutif ini subsekuens konsekutif maksimum.

Untuk persoalan ini, diharapkan kedua operasi dapat dilaksanakan lebih cepat dari O(N). Bagaimana implementasi segment tree-nya? Sekilas soal ini bahkan tidak dapat diselesaikan dengan segment tree!

Tentang Segment Tree: Lazy Propagation

Dari beberapa postingan yang saya buat, terdapat istilah lazy propagation pada segment tree. Mungkin di antara kalian ada yang belum tahu apa itu segment tree, apalagi lazy propagation. Nah untuk kalian yang belum tahu tentang segment tree, disarankan untuk membaca ulasannya di tutorial FPC Ristek Fasilkom UI.

UPDATE 1: sekarang webnya sudah musnah, termasuk tulisan-tulisan saya.
UPDATE 2: back up tulisan saya sudah dituangkan ke petunjuk coding segment tree.

Tulisan ini akan difokuskan dalam lazy propagation.

Salah satu keunggulan dari segment tree adalah kemudahannya dalam melakukan lazy propagation. Teknik ini biasanya digunakan ketika diperlukan update pada suatu interval (bukan suatu elemen). Sebagai contoh, misalkan diberikan array ar yang seluruh elemennya bernilai 0 dan sejumlah operasi:

1. update(a, b, c), yang artinya menambah isi dari ar[a], ar[a+1], ..., ar[b] dengan c.
   
2. query(a, b), yang artinya mencari jumlahan dari ar[a], ar[a+1], ..., dan ar[b].

Bila operasi update hanya dilakukan pada suatu elemen, tentunya permasalahan ini dapat dengan mudah dengan segment tree. Sayangnya, dengan update suatu interval kita tidak mungkin menginterasi setiap elemen dan melakukan update pada elemen tersebut karena kompleksitasnya akan menjadi O(N).

Solusi yang lebih baik adalah dengan melakukan update secara lazy.