Sabtu, 09 Mei 2020

Petunjuk Coding: Operasi Bit

Beberapa tulisan saya menyinggung tentang operasi pada bit, seperti pada struktur data Binary Indexed Tree dan teknik optimisasi konstanta. Tulisan ini akan membahas semua yang saya ketahui tentang operasi bit. Menguasainya akan membantu Anda dalam implementasi solusi.


Representasi Bit

Komputer merepresentasikan angka dalam bentuk bilangan basis 2, atau nama lainnya binary/biner. Representasi ini hanya memiliki angka 0 atau 1.
Sebuah digit pada bilangan biner disebut dengan bit.
Sebagai catatan, bilangan yang kita biasa gunakan adalah basis 10, dengan digit berkisar antara 0 sampai 9.

Perhatikan contoh bilangan biner berikut:
1001101

Digit paling kanan menyatakan banyaknya \(2^0\), digit kedua dari kanan menyatakan banyaknya \(2^1\), dan seterusnya. Kita dapat mengetahui nilai bilangan tersebut dalam basis 10 dengan menjumlahkan seluruh nilai yang dinyatakan setiap bit:
1 * 2^0 =  1
0 * 2^1 =  0
1 * 2^2 =  4
1 * 2^3 =  8
0 * 2^4 =  0
0 * 2^5 =  0
1 * 2^6 = 64
         ---- +
          77
Kini kita tahu hubungan antar representasi bilangan biner dan basis 10. Hubungan ini hanya berlaku untuk bilangan bulat (integer). Kita tidak membahas tentang bilangan riil, karena bentuk representasinya bergantung pada konteks.

Cara serupa dapat digunakan untuk mengubah bilangan basis 10 ke basis 2. Namun, ada algoritma yang lebih praktis:

Prinsip kerja algoritma ini akan Anda ketahui setelah memahami operasi shift right yang akan dibahas di bawah.

Minggu, 03 Mei 2020

Pembahasan Final JOINTS PCS 2019

Tulisan terakhir dari seri pembahasan JOINTS PCS 2019.
Soal-soalnya dapat dilihat dan dicoba di https://tlx.toki.id/problems/joints-2019-pcs-final.


Coin Exchange 2

Solusinya mirip dengan soal Coin Exchange pada penyisihan. Cukup coba iterasi dari \(N/2\) menuju ke 2. Begitu ditemukan nilai yang FPB-nya dengan \(N\) sama dengan 1, hentikan pencarian dan cetak jawaban.


Dolan 2020

Pertama, sederhanakan soal dengan menganggap suatu sel berisi 'P' sama dengan 5 sel berisi 'L':
.....       .....
.....       ..L..
..P..   =   .LLL.
.....       ..L..
.....       .....

Sekarang tugas kita tinggal mencari persegi panjang yang sepenuhnya hanya terdiri dari 'O'.
Apabila diproses baris per baris, sadari bahwa soal ini menjadi mirip dengan suatu soal klasik: diberikan sebuah histogram, cari luas persegi panjang terbesar yang sepenuhnya dikandung histogram tersebut.

Misalkan kita memiliki konfigurasi berikut dan sedang memproses baris ketiga. Supaya lebih mudah dilihat, tanda titik menyatakan 'O'.
LL.L..L.
.L....LL
....L...

Dari baris ketiga, struktur ini dapat dipandang seperti histogram berikut, dengan 'X' menyatakan bagian dari batangan histogram.
  X  X
X XX X  
XXXX XXX

Terdapat algoritma \(O(N)\) untuk mencari luas persegi panjang terbesar di dalam histogram dengan \(N\) batangan. Idenya adalah untuk setiap batangan pada histogram dengan tinggi \(h\), cari indeks sekiri dan sekanan mungkin sehingga seluruh ketinggian batangan histogram di antara keduanya \(\ge h\). Bila kedua indeks tersebut adalah \(a\) dan \(b\), berarti luas persegi panjang dengan panjang \(h\) dan lebar \((b-a+1)\) menjadi kandidat solusi.
Ilustrasi persegi panjang terbesar yang muat dan setinggi batangan yang berwarna gelap.
Mencari indeks terkiri dan terkanan untuk setiap batangan dapat dilakukan secara efisien dengan bantuan monotonic stack. Gunakan saja stack biasa, yang menyimpan indeks batangan. Syarat khusus yang menjadikannya monotonic adalah tinggi batangan untuk setiap indeks dalam stack wajib menaik.

Kamis, 30 April 2020

Pembahasan Semifinal JOINTS PCS 2019

Soalnya dapat Anda cek di https://tlx.toki.id/problems/joints-2019-pcs-semifinal.
Seperti biasa, coba kerjakan sendiri dulu sebelum membaca tulisan ini.


Coin Exchange

Maksud soal ini adalah mencari nilai terkecil dan terbesar yang berada di antara 1 dan N (eksklusif), sehingga nilai tersebut saling prima dengan N. Sebenarnya kondisi ini tidak menjamin seluruh nilai tukar bisa direpresentasikan. Misalnya untuk N=100, nilai terkecil yang saling prima dengannya adalah 3. Meskipun demikian, kita tidak bisa menggunakan 100 dan 3 untuk transaksi senilai 1, 2, 4, 5, 7, 8, dsb.

Untuk mencari bilangan yang saling prima, cukup periksa dari 2 sampai N-1 untuk bilangan yang FPB-nya dengan N sama dengan 1. Begitu ditemukan, langsung hentikan pencarian. Nilai inilah yang menjadi nilai terkecil. Lakukan cara serupa dengan pencarian dari N-1 sampai 2 untuk mencari nilai terbesarnya. Terakhir, cetak selisih mereka.

Solusi ini terkesan \(O(N)\), tetapi sebenarnya jauh lebih cepat dari itu. Sebab sangat besar kemungkinan \(N-k\) untuk \(k\) yang cukup kecil mengakibatkan FPB-nya dengan N sama dengan 1. Sebagai contoh, nilai 99 sudah saling prima dengan N=100. Demikian pula 1000000 dan 999999.


Hitung Kata

Ini soal DP yang cukup sederhana. Idenya seperti longest common subsequence (LCS), tetapi kali ini seluruh karakter di string kedua wajib dicocokkan. Apabila berhasil dicocokkan, tambahkan kemungkinan jawaban dengan 1.

Misalkan kedua string memiliki indeks yang dimulai dari 1. Seperti pada LCS, kita proses karakter demi karakter dari belakang.
Jika \(f(i, j)\) menyatakan banyaknya subsequence dari \(S[1..i]\) yang sama dengan \(P[1..j]\), maka pilihannya adalah:
  • Buang \(S[j]\), sehingga banyaknya cara pencocokan menjadi \(f(i-1, j)\).
  • Cocokkan \(S[i]\) dengan \(P[j]\), sehingga banyaknya cara pencocokan mejadi \(f(i-1, j-1)\). Pilihan ini hanya tersedia kalau \(S[i] = P[j]\).
Base case dicapai apabila:
  • \(j\) bernilai 0, yang artinya pencocokan berhasil.
  • \(i\) bernilai 0, tetapi \(j\) bukan 0, yang artinya pencocokan tidak berhasil.
Secara matematis, bisa dituliskan:
\[ f(i,j) = \left\{\begin{array}{ll}
1 & ,j = 0\\
0 & ,i=0 \land j>0\\
f(i-1,j) + f(i-1,j-1) & ,S[i]=P[j]\\
f(i-1,j) & ,S[i] \ne P[j]\\
\end{array}\right. \]
Sebelum mengimplementasikannya, saya menyadari kalau tidak ada modulo. Lalu saya bertanya-tanya apakah jawabannya muat ditampung dalam integer 64 bit. Jawaban terbesar dicapai apabila \(S\) berisi 'A' sebanyak 1000 karakter, dan \(P\) berisi 'A' pula sebanyak 10 karakter. Jawabannya adalah 1000 kombinasi 10, yang mana melebihi batas atas integer 64 bit.

Karena malas menggunakan big integer, saya coba submit saja. Ternyata accepted :))
Kompleksitas solusi ini \(O(|S||P|)\).


Kerja Pak Blangkon

Observasi yang penting adalah setiap pekerjaan dapat diselesaikan dalam 1 hari, sehingga pekerjaan yang lebih menguntungkan pasti dipilih terlebih dahulu.

Senin, 27 April 2020

Pembahasan Penyisihan JOINTS PCS 2019

Sempat ada laporan kalau ada masalah konfigurasi di soal-soal JOINTS 2019 yang dipasang di TLX. Sambil diperbaiki satu per satu, saya sekalian membaca soalnya. Berhubung soal-soalnya menarik, jadinya saya kerjakan dan akan saya bahas di sini.

Soalnya dapat Anda temui di web TLX: https://tlx.toki.id/problems/joints-2019-pcs-penyisihan

Sangat dianjurkan bagi Anda untuk mencobanya terlebih dahulu. Kalau tersendat baru liat pembahasan di sini :-)

Kode solusi saya cantumkan di akhir tulisan.


Dolan 2019

Deskripsi soal inilah yang membuat saya tertarik mengerjakan seluruh set soal.

Cukup proses setiap barisnya satu per satu sambil mencatat kategori jawaban terbaik sejauh ini. Supaya mudah, kodekan kategori jawaban sebagai berikut:
0. BALIK AJA
1. TERPAKSA
2. SENANG

Awalnya inisialisasi kategori jawaban dengan 0 (untuk "BALIK AJA"). Untuk setiap baris, lakukan iterasi dari kiri ke kanan sambil mencatat:
  1. Karakter terakhir sebelum 'O'. Simpan karakter ini di variabel "prev".
  2. Banyaknya karakter 'O' konsekutif sampai sejauh ini. Anggap banyaknya ini disimpan di variabel "count".
Setiap kali ditemukan karakter yang bukan 'O', simpan karakter itu di variabel "next" dan periksa apakah:
  1. count ≥ N+2. Kalau iya, berarti geng CJ pasti bisa "SENANG".
  2. count ≥ N+1. Kalau iya, periksa apakah salah satu dari prev atau next bernilai 'L'. Kalau iya berarti mereka  "SENANG", dan kalau tidak berarti kategori 1 menjadi kandidat jawaban.
  3. count = N dan nilai dari prev dan next sama-sama 'L'. Kalau iya berarti "SENANG", dan kalau tidak berarti kategori 1 menjadi kandidat jawaban.
Jangan lupa melakukan pemeriksaan kalau sudah mencapai ujung kanan kolom dan karakternya masih juga 'O'. Asumsikan saja next bernilai 'L'.

Terakhir, tinggal cetak kategori jawaban terbaik. Kompleksitas solusinya \(O(RC)\).


KPK

Solusi brutal jelas akan mendapat TLE, berhubung \(3^N\) dengan \(N=10^6\) terlalu besar.

Pertama, coba kita cari KPK dari suatu bilangan \(x\) dengan \(3^N\). Kita dapat menyatakan \(x\) sebagai perkalian dari suatu bilangan \(k\) dengan \(3^p\), sedemikian sehingga \(k\) tidak lagi mengandung faktor 3:
\[x = k 3^p\]
Mengingat masa SD, KPK dari \(k 3^p\) dan \(3^N\) adalah \(k 3^N\).
Bila \(x\) dimulai dari 1 sampai dengan \(3^N\), maka nilai yang ingin dicari adalah:
\[ \begin{array}{c} k_1 3^N + k_2 3^N + k_3 3^N + ... + k_{3^N} 3^N
\\ = 3^N (k_1 + k_2 + k_3 + ... + k_{3^N} ) \end{array} \]

Jumat, 20 Desember 2019

ICPC 4 Tahun

Setelah menceritakan pengalaman menuju OSN/IOI, kini saya akan menceritakan pengalaman menuju ICPC World Final. Tujuannya adalah berbagi pengalaman. Berhubung rentang maksimal untuk karir ICPC adalah 4 tahun, yang lebih lama dari 2-3 tahun pada OSN/IOI, memutuskan untuk menginvestasikan sebagian dari 4 tahun kuliah ke ICPC merupakan komitmen yang panjang.


Partisipasi Pertama

Setelah masuk Fasilkom UI dan mengikuti berbagai orientasi, saya direkrut untuk ikut ICPC oleh Felik. Anggota tim satunya lagi adalah Rasmunandar Rustam, sehingga tim kami sepenuhnya adalah TOKI 2011. Nama tim yang disepakati adalah Vidina, dari Felik yang artinya "masa depan".

Sebenarnya saya hanya tahu kalau ICPC adalah kontes pemrograman seperti IOI, dengan ciri:
  • Partisipasi tim
  • Penilaian jawaban hanya ada benar atau salah
... dan saya tidak tahu bagaimana aturannya kualifikasinya bekerja. Apakah dipilih N tim terbaik di suatu negara? Atau suatu region? Bagaimana pembagian regionalnya bekerja? Berhubung baru mulai kuliah dan banyak aktivitas, saya tidak mencari tahu jawabannya (atau mungkin karena saya lupa).

Felik kemudian mengurus administrasi tim kami. Kami juga berkenalan dengan Pak Denny, yang merupakan coach untuk tim UI untuk urusan ICPC. Saya mempelajari bahwa biasanya UI mengirim sekitar 3 tim ke suatu regional di Asia. Kalau pada tahun itu diselenggarakan ICPC regional Jakarta juga, maka UI dapat mengirim segerombolan tim karena biaya yang jauh lebih murah. Sebagai catatan, ICPC hanya ada pada semester ganjil.

Berhubung tahun 2011 tidak ada ICPC regional Jakarta, berarti tahun ini hanya 3 tim yang akan ikut regional. Penentuan 3 tim ini diputuskan dengan INC (Indonesia National Contest) yang diselenggarakan Binus. Tim Vidina berhasil mengamankan posisi di INC sebagai salah satu dari 3 tim terbaik dari UI, sehingga kami akan dikirim ke ICPC regional.

Ternyata regional yang dipilih adalah Kuala Lumpur. Kami berangkat ke Malaysia berasama dengan Pak Denny dan 1 tim UI lainnya. Kontesnya akan diselenggarakan di IIUM (International Islamic University Malaysia).

Selama perjalanan, saya belajar dari Pak Denny kalau sekitar 3 tim terbaik di suatu regional akan terkualifikasi ke ICPC World Final (biasa disebut "WF" saja). Aturan sebenarnya lebih rumit, yang melibatkan regional quota, suatu rumus yang memusingkan, pertimbangan khusus, dan sebagainya. Rasanya yang penting bertanding sebaik mungkin, lalu serahkan WF atau tidak ke tangan panitia.

Sejujurnya saya tidak banyak persiapan untuk ICPC ini. Saya juga tak tahu apa harapan partisipasi ini. Rasanya untuk menduduki 3 besar tidaklah mungkin. Namun karena sudah jauh-jauh ke Malaysia, saya tidak pikir panjang dan berkompetisi sebaik mungkin.

Hasil kompetisinya tidak baik. Peringkat akhir Vidina adalah 25-an, yang sangatlah jauh dari 3 besar.

Rasanya tidak enak telah menghabiskan uang fakultas, lalu tidak berkompetisi dengan baik. Kami pulang ke Indonesia sambil memikirkan solusi soal kompetisinya.

Pada semester kedua, Rasmunandar mundur dari Vidina karena ingin fokus ke pemrograman yang lebih aplikatif (seperti website atau aplikasi HP). Felik kemudian merekrut Cakra, yang tahun depan akan masuk UI sebagai angkatan 2012, dan nama timnya menjadi Vidina 2.0.



Tahun Kedua yang Suram

Masuk semester ketiga, tim kami kembali mengikuti INC dan masuk ke dalam 3 tim terbaik UI. Tahun ini terdapat ICPC regional Jakarta, sehingga kami akan berpartisipasi di 2 kontes. Ternyata selain Jakarta, kami akan dikirim ke Hanoi. Sebagai catatan, kontes di Hanoi jauh lebih awal daripada Jakarta.

Hasil regional di Hanoi suram, lagi-lagi kami peringkat 25-an. Namun kali ini saya cukup sedih karena tidak ada kemajuan jika dibandingkan tahun sebelumnya, padahal sudah berlatih selama semester genap. Selain merasa bersalah kepada Pak Denny dan fakultas karena tidak memberikan hasil yang baik, saya mulai merasa untuk mendapat peringkat 3 besar tidaklah mungkin. Saingan dari Taiwan, Cina, Hongkong, Vietnam, atau Singapura (yang isinya teman-teman TOKI juga) terlalu tangguh untuk dikalahkan. Rasa suram ini membuat saya kehilangan semangat dan tidak ikut jalan-jalan ke Ha Long Bay. Setidaknya, pengalaman berkunjung Vietnam cukup menarik dan saya membeli caping khas sana.

Caping "Pandaren" (foto oleh Felik)
Kontes selanjutnya adalah INC 2012, yang mana Cakra tidak bisa ikut karena ada acara orientasi. Jadinya hanya saya dan Felik yang harus nge-tank dan carry. Namun secara mengejutkan, performa kami sangat baik dan memperoleh peringkat ke-3. Hasil yang lebih baik mungkin bisa dicapai kalau kami ber-3. Berkat hasil yang baik ini, moral berperang saya kembali bangkit, dan siap untuk menghadapi regional Jakarta.

Tim UI berbondong-bondong berangkat ke Binus dengan bis kuning untuk regional Jakarta. Ini kedua kalinya saya ke Binus, setelah BNPC HS 2011 pada Pelatnas 1 yang lalu. Berkat moral yang positif, kami bertanding dengan baik dan berhasil duduk di peringkat 10. Ada pencapaian pertama yang diraih, yaitu first solver untuk suatu soal dan kami mendapatkan balon bintang.

Foto dari Felik
Lebih jauh lagi, ternyata kami mendapat penghargaan tim lokal (Indonesia) terbaik ke-3 dan mendapat plakat. Tim lokal terbaik pertama dan ke-2 adalah "Dongskar Pedongi" (timnya Irvan Jahja) dan "+1 Saklar Lhompat" (timnya Ashar). Penghargaan ini juga tiba dengan hadiah berupa hard disk eksternal. Kebetulan saat itu saya perlu format komputer dan butuh media penyimpanan data yang besar, jadilah pucuk dicinta ulam pun tiba.

Walaupun hasil ICPC di Hanoi suram, tapi hasil di Jakarta memberikan harapan. Masih ada waktu 2 tahun untuk berlatih untuk mencapai WF!

Jumat, 29 November 2019

Graf Berarah dengan Setiap Node Memiliki Tepat Satu Keluaran

Graf merupakan konsep yang umum ditemui pada kompetisi pemrograman. Kali ini kita akan membahas graf dengan sifat yang menarik, yaitu setiap node-nya memiliki tepat satu keluaran (memiliki tepat 1 outdegree).

Kalau digambar, grafnya terlihat seperti ini:




Sifat 1: Dijamin terdapat cycle

Tidak mungkin kita dapat membentuk grafnya tanpa cycle. Jika terdapat N node, maka usaha terbaik yang dapat kita lakukan untuk menghindari cycle adalah membentuk struktur seperti rantai: setiap node menunjuk ke node lainnya. Sayangnya ujung terakhir dari struktur rantai ini harus menunjuk ke suatu node lainnya, yang mana pilihannya adalah node-node sebelumnya. Hal ini menjamin selalu terbentuk setidaknya sebuah cycle.

Senin, 28 Oktober 2019

Petunjuk Coding: Binary Search

Konsep binary search sederhana; pada data terurut, periksa nilai di tengah, lalu putuskan apakah pencarian dilanjutkan di setengah awal atau akhir. Kenyataannya, implementasinya tidak semudah itu. Tulisan ini akan membahas implementasi berbagai macam binary search.


Jenis 1: data diskret

Biasanya kita diberikan sebuah array terurut berisi N nilai, lalu diminta mencari index untuk suatu nilai v.

Implementasi yang saya sukai adalah secara iteratif, menggunakan while. Representasikan rentang pencarian dengan dua variabel, sebut saja l dan r. Selama rentang pencarian tidak kosong (yaitu l <= r), periksa nilai di tengah. Kalau nilai di tengah sama dengan v, hentikan pencarian. Kalau lebih kecil, geser batas bawah rentang pencarian menjadi 1 indeks setelah bagian tengahnya. Kalau lebih besar, geser batas atas rentang pencarian menjadi 1 indeks sebelum bagian tengah.

Berikut implementasi lengkapnya. Kalau sampai keluar dari while dan variable ans masih bernilai -1, artinya nilai v tidak ditemukan.

Variasi lain yang memusingkan adalah kalau v tidak ditemukan, cari nilai terdekat yang lebih besar.
Solusinya sama seperti sebelumnya, kecuali ketika nilai di tengah mungkin menjadi jawaban, catat indeksnya. Setelah rentang pencarian habis, dijamin indeks terakhir yang dicatat menyimpan jawaban yang diinginkan. Berikut implementasinya:

Apabila nilai v tidak ditemukan dan yang diinginkan adalah nilai terdekat yang lebih kecil, cukup ubah kondisinya:

Kedua variasi ini adalah binary search yang akan sering Anda temukan pada kompetisi. Pastikan Anda hafal kapan jawaban perlu dicatat.


Jenis 2: Data Kontinu

Biasanya kita tidak diberikan array berisi data, melainkan kita diminta menebak suatu bilangan riil yang memenuhi suatu kondisi. Anggap saja kita memiliki fungsi f, yang menerima bilangan riil antara 0 sampai 1 dan mengembalikan true jika dan hanya jika kondisi terpenuhi. Lalu anggap fungsi f ini memiliki sifat khusus, yaitu terdapat suatu bilangan v, sehingga setiap x yang memenuhi x≥v pasti memiliki nilai f(x) bernilai true.

Sama seperti sebelumnya, buat dua variabel yang merepresentasikan rentang pencarian.
Lalu terdapat setidaknya dua pandangan tentang implementasinya, yaitu menggunakan while sampai rentang pencarian hampir tidak berubah lagi seperti berikut:


Pada implementasi di atas, dipilih nilai 10-8 sebagai nilai toleransi. Kalau beda rentang pencarian sudah lebih kecil dari nilai tersebut, pencarian dianggap selesai dan l dianggap sebagai jawabannya.

Pandangan implementasi lainnya adalah dengan menggunakan for sebanyak K kali. Nilai K biasanya 100, yang mana sudah sangat akurat:

Secara pribadi saya lebih menyukai strategi yang menggunakan for. Alasannya adalah dijamin setelah 100 langkah, program akan berhenti; sementara untuk strategi dengan while, tidak ada jaminan kapan program berhenti. Saya selalu menggunakan strategi dengan for dan tidak pernah ada masalah.


Penutup

Sekian petunjuk untuk mengimplementasikan binary search. Semoga bermanfaat!

Jumat, 27 September 2019

Penulisan Buku Pemrograman Kompetitif Dasar

Libur akhir tahun baru saja lewat. Saya jadi ingat masa-masa liburan akhir tahun 2017 yang dihabiskan untuk menulis buku Pemrograman Kompetitif Dasar (PKD). Proses penulisan buku itu cukup lama. Banyak yang sebelumnya tidak diketahui jadi harus diketahui. Saya akan membagikan pengalaman sepanjang penulisan buku PKD.

Awal Mula

Pada tahun 2014, saya diminta Ashar untuk menuliskan materi pemrograman dasar Pascal untuk dimuat ke TLX Training Gate (seterusnya akan saya sebut TLX-TG). Lalu tahun 2016, ada inisiatif untuk memperluas cakupan materi TLX-TG, sehingga dibuatlah materi pemrograman kompetitif dasar yang isinya lebih ke algoritma-algoritma. Seluruh materi ini ditulis dengan format slide presentasi (seperti materi perkuliahan). Argumennya adalah slide presentasi lebih ringkas daripada penjelasan berupa paragraf, dan dapat memuat gambar yang dianimasikan. Animasi yang saya maksud sebenarnya sesederhana seperti slide 1 memuat array, lalu slide kedua memuat array yang elemennya ditukar; misalnya digunakan untuk mengajarkan pengurutan.

Setelah satu tahun berlalu, Aji tiba-tiba mengajak saya untuk menganalisis kemajuan pemrograman kompetitif di Indonesia. Saya pun terpikir, apakah selama ini materi yang ditulis benar-benar digunakan dan bermanfaat bagi pelajar Indonesia?

Sepanjang saya menulis materi pemrograman kompetitif dasar, sebenarnya ada keraguan apakah slide media yang tepat. Slide mungkin unggul kalau digunakan oleh pengajar, seperti dosen atau guru. Namun kali ini konteksnya adalah pembelajaran mandiri. Saya pribadi lebih suka belajar hal baru dengan membaca tulisan yang penjelasannya lengkap, seperti buku atau artikel.

Analisis tahun 2017 itu dimulai dengan memberikan survey kepada anggota grup facebook "Olimpiade Informatika Indonesia". Saya menggunakan kesempatan ini untuk mengetahui apa pendapat peserta didik tentang media pembelajaran TLX-TG. Salah satu pertanyaan survey tersebut adalah mengurutkan preferensi terhadap empat media pembelajaran:
  1. Slide presentasi
  2. Tulisan artikel/blog
  3. Buku
  4. Video pengajaran
Ternyata keraguan saya terbukti benar. Yang lebih mengejutkan adalah slide presentasi berada di peringkat paling bawah. Media pembelajaran yang lebih diminati adalah video pengajaran, disusul dengan buku.

Memproduksi video pengajaran jelaslah sulit. Diperlukan peralatan untuk merekam video, microphone yang bagus untuk kualitas suara yang bagus, kemampuan mengedit, dan "sosok berkharisma" yang melakukan pengajaran. Lagipula, video pengajaran yang diakses lewat internet tidak menjamin kemudahan akses. Kualitas internet di Indonesia sangat beragam, dan saya sendiri kadang kesulitan untuk nonton video youtube. Singat cerita, video pengajaran tidak dapat dikejar.

Pilihan selanjutnya adalah buku. Mungkin buku adalah media pembelajaran yang paling seimbang dari keempat yang dicalonkan, karena:
  • Penjelasan dapat diberikan secara lengkap, tanpa perlu khawatir halaman menjadi penuh tulisan. Ini perlu dihindari pada penulisan slide.
  • Pembelajarannya sistematis, tidak lompat-lompat atau tercecer seperti tulisan artikel/blog pada umumnya.
  • Lebih mudah diakses daripada video pengajaran.
  • Dapat dicetak, lalu dikirimkan ke segala pelosok di Indonesia.
Yah, memang buku memiliki kekurangannya tersendiri. Anak SMP/SMA yang diminta membaca buku pemrograman atau algoritma penuh tulisan mungkin akan terintimidasi. Buku pelajaran sekolah biasanya memiliki gambar dan berwarna. Bahkan, kadang gambarnya tidak penting dan hanya berperan sebagai dekorasi, misalnya pelajaran ekonomi tentang barter lalu diberikan gambar orang menukar beras dengan kambing.

Selama diskusi dengan teman-teman TOKI berlangsung, keputusannya lebih condong ke penulisan buku. Tujuannya adalah membuat buku yang lengkap, sistematis, dan gratis untuk mempermudah pembelajaran mandiri. Namun saya ragu, dan mempertanyakan apa gunanya buku ini kalau sudah ada buku Competitive Programming 1 (CP1), yang sudah digratiskan oleh Steven & Felix Halim? Argumen yang diberikan adalah CP1 menggunakan Bahasa Inggris, dan tidak semua siswa-siswi sudah lancar berbahasa Inggris. Setelah diyakinkan masih ada niche, akhirnya diputuskanlah untuk menulis buku.

Rencananya adalah membukukan slide materi, ditambah dengan beberapa materi baru. Saya dan Aji berkomitmen menjadi penulis utama buku ini, dan berencana menyelesaikannya sebelum PJJ pra-OSN 2018.

Mulai Menulis Buku

Penulisan dimulai dengan mencari template buku. Idealnya penulisan akan dilakukan dengan Latex, karena gratis dan mudah diintegrasikan dengan version control seperti Git. Aji menemukan template buku yang sekiranya cocok, yaitu tidak terlalu ilmiah dan tidak terlalu santai. Diputuskan untuk sementara menggunakan template buku tersebut.

Selanjutnya dilakukan transformasi slide presentasi ke bentuk buku, atau lebih tepatnya "transpile" kode latex beamer slide ke format latex buku. Aji menulis script untuk melakukannya, dan jadilah buku sangat mentah versi 0.

Tugas selanjutnya adalah mengubah format poin-poin dalam slide menjadi narasi. Aji mengusulkan untuk merekrut sukarelawan untuk membantu proses ini. Jadinya dilaksanakan "hackathon" di kantor Sirclo atas bantuan Brian dan Ashar. Secara mengejutkan cukup banyak yang berminat untuk membantu. Kini bukunya lebih berwujud buku daripada sebelumnya, walaupun gaya penulisan setiap bab gado-gado karena dikerjakan oleh orang yang berbeda. Orang-orang yang membantu hackathon ini namanya dicantumkan sebagai kontributor buku.

Peserta Hackathon PKD
Memasuki libur hari natal dan tahun baru, kantor saya libur selama 2 minggu. Saya menghabiskan waktu bersama Aji untuk merapikan dan menyeragamkan penulisan setiap bab. Setiap bab diperiksa oleh kami, dari awal sampai akhir. Setelah itu bukunya sudah bisa disebut dengan "versi 0.0". Sebetulnya sempat ada perdebatan apakah bukunya mau diberi versi dalam bentuk <major>.<minor>.<patch> yang klasik, atau <major>.<patch> saja. Diputuskan untuk menggunakan <major>.<patch> saja karena tidak jelas kapan minor atau patch bertambah.

Pemolesan Konten

Tahap selanjutnya adalah review. Ashar dan Aji mengusulkan untuk merekrut Pak Suhendry. Untungnya Pak Suhendry bersedia membantu.

Awalnya saya percaya diri kalau bukunya ditulis dengan baik. Ternyata pemikiran itu terbukti salah ketika ditemukan kekeliruan di sana sini. Saya belajar kalau pihak ketiga dibutuhkan untuk memberikan masukan, sehingga hal-hal yang tidak kita pikirkan bisa diketahui.

Pak Suhendry memberikan review yang SANGAT BERMANFAAT. Banyak kekeliruan yang ditemukan, dan hal-hal kecil yang terlewatkan. Saya ingat saran yang paling bermanfaat adalah memperbaiki sistematika penulisan. Misalnya pembahasan perlu dimulai dari A dulu, lalu dilanjutkan ke B, dan seterusnya.

Dekorasi dan Estetika

Setelah kontennya memenuhi standar yang kita tetapkan, saya dan Aji mulai menggarap buku ini dari segi tampilan. Kami merekrut Ali untuk memberi masukan tentang font, skema warna, gambar cover, dan sebagainya. Setelah konsepnya jelas, saya menulis ulang template Latex bukunya sehingga memenuhi konsep yang kita tetapkan.

Bagian yang menyusahkan di sini adalah menulis template Latex itu tidak semudah menulis HTML + CSS (walaupun CSS sendiri pun tidak mudah). Banyak kode-kode misterius, konfigurasi library yang saling bertentangan, dan sebagainya. Setelah berdarah-darah, akhirnya selesai juga.

Suatu buku kurang sempurna apabila tidak ada kata pengantar dan basa-basinya. Jadi kami juga menambahkan kata pengantar, berikut yang lebih pentingnya, yaitu ucapan terima kasih kepada kontributor.

Publikasi

Kini buku sudah sangat berbentuk buku, tinggal dipublikasikan saja. Kami coba bertanya kepada alumni TOKI yang pernah menulis buku, dan ternyata kalau bukunya mau dijual di toko, tidak mungkin bisa non-profit. Toko buku pasti mau keuntungan.

Kalau pihak kita yang mengelola percetakannya, rasanya repot. Kita seakan-akan menjadi penjual toko online. Jadinya kami mulai dengan mempublikasikan dalam bentuk e-book.

Pelajaran

  1. Menulis buku itu melelahkan! Butuh kesabaran, ketangguhan, dan niat untuk menghabiskan berbulan-bulan untuk menyelesaikannya. Untungnya ada teman-teman TOKI dan Aji yang memotivasi.
  2. Harus mampu menulis Bahasa Indonesia dengan benar. Walaupun kita menggunakan bahasa itu setiap hari, penulisannya tidak semudah berbicara. Pertanyaan yang sering muncul kira-kira seperti "apakah ada spasi sebelum 'pun'?".
  3. Walaupun awalnya berdarah-darah, penggunaan Latex sangat membantu. Kita dapat menulis buku dengan editor apapun, lalu dimuat di version control dengan mudah. Kalau disuruh menulis buku lagi, saya pasti pakai Latex.  

Demikianlah pengalaman penulisan buku ini. Apa yang akan terjadi dengan buku ini pada masa depan? Apakah ada edisi kedua? Atau apakah akan ada PKL (Penjual Kaki Lima Pemrograman Kompetitif Lanjut)? Mari anggap saja itu pertanyaan untuk hari esok.

Seperti biasa, saya harap buku ini menjadi pedoman belajar pemrograman bagi kalian yang baru memulai. Semoga bermanfaat.

Video Seri Persiapan OSN Informatika


Sekitar 2 tahun yang lalu, saya dan Aji melakukan survey di grup Facebook Olimpiade Informatika Indonesia. Tujuan surveynya adalah mengukur apakah Training Gate TLX efektif dalam memberi pelajaran, dan juga media apa yang diharapkan ada untuk membantu pembelajaran. Hasilnya, media yang paling diminati adalah video pembelajaran, diikuti dengan buku, dan lain-lain. Berhubung tenaga kerja kami terbatas, maka dibuatlah buku terlebih dahulu.

Entah dari mana datangnya, tiba-tiba tim konten TOKI mendapatkan "hibah" tenaga kerja. Ali yang baru selesai studi mau membantu merekam dan mengedit video, sementara Aji dan Felix Jingga menyiapkan materinya. Pada akhirnya, mereka ditambah Andreas sukses merekam video pembelajaran yang dipublikasikan lewat youtube.

Pembelajaran melalui video tentunya sangat membantu, terutama mereka yang lebih cepat belajar dengan cara mendengarkan daripada membaca (cara belajar visual vs auditori). Saya menyarankan kalian yang ingin belajar OSN informatika untuk mencoba menonton videonya.


Hingga tulisan ini dibuat, sudah ada 16 video. Daftar videonya bisa anda cek di sini: https://www.youtube.com/watch?v=dnpkD_p12WM&list=PL42SmLrOBFuRoDXatrv1PajCbt2ejb2Gn.

Kini bertambahlah sumber pembelajaran kalian. Mulai dari forum, website, buku, sampai video. Yang diperlukan hanyalah motivasi dan semangat dari kalian. Jadi, selamat belajar!

Selasa, 02 April 2019

Terasi (bagian 4): Migrasi ke C++

Di tengah-tengah pengerjaan front end, tiba-tiba saya ada mendapatkan komitmen pekerjaan baru yang membuat proyek Terasi perlu ditunda dulu. Jadi sekitar bulan Juni 2016, saya berhenti untuk sementara.


Lanjutan Pengerjaan

Kini sudah bulan Juni 2017. Sekitar setahun setelah Terasi ditinggal.

Saya sudah beres urusan pekerjaan lainnya dan dapat kembali melanjutkan proyek Terasi. Sebelum langsung melanjutkan, saya periksa dulu apakah tiba-tiba sudah muncul aplikasi yang serupa.

Dari teman, saya tahu kalau Google Maps sudah mengintegrasikan jalur Transjakarta. Jadi saya lihat-lihat. Ternyata implementasinya masih sangat kasar. Jadi ketibaan bus di setiap halte di-hardcode "setiap 15 menit". Ditulisnya data didapatkan dari Transportasi Jakarta. Mungkin karena mereka belum memiliki data yang akurat, jadinya digunakan estimasi kasar 15 menit.

Dari teman lagi, ada sebuah aplikasi yang bernama "Trafi". Saya periksa, dan aplikasinya bagus. Saat itu kita bisa melihat posisi bus secara live. Sepertinya API yang digunakan sama dengan yang saya pakai. Melihat estimasi waktu tunggu, lagi-lagi waktunya di-hardcode per halte.

Kesimpulannya, saya bisa lanjut mengerjakan Terasi.

Oke lalu saya lihat data yang sudah dipanen. Secara mengejutkan ukuran data 1 hari menjadi besar. Setelah dibandingkan dengan data tahun lalu, ini yang saya lihat:

gyosh@gyosh ~/workspace/terasi/data $ ls -l --block-size=M | grep 01-01.tar.gz
-rw-r--r-- 1 gyosh gyosh 12M Jan  1  2016 2016-01-01.tar.gz
-rw-r--r-- 1 gyosh gyosh 25M Mar 18  2017 2017-01-01.tar.gz

Perhatikan kolom ke-5 (1 based). Terlihat bahwa dulunya 12 MB, kini 25 MB. Jadi ukurannya menjadi 2 kali lebih besar!
Pastinya ini hal yang baik untuk Jakarta, karena banyaknya bus bertambah. Lalu tiba-tiba terpikir, atau jangan-jangan ada koridor baru?

Jadi saya periksa peta Transjakarta terbaru, dan ternyata benar. Muncul lebih banyak subkoridor yang namanya berupa angka + huruf, seperti 5A, 5B, 5C, 5D, 5E. Koridor seperti itu biasanya menggunakan sebagian besar koridor 5, tetapi halte awal dan akhirnya mungkin saja berbeda. Selain itu, ada juga koridor baru dengan kode huruf + angka, seperti S11, S21, T11, dan sebagainya. Koridor itu sepertinya mencapai luar Jakarta, seperti daerah "-bodetabek".

Selanjutnya, saya coba menonton rekam jejak terbaru di aplikasi visualisasi saya. Ternyata data bus baru itu tidak terekam. Bus-busnya masih menggunakan informasi koridor yang lama. Artinya tidak ada bus yang mengaku di koridor 5A, 5B, s/d 5E. Semuanya mengaku di koridor 5. Lalu muncul juga banyak bus dengan kode koridor "NBRT".


Saya menduga kalau NBRT ini adalah bus pengumpan (Feeder Bus) Transjakarta. Merekalah yang saya sebut subkoridor, seperti 1A, 1B, 5A, 5B, dsb.