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

---

C. Berhitung

Pembuat soal: Ricky Suryadharma

Soal ini tidak mudah untuk dikerjakan, dan perlu beberapa strategi supaya kompleksitas waktunya rendah. Anda dapat membaca dokumen pembahasannya dari kak Ricky sendiri di sini.

---

D. Gudang Kardus

Pembuat soal: William Gozali

Gambar yang disajikan pada berkas soal rasanya cukup membantu untuk mendapatkan solusinya.

Observasi 1:

Bagian paling dasar dari gudang harus diisi sepenuh-penuhnya.

Observasi 2:

Setelah bagian paling dasar gudang diisi sepenuh-penuhnya, gudang ini bisa dianggap sebagai gudang dengan bentuk "hampir" setengah lingkaran dengan bagian bawahnya dipotong. Dengan begitu, strategi yang dijelaskan di observasi pertama dapat digunakan kembali.

Sekarang bagaimana cara mengisi bagian paling dasar gudang dengan sepenuh-penuhnya? Perhatikan gambar berikut.

Banyaknya kardus yang muat di "lantai dasar" adalah floor(2x/S). Nilai x sendiri dapat dihitung dengan:

\(x = \sqrt{R^2 - S^2}\)

Setelah itu, lanjutkan ke bagian berikutnya ("lantai 2"): 

Kali ini, nilai x adalah:
\(x = \sqrt{R^2 - (2S)^2}\)

Secara umum, untuk "lantai k" rumus x adalah:
\(x = \sqrt{R^2 - (kS)^2}\)

Lakukan terus sampai "lantai k" sehingga lantai tersebut tidak bisa memuat kardus, yaitu ketika
\(R^2 - (kS)^2 < 0\)

Dengan begitu, kompleksitas akhir solusi ini adalah O(R/S).

---

E. Kuis Chanek

Pembuat soal: William Gozali

Bila Anda belum terbiasa dengan DP, sangat disarankan untuk mempelajarinya terlebih dahulu (misalnya di sini).

Bila sudah terbiasa, maka soal ini terlihat cukup straight-forward. Yang menjadi state cukup jelas, yaitu posisi kita berada sekarang. Misalkan f(a,b) menyatakan banyaknya uang maksimal yang bisa diperoleh sampai akhir permainan, apabila kita berada di baris a dan kolom b. Selain itu, anggap m[a][b] adalah uang yang tersimpan di baris a kolom b. Formulasinya adalah:

\(\displaystyle
f(a,b) = \left\{
\begin{array}{ll}
m[a][b]&, a = R\\
\max_{
\begin{array}{c} 1 \le i \le C\\ i \ne b\end{array}
}\left( m[a][b] + f(a+1, i) \right)&, a < R \end{array} \right. \)

Terdapat RC state pada formulasi DP tersebut, dan setiap state membutuhkan waktu O(C) untuk diisi. Oleh karena itu kompleksitas totalnya O(RC²). Kompleksitas ini terlalu lambat, sehingga mendapatkan TLE.

Kita coba sederhanakan persoalan yang ada. Misalkan tidak ada aturan bahwa kolom yang berikutnya dipilih harus berbeda dengan kolom saat ini. Maka kompleksitas DP itu bisa direduksi menjadi O(RC) saja dengan cara:
Jika i adalah suatu bilangan dan x adalah sembarang bilangan, pilihan terbaik untuk setiap f(i, x) adalah pergi ke f(i+1, y), dengan f(i+1, y) adalah nilai terbesar dari f(i+1, 1), f(i+1, 2), ..., f(i+1, C).

Mengapa demikian? Jelas karena tujuan kita mencari yang terbesar! Secara alami, seluruh f(i, x) akan menuju ke f(i+1, y) tersebut.

Sekarang bagaimana bila ada aturan yang melarang kolom berikutnya harus berbeda dengan kolom saat ini? Caranya sederhana: simpan dua nilai terbesar ketimbang satu saja

Misalkan f(i+1, y) adalah yang terbesar dan f(i+1, z) adalah yang kedua terbesar dari f(i+1, 1), f(i+1, 2), ..., f(i+1, C). Maka:

• Jika x bukan y, maka f(i, x) pasti menuju ke f(i+1, y)
• Jika x adalah y, maka f(i, x) pasti menuju ke f(i+1, z)

Menurut saya pribadi, untuk mengimplementasikan strategi ini akan lebih mudah apabila digunakan strategi bottom up.

Karena berhasil menghilangkan looping dalam mencari pilihan terbaik, maka kompleksitas akhirnya O(RC). Cukup untuk mendapatkan AC.

---

F. Dinas Perhubungan

Pembuat soal: William Gozali

Soal ini juga cukup umum, dan terlihat cukup straight forward. Strategi yang digunakan adalah floodfill (bila belum familiar, kunjungi saya). Setelah setiap kota diberikan label, sisanya tinggal memeriksa untuk setiap pasang kota apakah mereka memiliki label yang sama. Sayangnya, kita tidak bisa memeriksa setiap pasang kota karena banyaknya kota bisa sampai 50.000. Jelas akan mendapat TLE.

Ada banyak solusi yang dapat Anda gunakan. Solusi dari saya adalah:

Pasangan yang tidak terhubung sama dengan: semua kemungkinan pasangan dikurangi pasangan yang terhubung.

Menghitung banyaknya pasangan yang saling terhubung tidak sulit, tinggal hitung saja untuk setiap label, ada berapa kota yang memiliki label tersebut. Misalkan banyaknya adalah x, maka banyaknya kota yang saling terhubung dalam komponen itu adalah x(x-1)/2. Bahkan, hal ini dapat dikerjakan pada saat melakukan floodfill untuk melabeli komponen.

Jadi, jika ada K komponen dalam graf tersebut, masing-masing dengan banyaknya anggota n₁, n₂, ..., n_K, maka jawabannya adalah \(C_{2}^{N} - C_{2}^{n_1} - C_{2}^{n_2} - ... - C_{2}^{n_K}\). Kompleksitasnya O(M).

Tambahan:
Mengapa dibatasi sebuah kota dibatasi hanya memiliki 4 tetangga? Supaya pengguna Pascal bisa menggunakan representasi adjacency list dan tidak dirugikan dibandingkan dengan pengguna C/C++ :)

---

G. Pembiakan Selektif

Pembuat soal: William Gozali

Strategi paling naif adalah dengan memeriksa setiap pasang ikan jantan dan betina, sehingga kompleksitasnya O(N²) untuk setiap pembeli. Tentunya, cara ini (sangat) lambat dan tidak akan mendapat AC.

Untuk memulai, urutkan dulu kualitas-kualitas ikan mulai dari yang paling kecil ke besar untuk masing-masing jenis kelamin ikan. Misalkan berikut ini adalah kualitas ikan jantan dan betina (masing-masing dalam sebuah baris).

1 3 3 4 5 8 9
1 2 2 3 4 4 6

Selanjutnya, kualitas ikan jantan ke-i akan dinyatakan dengan J[i]. Sementara kualitas ikan betina ke-i akan dinyatakan dengan B[i].

Jika pembeli ingin kualitas ikan keturunannya di antara 2 sampai 16, kita cari untuk setiap ikan jantan, banyaknya ikan betina yang dapat dipasangkan (hasil kali kualitasnya di antara 2 sampai 16) dengannya.

1: [2, 2, 3, 4, 4, 6]
3: [1, 2, 2, 3, 4, 4]
3: [1, 2, 2, 3, 4, 4]
4: [1, 2, 2, 3, 4, 4]
5: [1, 2, 2, 3]
8: [1, 2]
9: [1]

Pencarian banyaknya ikan betina itu bisa dilakukan dengan binary search yang dibagi menjadi dua bagian:

1. Mencari batas bawah, yaitu indeks i sedemikian sehingga hasil kali B[i] dengan kualitas ikan jantan itu lebih dari atau sama dengan A (batas bawah yang diberikan pembeli). Anggap nilai batas bawah ini adalah L.
2. Mencari batas atas, yaitu indeks i sedemikian sehingga hasil kali B[i] dengan kualitas ikan jantan itu kurang dari atau sama dengan B (batas atas yang diberikan pembeli). Anggap nilai batas atas ini adalah U.

Dengan sedikit matematika dan akal-akalan dalam binary search, kedua hal itu dapat dilakukan dalam O(log N). Banyaknya ikan betina yang "cocok" dengan ikan jantan itu kemudian bisa dihitung dengan (U - L + 1).

Sejauh ini, menjawab satu pertanyaan pembeli membutuhkan kompleksitas waktu O(N log N). Tentunya masih juga belum cukup untuk mendapatkan AC.

Strategi yang mungkin konyol, tetapi dapat dicoba adalah dengan memperhatikan bahwa batas bawah/atas untuk beberapa ikan jantan mungkin saja sama. Contohnya saja, perhatikan pada contoh di atas bahwa ikan dengan kualitas 3 dan 4 memiliki konfigurasi ikan betina yang sama persis. Jika diperhatikan lebih jauh lagi, hanya ada maksimal \(O(\sqrt{100.000})\) kemungkinan untuk batas bawah/atas dari suatu ikan jantan!

Mengapa bisa demikian? Perhatikan bahwa kualitas setiap ikan tidak lebih dari 100 ribu, demikian juga batasan untuk pertanyaan-pertanyaannya. Untuk membuktikannya, cukup hitung banyaknya elemen himpunan H(K) dengan:
\(H(K) = \{\lfloor\frac{K}{1}\rfloor, \lfloor\frac{K}{2}\rfloor, \lfloor\frac{K}{3}\rfloor, ..., \lfloor\frac{K}{K}\rfloor\}\)
Perhatikan bahwa banyaknya elemen pada H(K) belum tentu K, karena elemen yang nilainya sama hanya dianggap ada 1. Ingat bahwa ini adalah himpunan :)

Tentunya, ukuran terbesarnya adalah ketika K = 100.000. Nyatanya, hanya ada 631 elemen! Selain itu, bila dibuat grafik untuk |H(1)| sampai |H(100.000)|, hasilnya adalah:

Kurva berwarna biru adalah kurva untuk |H(x)|, sementara kurva jingga adalah kurva fungsi \(f(x)=\sqrt{x}\). Jika diteliti, \(|H(x)| \approx 2\sqrt{x}\).

Dengan begitu, yang perlu dilakukan tinggal:

1. Anggap M adalah nilai kualitas ikan/batasan permintaan pembeli yang terbesar
2. Kelompokkan setiap ikan jantan, menurut nilai ceil(A/J[i]). Maksimal terdapat \(O(\sqrt{M})\) kelompok. Semua ikan jantan pada satu kelompok memiliki batas bawah yang sama.
3. Kelompokkan setiap ikan jantan, menurut nilai floor(B/J[i]). Maksimal terdapat \(O(\sqrt{M})\) kelompok. Semua ikan jantan pada satu kelompok memiliki batas atas yang sama.
4. Lakukan binary search untuk setiap kelompok untuk mencari batas bawah dan atas mereka.

Total operasi yang dilakukan adalah \(O(\sqrt{M} \log{N})\) per pertanyaan pembeli. Cukup untuk mendapatkan AC.

---

H. Pipa Bocor

Pembuat soal: William Gozali

Cara sederhana yang mungkin digunakan adalah:

1. Untuk setiap petak yang memiliki pipa, tandai daerah sekitarnya yang terkena semburan airnya.
2. Lakukan BFS dari petak awal ke petak tujuan, tanpa melewati petak yang basah.

Kompleksitas untuk langkah pertama adalah O(NRC), sementara kompleksitas langkah kedua O(RC). Karena langkah pertama terlalu lambat, cara ini akan mendapat TLE.

Seandainya setiap pipa mengeluarkan air dengan kekuatan yang sama, soal ini dapat diselesaikan dengan mudah:

1. Untuk setiap petak yang memiliki pipa, masukkan lokasi petak itu ke queue.
2. Lakukan ekspansi (seperti pada BFS) sebanyak kekuatan air dari pipa.
3. Lakukan BFS dari petak awal ke petak tujuan, tanpa melewati petak yang basah.

Strategi ini dapat segera diadopsi untuk menyelesaikan persoalan ini. Ketimbang memasukkan semua petak berisi pipa ke dalam queue, cukup masukkan pipa-pipa dengan kekuatan air terkuat terlebih dahulu.

Misalkan kekuatan air pipa yang terkuat adalah T. Apabila Anda melakukan ekspansi node (seperti pada BFS), sebenarnya sama saja dengan memasukkan pipa-pipa baru dengan kekuatan T-1. Tambahkan pipa-pipa dengan kekuatan T-1 yang ada pada kasus uji (bila ada) ke dalam queue, lalu lakukan hal itu secara terus menerus. Proses ini mirip seperti BFS yang di-pause, lalu ditambahkan isinya berkali-kali. Berhubung setiap petak hanya akan masuk ke dalam queue, diproses, dan dikeluarkan dari queue maksimal satu kali, maka kompleksitasnya O(RC) saja. Lanjutkan dengan BFS, maka cukup untuk mendapatkan AC :)

Tambahan:

Saat pembahasan, ada siswa (kalau tidak salah, Candra Ramsi Gunawan?) yang menawarkan solusi:

1. Untuk setiap petak yang memiliki pipa, tandai daerah sekitarnya yang terkena semburan airnya. Namun hanya boundary-nya saja, atau kelilingnya. Dengan kata lain, proses ini hanya membutuhkan maksimal O(min(R,C)).
2. Lakukan BFS dari petak awal ke petak tujuan, tanpa melewati petak yang basah.

Kompleksitas akhirnya adalah O(N min(R,C) + RC), dan cukup cepat untuk AC. Sepertinya cara ini juga tidak memiliki celah yang menjadikannya WA. Luar biasa!

---

Komentar

Mempersiapkan kontes untuk siswa selalu tidak mudah. Sulit memperkirakan kemampuan siswa zaman sekarang, dan mengatasi masalah ketimpangan (ada yang sangat kuat, ada yang masih pemula). Namun saya cukup senang karena set soal ini dapat menahan sang juara sampai 164 menit (hampir 4 jam) untuk menyelesaikan semua soal.