SPOJ PERIOD - Period

Kebiasaan saya kalau sedang mau mengerjakan soal-soal di SPOJ adalah menatapi halaman status. Jika melihat ada orang melakukan pengumpulan untuk soal yang kodenya menarik, akan saya coba lihat soalnya. Kali ini saya mendapati soal sederhana yang menyenangkan untuk didiskusikan, yaitu tentang string. Sepengalaman saya bertanding, soal string jarang keluar di perlombaan (kecuali ICPC Jakarta).

Inti soalnya sederhana, Anda dapat langsung mengaksesnya di sini. Saya sangat merekomentasikan bagi kalian untuk mencobanya terlebih dahulu.

Solusi paling naif adalah dengan mencoba semua kemungkinan prefix, lalu untuk masing-masing prefix dicari periodenya. Seperti biasa, cara ini akan TLE. Untuk mencoba semua kemungkinan prefix saja sudah ada N kemungkinan. Oleh karena itu, untuk mempercepat pendekatan ini setidaknya untuk menghitung periode harus dilakukan dalam O(1).

Teknik Optimisasi Konstanta

Akhir-akhir ini saya sering berlatih di SPOJ, dan seringkali sudah menggunakan algoritma optimal, tetapi tetap TLE. Akibatnya saya harus melakukan optimisasi konstanta habis-habisan hingga akhirnya mendapat AC.

Pada competitive programming, konstanta sering dianggap menjadi hal yang kecil. Karena kecil, dianggap tidak mempengaruhi performa secara keseluruhan. Memang benar, saya termasuk yang berpikiran seperti itu. Namun hal ini tidak selalu berlaku apabila konstanta yang kecil itu ada dalam jumlah yang besar. Bayangkan jika harga beras awalnya Rp 1,00 per butir, lalu tiba-tiba naik menjadi Rp 1,12 per butir. Mungkin memang kenaikannya hanya Rp 0.12, tetapi bila kita membeli 1 ton beras yang isinya ada 36.590.000 butir beras, kenaikannya menjadi Rp 4.390.800,00. Hal yang sama juga berlaku pada program, bila konstanta yang kecil itu muncul pada looping yang bisa dilakukan ratusan ribu kali, bisa saja akan mempengaruhi performa program secara signifikan.

Biasanya, Anda hanya memerlukan optimisasi konstanta pada kompetisi ACM-ICPC (biasanya bukan Jakarta) atau mengerjakan soal di online judge. Untuk kompetisi seperti OSN atau IOI, sang pembuat soal sudah menentukan time limit secara bijaksana sehingga solusi dengan perbedaan konstanta yang bisa dimaklumi tetap mendapatkan AC. Bisa jadi time limit yang ditentukan berasal dari 10 dikali waktu eksekusi solusi si pembuat soal.

Pengalaman saya dalam pemrograman terus menambah pengetahuan dalam melakukan optimisasi konstanta. Berikut ini saya jabarkan teknik-teknik yang saya ketahui, dan siapa tahu dapat membantu Anda di kemudian hari. Sebagai catatan, berkat optimisasi konstanta (dan keberuntungan) saya berhasil menyelesaikan soal Alien Abduction Again, soal ICPC Jakarta 2013 dan berkat itu tim saya (Vidina 2.0) berhasil menjadi best local team :)

SPOJ FSHEEP - Fencing in the Sheep

Soal ini saya hadapi pada saat latihan Pelatnas 2 TOKI 2011. Saya benar-benar tidak bisa mengerjakannya pada saat itu. Akhirnya saya kembali pada saat Pelatnas 4 TOKI 2011, dan berhasil membalas dendam dengan menyelesaikan soal ini >:-)

Dari deskripsi soalnya, terlihat bahwa soal ini cukup sederhana: diberikan sebuah poligon yang mungkin tidak konveks dan sejumlah titik. Tentukan banyaknya titik yang ada di dalam poligon!

Memeriksa apakah suatu titik berada di dalam poligon bisa dilakukan dengan algoritma ray casting, yaitu dengan membuat segmen garis imajiner dari titik tersebut ke suatu arah sembarang, lalu hitung berapa kali garis itu berpotongan dengan poligon. Bila genap, artinya titik berada di luar poligon dan bila ganjil, artinya titik berada di dalam poligon (tidak percaya? Cobalah!). Sayangnya algoritma ini agak repot dilakukan karena garis imajiner yang dibuat tidak boleh menyentuh titik sudut pada poligon. Lagipula kompleksitas untuk sekali pemeriksaan adalah O(N), padahal poligon yang diberikan bisa memiliki sisi sebanyak 100.000, dan banyaknya titik juga bisa sampai 100.000.

Bila tidak ada properti khusus pada soal ini, maka sepertinya soal ini mustahil untuk diselesaikan. Beruntungnya, ada sebuah kalimat yang sangat penting pada soal: "Exhausted, he moves to a place within the pen from which he can see the whole interior of the pen (without any fence getting in the way) and begins to count the sheep which are within it."

Artinya, dijamin ada sebuah titik yang mana bila seseorang berdiri di sana, dia bisa melihat seluruh isi poligon (kemudian diberitahu bahwa titik tersebut ada di (0,0)). Berikut ini gambar yang memberi ilustrasi jenis poligon tersebut. Poligon di sebelah kiri merupakan poligon yang valid, dan yang kanan tidak karena daerah yang berwarna coklat tidak bisa dilihat:

Komposisi Struktur Data Dynamic Range Query

Sejauh ini saya sudah pernah membahas struktur data:

• Disjoint-set
• Segment tree[2] [3]
• Binary Indexed Tree
• Treap [1]

Ada juga struktur data yang menarik untuk digunakan:

• BBST (AVL tree atau Red-Black Tree)
• Segment array [1]
• Range tree [1] (sering diimplementasikan sebagai segment tree dengan nilai agregat berupa vector)

Dan ada juga struktur data yang lebih jarang digunakan:

• Kd Tree
• Quad Tree
• Interval Tree

Masing-masing struktur data tersebut memiliki peran dan kegunaan masing-masing. Oleh karena itu, ketika sedang mengerjakan soal dynamic range query non-klasik, pertanyaan yang muncul adalah "dikerjakan pakai struktur data apa ya?"

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