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