Akhir Tahun 2013

Tidak terasa waktu setahun telah berlalu, yang artinya saya sudah menulis blog ini selama setahun. Akhirnya wacana yang tersimpan selama bertahun-tahun dapat saya wujudkan, dan karena blog ini masih aktif, artinya saya cukup berhasil :)

Sejauh ini, sudah ada 25 post. Bisa dikatakan secara rata-rata saya menulis setiap sebulan dua kali. Jumlah yang tidak banyak, dibandingkan dengan target seminggu satu post. Apa dayanya, kadang-kadang saya harus mengerjakan tugas kuliah, mengurus organisasi, dan lain-lain. Bagaimanapun juga, saya akan terus berusaha untuk mengejar target tersebut.

Beberapa hal menarik yang saya alami selama menulis blog ini:

• Belajar menggunakan LaTeX untuk menulis rumus
• Belajar menulis yang mudah dimengerti orang lain
• Blog saya sering dikunjungi orang asing untuk melihat postingan ini. Sepertinya diskusi di internet benar-benar sangat jarang sehingga yang muncul di google adalah blog saya :D
• Menulis pembahasan untuk soal benar-benar menambah pemahaman terhadap solusi yang telah kita dapatkan!

Terlepas dari blogging, saya juga berhasil melewati tahun ini dengan baik. Pada tahun ini, selain berkuliah, saya juga memegang posisi:

1. PIC Competitive Programming CompFest (mudahnya: ketua bagian kompetisi pemrograman)
2. Ketua FPC (Fun Programming Club) di Ristek Fasilkom
3. Ketua Departemen Jumatan di KMBUI (Keluarga Mahasiswa Buddhis Universitas Indonesia), intinya mengadakan pertemuan setiap hari Jumat dengan anggota lainnya
4. Asisten dosen untuk kuliah struktur data dan algoritma, dengan segudang berkas yang perlu dikoreksi!

Pada awal tahun, saya mengatakan "kalo sampe bisa ngelewatin 1 tahun dengan 3 kepengurusan dan beberapa kerjaan lain gini, gua akan merasa ganteng". Ternyata memang saya ganteng :')

Banyak kejadian-kejadian yang saya alami dan pelajaran yang saya dapatkan, terutama dalam menjalankan kepengurusan itu. Saya belajar bagaimana mengurus banyak hal (tidak multi-tasking, saya lebih suka sekuensial), mengatur waktu, dan bertanggungjawab dalam melaksanakan berbagai pekerjaan. Benar-benar terasa bagaimana efeknya terhadap kehidupan kita, padahal sebelumnya saya kurang peduli terhadap kegiatan seperti itu. Ternyata memang benar kata orang bijak, "Jika ingin berkembang, keluarlah dari zona nyaman Anda".

Selain itu, saya juga mengikuti berbagai kompetisi. Mulai dari ITBPC, Gemastik, sampai ICPC. Dari sekian banyak kompetisi yang saya ikuti, yang berkesan bagi saya adalah pencapaian terbaik selama di tim Vidina 2.0, yaitu mendapat predikat best local team pada ACM-ICPC Asia Jakarta 2013. Benar-benar tidak menyangka bahwa kita bisa mendapatkannya :')

 

Foto oleh Pak Denny

Semoga di tahun 2014 saya dapat berkontribusi lebih banyak dalam kehidupan ini, khususnya dunia pemrograman di Indonesia dan TOKI.

UVa 10381 - The Rock

Soal ini sudah pernah saya baca sejak tahun 2010, yaitu ketika saya bertekad untuk menyelesaikan soal-soal UVa di chapter 103. Sayangnya, berhari-hari telah saya gunakan untuk memikirkan solusinya dan tidak juga ditemukan :(. Ingin mencari diskusinya di internet pun sumbernya sangat sedikit. Akhirnya pada tahun 2013, saya kembali menantang soal ini dan setelah diskusi dengan Ashar, kami berhasil menyelesaikannya!

Untuk menyelesaikan soal ini, perlu dipahami bahwa soal ini dapat dimodelkan sebagai permainan 2 pemain: satu orang berusaha berjalan sampai pintu keluar (sebut saja A), dan satu orang berusaha memblokir jalan (sebut saja B). Terdapat perbedaan peran yang mana B hanya memiliki kesempatan satu kali memblokir dan dapat dilaksanakan kapan saja. Lalu setelah diblokir, permainan dapat dianggap berakhir karena si pemain yang satunya pasti memilih jalur terpendek. Pertanyaannya adalah: jika keduanya bermain optimal, berapa langkah minimal yang dibutuhkan oleh pemain yang berjalan?

Struktur Data Treap

Sebagai alternatif AVL Tree, Red Black Tree, dan Splay Tree

Bila Anda sering berkecimpung dalam soal dynamic range query, tidak jarang Anda akan menemukan soal yang membutuhkan Balanced Binary Search Tree (BBST) untuk menyelesaikannya. Biasanya, persoalan tersebut melibatkan:

• Dynamic Order Statistic, yaitu diberikan informasi nilai-nilai yang bisa berubah-ubah, lalu sering ditanyakan "Bila nilai-nilai diurutkan dari yang terbesar, siapa yang berada di posisi ke-i?", atau
• Penambahan dan penghapusan objek yang rentang nilainya bisa sangat besar (sehingga array tidak cukup), dan tidak dapat dilakukan grid compression (pemetaan koordinat menjadi yang hanya dibutuhkan saja), dan terdapat query lain yang tidak dapat dilayani oleh STL set atau map pada C++ secara efisien.

Untuk mengatasi kedua hal tersebut, biasanya orang akan menggunakan BBST. Untuk competitive programming, BBST yang populer adalah AVL Tree dan Red-Black Tree. Lalu apakah masalah selesai sampai di sini?

Ada masalah utama dari AVL Tree dan Red-Black Tree, yaitu sulit untuk menulis implementasinya. Sekalipun kompetisi itu berbentuk ICPC dan Anda memiliki catatan implementasinya, Anda masih harus berhadapan dengan panjang dan rumitnya implementasi tersebut (AVL Tree yang saya implementasikan ada 200 baris). Banyaknya baris kode yang Anda tulis akan meningkatkan peluang terjadinya kesalahan, dan sekalinya ada bug, sulit untuk mendeteksi di mana bug itu berada!

Nah karena masalah tersebut, terdapat varian BBST yang lebih ramah dalam hal implementasi: treap. Struktur data ini merupakan "gabungan" dari struktur Binary Search Tree dan heap. Bentuknya berupa binary tree yang tidak harus complete. Setiap node pada treap mengandung dua nilai, yaitu priority dan key. Perlu diperhatikan nilai priority di sini sifatnya sebagai pembantu dalam menyeimbangkan struktur tree, sehingga nilainya tidak berkaitan dengan nilai sebenarnya yang ingin Anda simpan. Bahkan dalam implementasinya, nilai priority didapatkan dengan random. Oleh karena itu treap juga dikenal sebagai randomized data structure, dan memiliki kompleksitas operasi penambahan, penghapusan, dan pencarian dalam expected O(log N). Menurut sumber-sumber yang saya baca, konstanta dari struktur data ini kecil, sehingga expected O(log N) yang dimiliki sangat ringan dan cepat!

ACM ICPC Regional Harbin 2010 - Cross the Wall

Sebuah perkenalan kepada DP Convex Hull... 

Satu lagi soal dari ICPC Regional Harbin 2010 yang sedikit sekali diskusinya, yaitu Cross the Wall. Soal ini sangat menarik karena memerlukan observasi yang mendalam.

Inti dari persoalannya sederhana:

• Diberikan N persegi panjang dengan berbagai ukuran panjang dan lebar.
• Anda boleh membuat maksimal K buah lubang persegi panjang pada sebuah bidang (tembok) sedemikian sehingga setiap persegi panjang dapat melewati bidang tembok tanpa dirotasi.
• Lubang yang dibuat tidak boleh bersentuhan dengan lubang lainnya yang sudah pernah dibuat.
• Persegi panjang yang panjang dan lebarnya lebih kecil atau sama dengan panjang dan lebar lubang bisa melewati lubang tersebut.
• Biaya membuat sebuah lubang persegi panjang dengan panjang P dan lebar L adalah P &times L.
• Seluruh persegi panjang yang dibicarakan di sini memiliki sisi yang paralel dengan sumbu x atau y.
• Tentukan total biaya minimum untuk membuat setiap persegi panjang dapat melewati bidang tembok!

Batasan pentingnya:

• 1 ≤ N ≤ 50.000
• 1 ≤ K ≤ 100
• Panjang dan lebar setiap persegi panjang adalah bilangan bulat positif tidak lebih dari 1.000.000

Pembahasan CP CompFest - Mahasiswa

Seperti yang pernah saya janjikan sebelumnya, inilah pembahasan CP CompFest tingkat Mahasiswa. Seluruh kode sumber untuk pembahasan di bawah ini bisa diunduh dari sini.

---

A. Pangeran Berti

Pembuat soal: Alham Fikri Aji

Cukup cari dua kerajaan dengan banyaknya wanita yang menyukai pangeran sebanyak mungkin. Setelah itu, jawaban bisa didapatkan dari total seluruh wanita dikurangi wanita di dua kerajaan itu.

---

B. Ini Prima

Pembuat soal: Gede Wahyu Adi Pramana

Menggunakan algoritma O(N²) jelas akan mendapatkan TLE.

Perhatikan bahwa barisan dianggap tidak prima total apabila terdapat setidaknya dua bilangan dalam barisan itu yang keduanya memiliki satu faktor prima yang sama. Oleh karena itu, supaya barisan itu prima total, seluruh bilangan harus terusun atas faktor-faktor prima yang berbeda.

Solusi yang dapat digunakan adalah:
Sediakan tabel yang menampung "keberadaan" suatu faktor prima. Untuk setiap bilangan di dalam barisan, faktorisasi prima bilangan itu, lalu tandai "keberadaan" faktor prima dalam tabel itu. Bila ada faktor prima yang sebelumnya sudah "ada" di dalam tabel, lalu hendak ditandai "keberadaan"-nya, artinya barisa itu tidak prima total. Sehingga solusinya memiliki kompleksitas kasar \(O(N \sqrt{M})\), dengan M adalah bilangan rata-rata dalam barisan.

Pastikan faktorisasi bilangan berjalan dengan cepat sehingga bisa mendapatkan AC.

Pembahasan CP CompFest - SMA

Seperti yang pernah saya janjikan sebelumnya, inilah pembahasan CP CompFest tingkat SMA. Kode untuk solusi ini bisa diunduh di sini.

---

A. Laser Ajaib

Pembuat soal: Verdiyanto Saputra

Soal yang paling mudah untuk kontes ini, tetapi butuh ketelitian dalam mengerjakannya.
Untuk setiap kolom, periksa apakah terdapat karakter '#'. Bila tidak ada, maka hasilnya sudah pasti "TIDAK KENA". Sementara bila ada dan bukan merupakan kolom terakhir, periksa apakah di kolom berikutnya bagian atas, tengah, atau bawahnya berisi karakter '#'. Bila tidak, maka jawabannya "TIDAK KENA". Apabila jawabannya bukan "TIDAK KENA", maka cetak "KENA".

---

B. Password Internet Banking

Pembuat soal: Irwan Mulyawan

Ketelitian sangat dibutuhkan untuk memahami maksud soal dan mengerjakannya. Solusi yang saya buat adalah dengan cara rekursif.
Pertama, bangkitkan bilangan prima yang lebih kecil dari 100. Cara yang standar berjalan cukup cepat karena kita tidak perlu mencari bilangan prima yang terlalu banyak. Misalkan string itu bernama S, memiliki panjang L, dan S[i..j] menyatakan substring dari S mulai dari indeks i sampai j (zero-based). Secara garis besar, algoritma yang digunakan:

kerja(a){
  jika (a+1 < L)
    lQ <- 0
    Q <- 2
    lakukan terus:
      jika (a + Q - 1 >= L)
        // tahapan ini selesai, lanjut ke tahap berikutnya
        kerja(a + lQ)
        break
      selain itu
        // putar S[a..a+Q-1]
        balik(S, a, a + Q - 1)
        lQ <- Q
        Q <- prima_selanjutnya(Q)

Algoritma itu dipanggil dengan kerja(0). Kompleksitas solusi ini tidak lebih dari O(N²).

SPOJ MTREE - Another Tree Problem

Saat iseng mencari soal di SPOJ, tiba-tiba saya mendapatkan soal yang menarik. Soal itu adalah SPOJ - MTREE. Terlihat mudah, tetapi tidak begitu. Oleh sebab itu saya akan membahasnya. Saya juga menyarankan Anda untuk mencoba mengerjakan soal itu terlebih dahulu.

Cara paling sederhana adalah dengan mencoba semua N² kemungkinan path, lalu mengalikan keseluruhannya dalam O(N). Sehingga kompleksitas akhirnya O(N³) dan jelas TLE. Cara yang lebih cepat adalah mengalikan sambil mencoba semua kemungkinan jalur, sehingga kompleksitasnya O(N²). Cara ini juga jelas TLE.

Untuk ide menyelesaikannya, mari sederhanakan persoalannya terlebih dahulu. Misalkan tree yang diberikan adalah binary tree yang memiliki root (rooted binary tree), dan kita tertarik untuk mencari bobotnya (sesuai dengan deskripsi soal).

Perhatikan gambar berikut untuk penjelasan di bagian-bagian berikutnya:

Competitive Programming CompFest 2013

CompFest adalah kegiatan tahunan yang dilaksanakan oleh mahasiswa Fasilkom UI. Sejak tahun 2010, terdapat kompetisi pemrograman yang modelnya seperti ACM-ICPC. Kompetisi ini bernama CP CompFest, yang terbagi atas dua jenjang: siswa dan mahasiswa. Untuk tahun 2013, saya dipercaya sebagai Person-In-Charge (PIC), atau lebih mudahnya "ketua" untuk kompetisi ini.

Soal

Berikut ini adalah soal yang diujikan dalam kompetisi ini:

• Penyisihan SMA
• Final SMA
• Penyisihan mahasiswa
• Final mahasiswa

Untuk pembahasan:

• Pembahasan penyisihan SMA
• Pembahasan final SMA
• Pembahasan penyisihan mahasiswa
• Pembahasan final mahasiswa

Menuju OSN 2013

OSN 2013 jatuh pada bulan September, kurang dari sebulan sejak tulisan ini dibuat. Suasana kompetisi semakin terlihat, mulai dari aktifnya para peserta OSN komputer dalam mengerjakan PJJ, bergeraknya supervisor dalam membantu mereka, sampai para petinggi TOKI yang mempersiapkan OSN di Bandung mendatang. Terdapat banyak perbedaan dari suasana OSN zaman saya, oleh karena itu melalui tulisan ini saya ingin berbagi beberapa pandangan yang mungkin dapat membantu memahami kompetitor anda. Tentunya, ini semua hanya pemikiran saya yang didasari dengan pengalaman dan pengamatan selama menjadi orang TOKI.

Semakin banyaknya pengguna C/C++

Berhubung saya bertugas sebagai supervisor PJJ pra OSN 2013, sedikit banyak bisa melihat aktivitas pengerjaan PJJ para peserta. Terlihat bahwa banyak peserta yang menggunakan bahasa C++. Cukup mengejutkan, karena pada OSN 2009 hanya ada 1 orang (dari 110) yang menggunakan C++.

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.

UVa 12357 - Ball Stacking

Rasanya sudah lama sekali semenjak terakhir kali saya mempublikasi tulisan. Mohon maaf karena kesibukan yang luar biasa di kampus, jadinya ngeblognya tertunda.

Kali ini saya akan membahas soal dari UVa 12357 - Ball Stacking. Seperti biasa, karena soal ini menarik dan diskusinya di internet masih sangat sedikit.

Pada soal ini, terdapat N(N+1) bola yang bertumpuk. Lapisan paling bawah memiliki N bola, disusul dengan lapisan berikutnya dengan N-1 bola, lalu N-2 bola, dan seterusnya hingga 1 bola di paling atas. Setiap bola memiliki nilai. Perhatikan gambar berikut untuk kejelasan:

UVa 12240 - Cocircular Points

Berhubung baru kuliah komputasional geometri, kali ini saya akan membahas soal geometri UVa 12240 - Cocircular Points.

Inti soal ini sederhana: diberikan N buah titik. Cari himpunan titik dengan anggota sebanyak mungkin yang saling cocircular. Sebuah himpunan titik dinyatakan saling cocircular apabila ada lingkaran sedemikian sehingga seluruh titik di himpunan itu terletak pada sisi lingkaran tersebut.

Observasi:
Dari tiga buah titik yang tidak segaris, kita bisa membuat tepat sebuah lingkaran yang sisinya menyentuh ketiga titik tersebut. Titik pusat segitiga (sebut saja di \((P_x, P_y)\))itu dapat dicari dengan menyelesaikan persamaan berikut:

\(\begin{eqnarray*}r^2 &=& (A_x-P_x)^2+(A_y-P_y)^2 \\
r^2 &=& (B_x-P_x)^2+(B_y-P_y)^2 \\
r^2 &=& (C_x-P_x)^2+(C_y-P_y)^2 \end{eqnarray*}\)

UVa 1232 - Skyline

Soal ini bersumber dari ICPC Regional Asia, Singapore, 2007-2008. Menarik untuk dibahas, sehingga saya menuliskannya di sini. Sangat disarankan Anda mencoba terlebih dahulu untuk menyelesaikannya.

Inti soalnya kita memiliki sebuah array yang awalnya berisi angka 0 dan akan melayani sejumlah operasi. Operasi ini adalah membuat nilai array di suatu interval tertentu menjadi nilai maksimum antara nilai sebelumnya dengan suatu nilai yang baru. Tugas kita adalah menghitung ada berapa kali perubahan nilai yang terjadi.

Sebuah kata kunci yang tidak boleh Anda lewatkan adalah "You may assume that the amount of overlap for each dataset is at most 2000000". Biasanya soal yang menyebutkan batasan seperti ini dapat diselesaikan dengan algoritma output-sensitive, artinya kompleksitasnya bergantung pada keluaran.

Berhubung di soal ini hanya ada satu macam operasi (query), kita bisa mengerjakannya secara offline (setiap operasi dibaca dulu, lalu dikerjakan dulu semuanya, baru dicetak semuanya). Biasanya cara ini lebih mudah ketimbang kita harus melaksanakan setiap operasi secara online.

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).

UVa 12589 - Learning Vector

Soal yang akan dibahas kali ini adalah UVa 12589 - Learning Vector. Singkatnya, kita berikan N vektor. Pilih K vektor sedemikian sehingga bila vektor-vektor itu digambar dalam poligon dengan urutan tertentu, akan menghasilkan luas daerah di atas sumbu-x terbesar.

Observasi 1:
Misalkan kita memiliki sejumlah vektor. Menggambarkannya dalam bentuk poligon dengan urutan apapun akan berakhir di suatu titik yang sama. Alasannya karena penjumlahan vektor bersifat komutatif. Permasalahan berikutnya adalah bagaimana kita menentukan urutan penggambarannya sehingga luas yang dihasilkan maksimal.

Observasi 2:
Untuk menghasilkan luas di atas sumbu-x maksimal, sejumlah vektor itu harus kita urutkan mulai dari yang "gradien"-nya terbesar. Jadi muncul strategi greedy untuk mengurutkan vektor-vektor tersebut.

UVa 11491 - Erasing and Winning

Soal yang menarik untuk dibahas kali ini berasal dari UVa 11491 - Erasing and Winning.
Persoalannya sederhana, kita diberikan sebuah bilangan yang besarnya n dan n ~ 100000. Jika kita harus menghapus d dijit, maka berapa bilangan terbesar yang dapat kita hasilkan?
Karena banyaknya dijit cukup besar, jelas bahwa brute force \(O(2^n)\) tidak akan bekerja.

Observasi 1:
Solusi optimal ketika d dijit dihapus sama saja dengan: bilangan terbesar yang dapat dihasilkan bila kita menghapus 1 dijit dari solusi optimal saat (d-1) dijit dihapus. Oleh karena itu, kita dapat menghapus 1 per 1 dan di setiap langkahnya harus optimal. Observasi ini memunculkan aroma greedy pada persoalan ini.

ACM ICPC Regional Harbin 2010 - Volume

Entah mengapa saya merasa kasihan dengan soal ini, sehingga saya memutuskan untuk membahasnya. Soal yang akan dibahas dapat anda akses di Live Archive dengan kode 5096 (LA 5096).

Singkatnya, soal ini ingin kita untuk menghitung volume dari bangun berikut, dengan tinggi silinder dan jari-jarinya diberikan:

Gambar dari https://icpcarchive.ecs.baylor.edu

Untuk menyelesaikan soal ini, dibutuhkan pengetahuan tentang integral. Misalkan jari-jari silinder itu r dan tingginya h. Terdapat dua macam kasus, yaitu ketika 2r ≤ h, dan ketika 2r > h (bentuknya menjadi berubah).

Pertama, kita anggap 2r ≤ h sehingga bentuknya persis seperti yang ditunjukkan gambar di atas. Ambil \(\frac{1}{8}\) bagian dari bangun itu, sehingga didapatkan bentuk berikut:

Kita cukup mencari volume dari bangun ini, lalu dikali dengan 8. Volume dari bangun ini sama dengan volume dari 2 kali \(\frac{1}{4}\) silinder dikurangi dengan volume daerah di daerah perpotongannya. Daerah perpotongan itu memiliki bentuk seperti gambar warna ungu, dan memiliki tampak samping seperti bentuk berwarna merah:

Dengan menganggap bidang s bergeser dari atas ke bawah (yaitu dengan menjalankan x=0 sampai x=r), volume dari bangun perpotongan itu adalah:
\(
\begin{eqnarray*}
\int_0^r \! s^2 \, \mathrm{d}x &=& \int_0^r \! \left(\sqrt{r^2 - x^2}\right)^2 \, \mathrm{d}x\\
&=& \int_0^r \! r^2 - x^2 \, \mathrm{d}x\\
\end{eqnarray*}
\)
Integral tersebut diselesaikan dengan substitusi trigonometri

Misalkan \(x = r\sin{\theta}\), maka \(\mathrm{d}x = r\cos{\theta}\ \mathrm{d}\theta\)
Perhatikan bahwa batas-batas integral kita masih dalam \(x\), bukan \(\theta\). Untuk itu, kita perlu melakukan perubahan.

Untuk batas bawah:
\(
\begin{eqnarray*}
0 &=& r \sin{\theta}\\
0 &=& \sin{\theta}\\
\theta &=& 0\\
\end{eqnarray*}
\)

Untuk batas atas:
\(
\begin{eqnarray*}
r &=& r \sin{\theta}\\
1 &=& \sin{\theta}\\
\theta &=& \pi/2\\
\end{eqnarray*}
\)

Substitusikan ke dalam persamaan:
\(
\begin{eqnarray*}
\int_0^r \! r^2 - x^2 \, \mathrm{d}x &=& \int_0^{\pi/2} \! \left( r^2 - r^2\sin^2{\theta}\right) r \cos{\theta}\ \mathrm{d}\theta\\
&=& \int_0^{\pi/2} \! r^3 (1 - \sin^2{\theta}) \cos{\theta}\ \mathrm{d}\theta\\
&=& r^3 \left( \int_0^{\pi/2} \! \cos{\theta}\ \mathrm{d}\theta - \int_0^{\pi/2} \! \sin^2{\theta}\cos{\theta}\ \mathrm{d}\theta\right) \\
&=& r^3 \left( \left[\sin{\theta}\right]_0^{\pi/2} - \left[\frac{1}{3}\sin^3{\theta}\right]_0^{\pi/2} \right)\\
&=& r^3 \left( 1 - \frac{1}{3} \right)\\
&=& \frac{2}{3}r^3\\
\end{eqnarray*}
\)

Jadi kita sudah dapatkan volume dari bagian perpotongan kedua silinder tersebut. Volume keseluruhannya adalah 8 dikali, luas 2 kali 1/4 tabung dikurangi daerah yang tumpang tindih:
\(
\begin{eqnarray*}
V &=& 8\left( 2\frac{1}{4}\pi r^2 h - \frac{2}{3}r^3 \right) \\
&=& 2\pi r^2 h - \frac{16}{3}r^3\\
\end{eqnarray*}
\)

Sekarang kita beranjak ke kasus berikutnya, ketika 2r > h. Anda dapat membayangkan bentuknya seperti dua koin yang menyatu di bagian tengah. Seperempat dari bangun tersebut berbentuk seperti gambar di kiri:

Volume dari bangun tersebut adalah dua kali volume bagian yang berwarna merah atau biru. Sementara volume bangun keseluruhan adalah empat kali dari bangun tersebut. Kita akan mencari volume bangun berwarna merah. Volumenya sama dengan volume setengah silinder itu dikurangi dengan volume daerah yang dipotong.

Volume yang dipotong adalah:
\(
\begin{eqnarray*}
2 \int_0^{h/2} \! x s \, \mathrm{d}x &=& 2 \int_0^{h/2} \! x \sqrt{r^2 - x^2} \, \mathrm{d}x\\
\end{eqnarray*}
\)
Seperti pada cara yang sebelumnya, kita gunakan substitusi trigonometri.
\(
\begin{eqnarray*}
2 \int_0^{h/2} \! r\sin{\theta} \sqrt{r^2 - r^2 \sin^2{\theta}} \, r\cos{\theta}\ \mathrm{d}\theta &=& 2 \int_0^{h/2} \! r^3 \sin{\theta}\cos^2{\theta} \, \mathrm{d}\theta\\
&=& 2\left[ -\frac{1}{3} r^3 \cos^3{\theta} \right]_0^{h/2} \\
&=& -\frac{2}{3}\left[ r^3 \cos^3{\theta} \right]_0^{h/2} \\
\end{eqnarray*}
\)

Ups, batas integral masih dalam \(x\). Akan lebih mudah jika \(\theta\) dikembalikan ke \(x\). Perhatikan bahwa \(r\cos{\theta} = \sqrt{r^2 - x^2}\). Jika disubstitusi:
\(
\begin{eqnarray*}
-\frac{2}{3}\left[ r^3 \cos^3{\theta} \right]_0^{h/2} &=&-\frac{2}{3}\left[ (r^2 - x^2)^{3/2} \right]_0^{h/2}\\
\end{eqnarray*}
\)

Berhubung kalau dibuka ke bentuk tertutup rumusnya akan memusingkan, jadi saya biarkan dalam bentuk dengan batas atas dan bawah saja.

Volume akhir dari kasus kedua ini adalah 4 dikali 2 dikali, volume setengah silinder yang dikurangi bagian terpotong:
\(
\begin{eqnarray*}
V &=& 4 \left( 2\left( \left( \frac{1}{2}\pi r^2 \frac{1}{2}h \right) - \left( -\frac{2}{3}\left[ (r^2 - x^2)^{3/2} \right]_0^{h/2} \right) \right) \right)\\
&=& 8\left( \frac{1}{4} \pi r^2 h +\frac{2}{3}\left[ (r^2 - x^2)^{3/2} \right]_0^{h/2}\right)\\
\end{eqnarray*}
\)

Yap, rumus sudah didapatkan. Selanjutnya tinggal diaplikasikan ke program.

Mau Dibawa ke Mana Bahasa Indonesia?

Tulisan kali ini tidak ada sangkut pautnya dengan competitive programming, hanya merupakan tuangan dari pikiran saya tentang kondisi berbahasa di negeri ini.

Prakata: tulisan ini hanyalah pikiran yang pernah melintas di kepala saya. Tidak ada maksud melawan, menjelek-jelekkan, atau sejenisya.

"... ciyuss? Miapah!?! Enelan?!??!"
"... gitu lho bro konsep kita, gimahow?"
"selaww brayy, kumpul masih minggu depan..."
"ini tuh gak make sense banget deh..."
"... gimana dong? Secara gue ini kan..."

Kata-kata yang kadang saya dengar entah di acara/iklan televisi, percakapan anak muda, baca di tweet seseorang, atau di status facebook. Terus terang, kata-kata itu membuat pikiran saya melayang-layang.

Beberapa waktu yang lalu, saya membaca sebuah artikel di entah situs apa (saya lupa). Artikel itu memberi komentar atas generasi muda yang yang sudah tidak lancar lagi berbahasa Indonesia. Artikel itu juga menyatakan di sekolah, mayoritas mereka menggunakan bahasa Inggris. Komentar itu juga dikaitkan dengan Sumpah Pemuda, bahwa para pemuda di masa lalu tidak main-main dalam menyatakan Bahasa Indonesia sebagai bahasa nasional.

Secara pribadi, saya setuju dengan maksud yang ingin disampaikan artikel itu. Jika anda bangsa Indonesia, hendaknya mampu berbahasa Indonesia dengan baik. Urusan bahasa sehari-hari tidak terlalu dipermasalahkan, entah itu bahasa Jawa, Sunda, Batak, atau bahasa daerah lainnya. Urusan sekolah mau belajar bahasa apa terserah, yang penting muridnya (yang bangsa Indonesia) mampu berbahasa Indonesia dengan baik.

Masalah muncul ketika yang dimaksudkan adalah berbahasa Indonesia, tetapi yang diucapkan adalah "bahasa" Indonesia. Entah dari mana sumbernya tetapi "bahasa" Indonesia hibrida mulai bermunculan. Sebut saja ciyus, enelan, dan kawan-kawannnya. Yang lebih lucu lagi adalah gimahow, selaw, bray. Bahasa apa itu!?

Sebelum saya mengenal kata-kata tersebut, saya tidak menganggap bahwa bahasa "gaul" merupakan sesuatu yang buruk. Sayangnya keberadaan kata-kata itu mulai mengancam kedudukan bahasa "gaul" di zona-aman-digunakan. Apakah kata-kata seperti itu bermakna? Apakah menggunakan kata-kata seperti itu akan membuat seseorang terlihat gaul? Apakah berkomunikasi dengan setengah bahasa Inggris setengah bahasa Indonesia membuat seseorang terlihat keren?

Sungguh lucu apabila di masa depan kata-kata tersebut masuk ke dalam KBBI, dianggap sebagai kata-kata serapan. Bagaimanapun juga, saya tidak tahu apakah ini merupakan salah satu bentuk evolusi bahasa, fenomena yang wajar, atau hanya tren sesaat. Menurut saya, sebisa mungkin gunakan bahasa Indonesia jika memang ada kata untuk mewakili apa yang ingin disampaikan. Dalam menulis blog, saya sendiri berusaha menghindari penggunaan kata-kata bahasa asing, kecuali jika kata tersebut memang lazim digunakan untuk merepresentasikan maksud saya. Mengapa menggunakan thanks jika kita punya terima kasih, atau setidaknya "makasih"?

UVa 12440 - Save the Trees

Soal menarik yang akan dibahas kali ini adalah UVa 12440 - Save the Trees. Sedikit sekali diskusi yang ada di internet tentang soal ini, sehingga saya memutuskan untuk menulis pembahasannya.

Persoalannya adalah, diberikan sebuah barisan pohon (bisa sampai 100000) dengan ketinggian dan jenis tertentu. Tugas kita adalah mengelompokkan pohon-pohon konsekutif ke dalam beberapa grup, dimana banyakya grup tidak dibatasi dan di dalam grup tidak boleh ada pohon berjenis sama. Biaya untuk mengelompokkan sebuah grup sama dengan tinggi maksimum dari pohon di grup tersebut. Berapa biaya total minimal yang mungkin untuk mengelompokkan semua pohon tersebut?

Misalnya tinggi pohon ke-i dinyatakan dengan h[i], dan jenis pohon ke-i adalah c[i].
Observasi 1:
Untuk setiap pohon ke-i, ada pohon x dimana x adalah minimal dan x ≤ i, sedemikian sehingga c[j] untuk x ≤ j ≤ i unik. Kita sebut x ini sebagai pre[i].

UVa 10271 - Chopsticks

Soal menarik kali ini bersumber dari UVa 10271 - Chopsticks. Karena tidak banyak orang yang membahas soal ini di internet, maka saya akan membahasnya. Sedikit curhat, pertama kali saya membaca soal ini adalah pada tahun 2010. Pada saat itu saya benar-benar tidak ada ide bagaimana mengerjakannya. Di tahun 2011 akhir akhirnya saya kembali menantang soal ini, dan akhirnya accepted :D

Tugas: diberikan N batangan sumpit dengan panjang tertentu. Bentuk K triplet sumpit sedemikian sehingga biayanya seminimal mungkin. Biaya membentuk sebuah triplet sumpit sama dengan kuadrat dari selisih dua sumpit terpendek.

Misalkan kita tidak perlu mencari sumpit terpanjang untuk setiap set. Persoalan kita sekarang adalah:
Diberikan N bilangan. Buat K pasangan bilangan sedemikian sehingga jumlah kuadrat dari selisih mereka seminimal mungkin! Untuk kemudahan, anggap saja kita ingin meminimalkan biaya pemilihannya.

tokilearning - Webs

Update 2017-06-14:
Web tokilearning yang lama sudah tidak aktif, Anda sudah tidak bisa mengumpulkan jawaban untuk soal ini. Namun Anda masih dapat mempelajarinya di tulisan ini.

Oke kali ini saya akan membahas soal Webs dari tokilearning. Konon katanya soal ini digunakan untuk simulasi Pelatnas 2 TOKI 2010 di UGM. Dari gaya bahasanya, kelihatannya soal ini dibuat oleh Irvan Jahja. Sekilas, soal ini tampak menyeramkan. Pada kenyataannya tidak terlalu menyeramkan, asal kita memilah-milah dan tahu apa yang harus dikerjakan.

Tugas kita adalah menghitung berapa banyak segitiga yang ada!

UVa 12384 - Span

Saya akan membahas sebuah persoalan yang menarik, bersumber dari UVa 12384 - Span. Deskripsi soal yang singkat, padat, dan jelas itu mungkin sedikit membingungkan. Pastikan anda mengerti maksud soal atau setidaknya mampu membaca notasi matematikanya. Sebagai informasi, jika A adalah sebuah himpunan, maka |A| menunjukkan banyaknya elemen di dalam himpunan A.

Saya akan merubah cerita soal tersebut sehingga tidak terlalu matematis. Misalkan array X menampung tinggi badan orang dalam sebuah barisan, dari paling depan hingga paling belakang. Setiap orang di barisan menghadap ke depan. Orang di barisan ke-i dapat melihat orang di barisan ke-j, apabila semua orang yang berada di antara i dan j (termasuk i dan j) lebih pendek atau sama dengan tinggi orang ke-i. Lalu S[i] akan menunjukkan banyaknya orang yang dapat dilihat orang ke-i. Nah tugas kita berikutnya adalah menghitung nilai dari (S[1] + S[2] + ... + S[n]) mod m.

Halo Dunia

Halo dunia! Perkenalkan saya, William Gozali!

Setelah tertunda bertahun-tahun, akhirnya saya memulai menulis blog! Mari kita mulai dengan berbincang-bincang tentang mengapa saya menulis blog, apa saja yang akan ada di blog ini, dan apa harapan saya dengan adanya blog ini.

Sudah sejak zaman batu saya hidup dibantu orang lain. Pas lahir, orang tua dibantu dokter. Pas bayi, makan dibantu orang tua. Pas bocah, belajar dibantu orang yang lebih tua. Hingga akhirnya pada suatu saat saya berhadapan di pintu gerbang keagungan: internet.

Di internet, saya sangat terbantu! Ketika ada tugas sekolah yang referensinya sulit dicari, internet membantu saya. Ketika saya ingin belajar ilmu akuarium, internet membantu saya. Ketika saya ingin menjalankan praktikum, internet membantu saya. Namun seperti yang saya tulis di paragraf sebelumnya, internet adalah sebuah pintu gerbang. Pintu gerbang ke mana? Ke tulisan orang lain yang bermanfaat! Meskipun tidak semuanya bermanfaat, tetapi kita bisa memilih mau ke arah mana internet membawa kita. Hasilnya, saya banyak terbantu karena adanya tulisan-tulisan bermanfaat dari orang lain. Untuk membalas budi mereka, saya sendiri pun akan menulis tulisan yang bermanfaat!

Judul dari blog ini adalah "Kupas Kode". Mungkin anda akan bertanya "mengapa demikian?"

Kupas adalah aktivitas berhubungan dengan buah yang kulitnya tidak bisa dimakan. Kalau buah itu dilihat dari luar saja, kita tidak tahu apa yang bisa didapatkan. Apakah rasanya manis? Apakah asam, tetapi sangat bernutrisi? Untuk itu buahnya perlu pelan-pelan dibuka, lalu dirasakan, sampai dicerna. Seperti buah ini, ilmu pun demikian. Saya akan membahas ilmu-ilmu yang saya miliki dari kulit luar, sampai ke dalam-dalamnya.

Saya masih anak muda (setidaknya saat menulis tulisan ini), belum punya gelar keilmuan tertentu. Namun ada hal yang saya miliki dan saya rasa akan bermanfaat, yaitu pengalaman di kompetisi pemrograman (atau populer dengan istilah competitive programming). Saya akan mengisi blog ini dengan pembahasan soal-soal competitive programming yang menarik atau jarang ada pembahasannya di internet, ditambah sampingan-sampingan seperti pengalaman hidup, pemikiran pribadi, dan hal lainnya.

Dengan harapan bahwa suatu saat nanti blog ini akan kaya manfaat, saya akan berusaha mengisi blog ini dengan artikel bermanfaat!

Sekian tulisan pertama saya. Salam sejahtera.