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}$$
Dengan $k_x$ menyatakan perkalian seluruh faktor $x$ yang bukan 3.

Kini kita perlu mencari jumlahan barisan $k_x$. Saya akan menyebut barisan ini dengan nama "barisan ampas" karena setiap elemennya seperti sisa bilangan setelah seluruh faktor 3-nya diperas habis.

Beberapa nilai pertama barisan ampas adalah:

1 2 1 4 5 2 7 8 1 10 11 4 13 14 5 ...

Perhatikan bilangan yang tidak digaris bawah. Elemen di posisi bukan kelipatan 3 dijamin tidak berubah, karena mereka tidak mengandung faktor 3. Jumlahan elemen-elemen tersebut dapat dinyatakan dengan jumlah bilangan dari 1 sampai $3^N$, dikurangi dengan jumlah elemen di posisi kelipatan 3:
$$\sum_{i=1}^{3^N} i - 3\sum_{i=1}^{3^{N-1}} i$$
Sekarang kita tinggal menambahkannya dengan jumlahan bilangan-bilangan di posisi kelipatan 3. Coba kita kumpulkan nilainya dulu:

    1     2     1       4       5 ...

Ternyata ada pola yang berulang, nilai tersebut sama persis dengan barisan ampas. Perbedaannya hanya banyaknya elemen barisan ini adalah sepertiga sebelumnya, yakni $3^{N-1}$. Ini bukan kebetulan semata karena pembagian dari barisan 3, 6, 9, 12, 15, ... dengan 3 akan memunculkan 1, 2, 3, 4, 5, ...
Hal ini memberikan ide penyelesaian rekursif.

Apabila kita definisikan $f(N)$ sebagai jumlahan barisan ampas pada awalnya, kini dapat dirumuskan:
$$f(N) = \sum_{i=1}^{3^N} i - 3\sum_{i=1}^{3^{N-1}} i + f(N-1)$$
Tetapkan base case-nya saat $N=0$, yang mana $f(0)=1$.

Untuk menghitung jumlah dari 1 sampai $3^N$ secara cepat, gunakan rumus deret aritmetika:
$$\sum_{i=1}^{3^N} i = \frac{3^N(3^N+1)}{2}$$
Sayangnya rumus ini tidak langsung dapat digunakan dengan modulo, karena ada pembagian dengan 2. Berhubung nilai modulonya dan 2 saling prima, kita dapat menggunakan invers modulo. Singkat cerita, perhitungannya menjadi:
$$\sum_{i=1}^{3^N} i \bmod M= 3^N(3^N+1)2^{M-2} \bmod M$$
(jangan lupa untuk mencari $2^{M-2}$ dengan pemangkatan fast exponentiation).

Sekarang tinggal menghitung nilai $f$ dari 0 sampai dengan N seperti DP bottom up.
Setiap pertanyaan kini dapat dijawab dengan mencari $3^N f(N)$. Solusi ini bisa diimplementasikan dalam $O(N)$.

---

Perpustakaan Blangkon

Soal sederhana kalau sudah tahu struktur data hash table atau BST. Cukup pakai unordered_map atau map pada C++. Kompleksitas solusi akhirnya $O(N+M)$, dengan asumsi panjang judul buku tidaklah signifikan.

---

Sepotong Batik

Bagian yang merepotkan dari soal ini adalah pola mungkin terpotong di atas, kiri, bawah, atau kanan.

Untuk sedikit meringankan kerepotan, saya akan menambah seluruh koordinat dengan satu.
Lalu gunakan strategi 2D partial sum. Misalkan $f(i, j)$ menyatakan banyaknya titik warna utama dari posisi $(1, 1)$ sampai $(i, j)$. Mencari banyaknya titik warna dari $(r_1, c_1)$ sampai dengan $(r_2, c_2)$ sama dengan mencari:
$$f(r_2, c_2) - f(r_2, c_1-1) - f(r_1-1, c_2) + f(r_1-1, c_1-1)$$
Perhatikan ilustrasi berikut untuk jelasnya:

Pencarian jumlahan elemen di (r₁, c₁) sampai (r₂, c₂) dengan 2D partial sum.

Karena sekarang koordinat kiri atas selalu $(1, 1)$, kita hanya perlu khawatir dengan pola-pola yang terpotong di bagian bawah atau kanan.

Pencarian banyaknya titik warna dapat dipecah menjadi beberapa langkah:

1. Buang semua jarak antar pola (vertikal maupun horizontal). Misalkan kini banyaknya baris dan kolom adalah rClean dan cClean.
2. Hitung banyaknya baris yang sepenuhnya mengandung pola (tanpa peduli apakah ada pola terpotong di kanannya).
3. Lakukan iterasi i=1 sampai dengan A, dan hitung banyaknya titik warna di posisi (i, 1) sampai dengan (i, cClean). Kalikan jawabannya dengan banyaknya baris yang sepenuhnya mengandung pola.
4. Untuk pola yang terpotong di bawah, iterasi i=1 sampai dengan rClean%A, dan hitung banyaknya titik warna di posisi (i, 1) sampai dengan (i, cClean).

Pencarian titik warna dari posisi (i, 1) sampai dengan (i, cClean) pun dapat menggunakan strategi yang serupa. Yang penting Anda hati-hati dalam menghitung indeksnya.

Dengan cara ini, fungsi $f$ dapat dihitung dalam $O(A)$.
Sangat cukup untuk mendapatkan accepted.

---

Komentar

Soal favorit saya adalah KPK, dan saya rasa ada solusinya yang lebih mudah. Kalau Anda tahu, mohon beritahu saya.

Sentuhan akhir yang saya sarankan adalah penyeragaman format soal. Pada set soal ini, ada soal formatnya multicase dan menggunakan prefix "Kasus #x: ...", sementara soal lainnya tidak. Meskipun rasanya kurang penting untuk menyamakan formatnya, menurut saya ini akan memberikan kesan lebih artistik.

Seluruh kode solusi dapat diunduh di sini.
Saya akan membahas pembahasan semifinal pada tulisan mendatang.