Soal-soalnya dapat dilihat dan dicoba di https://tlx.toki.id/problems/joints-2019-pcs-final.
Coin Exchange 2
Solusinya mirip dengan soal Coin Exchange pada penyisihan. Cukup coba iterasi dari \(N/2\) menuju ke 2. Begitu ditemukan nilai yang FPB-nya dengan \(N\) sama dengan 1, hentikan pencarian dan cetak jawaban.Dolan 2020
Pertama, sederhanakan soal dengan menganggap suatu sel berisi 'P' sama dengan 5 sel berisi 'L':..... ..... ..... ..L.. ..P.. = .LLL. ..... ..L.. ..... .....
Sekarang tugas kita tinggal mencari persegi panjang yang sepenuhnya hanya terdiri dari 'O'.
Apabila diproses baris per baris, sadari bahwa soal ini menjadi mirip dengan suatu soal klasik: diberikan sebuah histogram, cari luas persegi panjang terbesar yang sepenuhnya dikandung histogram tersebut.
Misalkan kita memiliki konfigurasi berikut dan sedang memproses baris ketiga. Supaya lebih mudah dilihat, tanda titik menyatakan 'O'.
LL.L..L. .L....LL ....L...
Dari baris ketiga, struktur ini dapat dipandang seperti histogram berikut, dengan 'X' menyatakan bagian dari batangan histogram.
X X X XX X XXXX XXX
 |
| Ilustrasi persegi panjang terbesar yang muat dan setinggi batangan yang berwarna gelap. |
Proses setiap batangan dari kiri ke kanan, sambil menyimpan stack yang isinya hanya boleh menaik. Misalkan \(h[i]\) menyatakan tinggi batangan histogram di indeks ke-i. Untuk suatu batangan ke-\(i\):
- Selama stack tidak kosong dan \(h[stack.top()] \ge h[i]\):
- Ambil elemen paling atas stack, sebut saja \(t\), lalu buang dia dari stack.
- Indeks sekiri dan sekanan mungkin sehingga seluruh ketinggian batangan histogram di antara keduanya \(\ge h[t]\) ada di \(stack.top()+1\) dan \(i-1\). Kalau ternyata stack sudah kosong, berarti indeks terkirinya 0. Perhatikan gambar di bawah untuk intuisi mengapa ini benar.
- Baru masukkan \(i\) ke dalam \(stack\). Karena seluruh indeks yang tingginya lebih dari \(i\) sudah dibuang, dipastikan tinggi batangan pada indeks di stack ini terurut menaik.
 |
| (i) Kondisi awal stack, batangan yang berwarna gelap berada di dalam stack. (ii) Penambahan batangan terbaru di paling kanan mengakibatkan pembuangan elemen top of stack, sambil menghitung luas persegi panjang terbesar yang muat dan setinggi batangan tersebut. (iii) Peristiwa yang sama dengan (ii) masih perlu dilakukan karena tinggi elemen pada top of stack masih lebih dari tinggi elemen yang hendak dimasukkan. (iv) Kini batangan terbaru dapat dimasukkan ke dalam stack. |
Lakukan hal tersebut sampai batangan paling kanan. Terakhir, proses semua elemen tersisa yang masih ada dalam stack. Karena saya malas mengetik kode lagi, saya buat saja ada batangan baru setelah indeks terakhir dengan tinggi 0.
Setiap batangan pasti di-push sekali, dan di-pop sekali. Setiap kali suatu batangan di-pop, kita menghitung persegi panjang terbesar yang bisa dibentuk dengan batangan tersebut. Dengan cara ini, seluruh kemungkinan persegi panjang optimal telah dicoba.
Apabila algoritma ini diterapkan di seluruh baris, kompleksitasnya menjadi \(O(RC)\). Pas untuk accepted.
Gim Punakawan
Soal ini memiliki aroma DP semacam Fibonacci yang sangat kuat. Lalu melihat batasan \(N\) yang diberikan, sudah pasti ini perlu diselesaikan dengan perkalian matriks. Jadinya kita perlu mencari fungsi yang bentuknya seperti:\[f(x) = k_1f(x-1) + k_2f(x-2) + k_3f(x-3) + ...\]
Misalkan S, G, P, dan B berturut-turut menyatakan Semar, Gareng, Petruk, dan Bagong. Tugas kita menghitung banyaknya kemungkinan string yang hanya terdiri dari keempat karakter tersebut, memiliki panjang \(N\), dan memenuhi tabiat setiap punakawan.
Misalnya kita masih perlu memanggil \(x\) punakawan. Kita memiliki pilihan:
- Memanggil S. Pemanggilan selanjutnya tidak boleh S lagi. Karena tidak ingin menyimpan state tambahan dalam DP-nya, langsung saja kita tentukan siapa yang akan dipanggil selanjutnya. Kemungkinannya adalah: P, G, B. Berhubung pemanggilan B harus disusul dengan P, berarti pilihan sebenarnya adalah P, G, BP.
Jadi, ada 3 pilihan kalau kita memanggil S: SP, SG, SBP. - Memanggil G. Tidak ada syarat tambahan, dan hanya ada 1 pilihan: G
- Memanggil P. Tidak ada syarat tambahan, dan hanya ada 1 pilihan: P
- Memanggil B, yang mana harus disusul dengan P. Jadi pilihannya: BP
Keempat kemungkinan melahirkan 6 pilihan string untuk setiap pemanggilan, dengan panjang masing-masing 2, 2, 3, 1, 1, dan 2 (untuk SP, SG, SBP, G, P, dan BP).
Definisikan \(f(x)\) sebagai banyaknya kemungkinan string dengan panjang \(x\) karakter yang dapat dibuat. Dengan pilihan berupa SP, SG, SBP, G, P, dan BP, maka nilai \(f(x)\) sama dengan:
\[\begin{array}{rcl} f(x) &=& f(x-2)+f(x-2)+f(x-3)+f(x-1)+f(x-1)+f(x-2) \\
&=& f(x-3) + 3f(x-2) + 2f(x-1)
\end{array}\]
Fungsi ini rekursif, dan base case dicapai saat \(f(1)=4\), karena ada 4 kemungkinan string: S, G, P, B.
Definisikan juga \(f(0) = f(-1) = 1\), untuk mempermudah perhitungan \(f(2)\) dan \(f(3)\). Untuk memastikan fungsi kita benar, boleh dicoba menghitung \(f(2)\) dan \(f(3)\):
\[\begin{array}{rcl} f(2) &=& f(-1) + 3f(0) + 2f(1) \\
&=& 1 + 3 \cdot 1 + 2 \cdot 4 \\
&=& 12
\end{array}\]
\[\begin{array}{rcl} f(3) &=& f(0) + 3f(1) + 2f(2) \\
&=& 1 + 3 \cdot 4 + 2 \cdot 12 \\
&=& 37
\end{array}\]
Sudah sama dengan contoh masukan! Kini tinggal diubah ke versi perkalian matriks.
Kita perlu membuat 2 matriks, yaitu matriks basis dan rekurensnya.
Untuk basis, yang selanjutnya dinamakan dengan \(A\), matriksnya berukuran \(1 \times k\), dengan \(k\) adalah elemen paling lama yang dibutuhkan. Pada rumus \(f(x)\), elemen paling lama yang dibutuhkan adalah \(f(x-3)\). Jadi ukurannya \(1 \times 3\). Isi dari matriks ini adalah 3 suku berurutan pertama, yaitu \(f(-1), f(0), f(1)\):
\[A = \left[ \begin{array}{ccc}1 & 1 & 4 \end{array} \right]\]
Untuk rekurens, yang selanjutnya dinamakan dengan \(B\), matriksnya berukuran \(k \times k\). Perhatikan bahwa hasil \(A \cdot B\) adalah matriks berukuran \(1 \times k\). Tujuannya adalah membuat \(A \cdot B\) berisi \(f(0), f(1), f(2)\):
\[A \cdot B = \left[ \begin{array}{ccc}1 & 4 & 12 \end{array} \right]\]
Dengan sedikit corat-coret, nilai matriks \(B\) adalah:
\[B = \left[ \begin{array}{ccc} 0 & 0 & 1 \\ 1 & 0 & 3 \\ 0 & 1 & 2 \end{array} \right]\]
Kolom pertama dan kedua berguna untuk menggeser isi matriks \(A\) ke kiri. Sementara kolom ketiga untuk menghitung nilai \(f\) berikutnya.
Sadari bahwa \(A \cdot B\) dapat dikalikan lagi dengan \(B\), menghasilkan \(f(1), f(2), f(3)\):
\[A \cdot B^2 = \left[ \begin{array}{ccc} 4 & 12 & 37 \end{array} \right]\]
Dengan mengulang proses ini, pencarian \(f(N)\) dapat dilakukan dengan menghitung \(AB^{N-1}\) dan mengambil elemen ketiganya.
Pemangkatan matriks dapat menggunakan fast exponentiation biasa. Kompleksitas akhir solusinya adalah \(O(\log{N})\). Anda dapat melihat implementasinya pada kode yang saya cantumkan di akhir tulisan.
Kotak Ajaib
Misalnya diberikan angka berikut:1 6 5 2 3 10 14
Bila elemen terakhir harus dipilih sebagai indeks terakhir, maka ada berapa kemungkinan indeks pertama sehingga jumlah bilangan antar keduanya habis dibagi 4?
Untuk mendapatkan jawabannya, mari hitung jumlahan kumulatifnya:
kumulatif: 1 7 12 14 17 27 41
Kita perlu mencari banyaknya prefix, sehingga nilai 41 dikurangi prefix tersebut habis dibagi 4.
Berhubung kita hanya peduli dengan sisa bagi terhadap 4, mari cari sisa baginya terhadap 4:
kumulatif: 1 7 12 14 17 27 41
mod 4 : 1 3 0 2 1 3 1
Kini lebih terlihat bahwa kita cukup mencari prefix yang sisa bagi jumlahannya terhadap 4 sama dengan sisa bagi jumlahan kumulatif sejauh ini (yaitu 1). Terdapat 2 kemungkinan, yaitu posisi yang jumlahan kumulatifnya 1 atau 17. Apabila kita membuang prefix tersebut, didapatkan hasil yang habsi dibagi 4:
- 41 - 1 = 40 (jumlah subbarisan 6, 5, 2, 3, 10, 14)
- 41 - 17 = 28 (jumlah subbarisan 10, 14)
Air Mancur Gelas
Operasi yang dilakukan pada subtree biasa dapat diubah ke bentuk range update, dengan cara mengubah tree menjadi array sesuai dengan urutan in-order traversal. |
| Urutan masuk dan keluar setiap node pada in-order traversal. Gambar bagian bawah menunjukkan kapan suatu node mulai dan selesai dikunjungi. |
Operasi yang lain adalah mencari berapa nilai suatu node, yang dapat dijawab dengan mencari nilai pada indeks L[x].
Struktur data paling mudah untuk melayani range update dan single query seperti ini adalah Binary Index Tree (BIT). Ingat bahwa BIT mendukung dua operasi: update(i, v) yang menambah nilai v pada indeks ke-i, dan query(i) yang mencari jumlahan dari indeks ke-1 sampai ke-i. Kalau belum tahu tentang BIT, silakan baca tulisan ini.
Untuk range update +v di indeks antara a dan b, lakukan:
- update(a, v)
- update(b+1, -v)
Sementara pencarian nilai di indeks x dapat dilakukan dengan mencari query(x).
Solusi ini bekerja dalam \(O(Q \log{N})\).
Kelas Matematika
Ini soal tersulit, dan saya menghabiskan waktu beberapa jam memikirkannya. Pada akhirnya saya menyerah dan bertanya ke teman-teman lain. Ammar mendapatkan solusinya, yang ternyata mengejutkan. Rasanya tidak mungkin saya menemukannya.Pertama, ubah dulu bentuk persamaannya:
\[
\begin{eqnarray*}
\frac{xy}{r} &=& x - y \\
xy &=& rx - ry \\
xy + ry &=& rx \\
y(x + r) &=& rx \\
y &=& \frac{rx}{x+r}
\end{eqnarray*}
\]
Nilai \(y\) adalah bilangan bulat. Kini diketahui bahwa \(rx\) harus habis dibagi \(x+r\), atau dengan kata lainnya \(x+r\) pastilah faktor dari \(rx\).
Berhubung nilai \(x\) tidak diketahui, terdapat sebuah trik untuk mengubah nilai pembilang supaya sepenuhnya menjadi nilai yang diketahui. Untuk kasus ini, tambahkan pembilang dengan \(r^2 - r^2\):
\[
\begin{eqnarray*}
y &=& \frac{rx+r^2-r^2}{x+r} \\
&=& \frac{r(x+r)-r^2}{x+r} \\
&=& r + \frac{-r^2}{x+r} \\
&=& r + \frac{r^2}{-x-r} \\
\end{eqnarray*}
\]
Pembilangnya menjadi \(r^2\), yang nilainya diketahui. Jadi \(-x-r\) haruslah faktor dari \(r^2\). Misalnya diketahui \(d\) adalah suatu faktor \(r^2\), nilai \(x\) dapat dicari dengan:
\[
\begin{eqnarray*}
-x-r &=& d \\
-x &=& d +r \\
x &=& -d -r
\end{eqnarray*}
\]
Sebagai contoh, pada soal diberikan \(r=3\). Faktor dari \(r^2\) adalah 1, 3, dan 9. Maka nilai \(x\) yang mungkin adalah:
- -1-3 = -4
- -3-3 = -6
- -9-3 = -12
Setelah dijelaskan Ammar, saya butuh waktu untuk mencerna keajaiban ini.
Sekarang kita hanya perlu mencari seluruh faktor dari \(r^2\).
Misalnya \(p_1, p_2, p_3, \ldots, p_k\) menyatakan \(k\) bilangan prima pertama, dan \(e_1, e_2, e_3, \ldots, e_k\) menyatakan suatu bilangan asli. Nilai \(r\) dapat dituliskan dalam bentuk faktorisasi prima:
\[r = p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdot \ldots \cdot p_k^{e_k}\]
Untuk \(r^2\), faktorisasi primanya sesederhana kalikan pangkatnya dengan dua:
\[r^2 = p_1^{2e_1} \cdot p_2^{2e_2} \cdot p_3^{2e_3} \cdot \ldots \cdot p_k^{2e_k}\]Sekarang kita hanya perlu mencari seluruh faktor dari \(r^2\).
Misalnya \(p_1, p_2, p_3, \ldots, p_k\) menyatakan \(k\) bilangan prima pertama, dan \(e_1, e_2, e_3, \ldots, e_k\) menyatakan suatu bilangan asli. Nilai \(r\) dapat dituliskan dalam bentuk faktorisasi prima:
\[r = p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdot \ldots \cdot p_k^{e_k}\]
Untuk \(r^2\), faktorisasi primanya sesederhana kalikan pangkatnya dengan dua:
Kini tinggal brute force untuk setiap faktor prima \(p_i\), seberapa banyak faktor prima ini akan digunakan. Misalkan banyaknya dinyatakan sebagai \(q_i\). Nilai \(q_i\) berkisar antara 0 sampai \(2e_i\). Setelah seluruh \(q_i\) ditentukan, perkalian dari seluruh \(p_i^{q_i}\) merupakan faktor dari \(r^2\).
Supaya lebih jelas, ambil contoh \(r=12\). Faktorisasi primanya:
\[12=2^2 \cdot 3^1\]
Faktorisasi prima untuk \(r^2\):
\[144=2^4 \cdot 3^2\]
Dan berikut ialah seluruh faktor dari 144:
\[\begin{array}{l|l|l}
2^0 \cdot 3^0 = 1 & 2^0 \cdot 3^1 = 3 & 2^0 \cdot 3^2 = 9 \\
2^1 \cdot 3^0 = 2 & 2^1 \cdot 3^1 = 6 & 2^1 \cdot 3^2 = 18 \\
2^2 \cdot 3^0 = 4 & 2^2 \cdot 3^1 = 12 & 2^2 \cdot 3^2 = 36 \\
2^3 \cdot 3^0 = 8 & 2^3 \cdot 3^1 = 24 & 2^3 \cdot 3^2 = 72 \\
2^4 \cdot 3^0 = 16 & 2^4 \cdot 3^1 = 48 & 2^4 \cdot 3^2 = 144 \\
\end{array}\]
Masing-masing faktor itu tinggal dijadikan negatif, lalu dikurangi \(r\), dan didapatkanlah suatu kemungkinan \(x\).
Faktorisasi prima dapat diimplementasikan dalam \(O(\sqrt{r})\), sehingga kompleksitas solusi ini adalah \(O(\sqrt{r} + K)\) dengan \(K\) menyatakan banyaknya jawaban.
Typo!
Soal ini kelihatan seperti DP, tapi sebenarnya tidak perlu DP. Sebab hanya boleh ada 1 typo, jadi bisa saja kita coba semua kemungkinannya.Pertama, periksa apakah keduanya sama. Kalau ya, berarti bisa login.
Kalau tidak, periksa apakah panjang password asli <8. Kalau ya, berarti dijamin tidak bisa login.
Selain daripada itu, cari berapa nilai panjang password asli dikurangi panjang password diketik:
- Jika lebih dari 1 atau negatif, dipastikan tidak bisa login
- Jika sama dengan 1, berarti ada karakter yang hilang
- Jika sama dengan 0, berarti mungkin ada karakter yang salah diketik
Untuk kasus ketiga, periksa banyaknya karakter yang berbeda. Kalau tidak lebih dari 1, berarti bisa login.
Selain seluruh kasus di atas, berarti tidak bisa login.
Kompleksitasnya \(O(N^2)\) dengan \(N\) menyatakan panjang password. Ini terjadi saat kasus kedua dijumpai, karena kita harus mencocokkan string untuk \(N\) kemungkinan karakter yang hilang, dan sekali pencocokan string kompleksitasnya \(O(N)\).
Smart Village
Mari selidiki dulu tabel jenis jalan berdasarkan jenis desa.Misalkan telah ditetapkan jenis suatu desa. Untuk menghindari ada jalan berjenis 0, maka pilihan jenis desa tetangganya dapat ditentukan:
- Untuk A: B, X
- Untuk B: A, C
- Untuk C: B, X
- Untuk X: A, C
Ternyata tidak ada bedanya kalau desa ini adalah A/C, atau B/X. Dengan demikian, tabelnya dapat disederhanakan:
A/C B/X A/C 0 >0 B/X >0 0
Sekarang jadi jelas, apabila suatu desa memiliki jenis A/C, maka seluruh tetangganya wajib memiliki jenis B/X. Tidak boleh ada dua desa yang sama-sama A/C, atau sama-sama B/X. Observasi ini mengingatkan pada masalah klasik, yaitu bicoloring.
Salah satu permasalahan bicoloring adalah: diberikan sebuah graf, tentukan apakah graf ini dapat diwarnai dengan dua warna, sehingga tidak ada node bertetangga yang warnanya sama. Graf yang memenuhi sifat ini dapat disebut bicolorable.
 |
| Graf dengan 2 connected component yang masing-masing bicolorable. |
 |
| Contoh graf yang tidak bicolorable. Bagaimanapun pewarnaan yang dilakukan, tidak mungkin setiap node bertetanggaan dapat memiliki warna berbeda. |
- Mulai dari sembarang node yang belum diwarnai, warnai node tersebut dengan warna 1.
- Kunjungi seluruh tetangganya yang belum diwarnai. Mereka harus diberi warna lainnya. Ulangi proses ini sampai seluruh node yang dapat dikunjungi telah diwarnai.
- Apabila ada tetangga yang warnanya sama dengan warna node yang sedang dikunjungi, berarti komponen graf ini tidak bicolorable.
Prosedur tersebut perlu dilakukan sampai seluruh node pada graf diwarnai. Waspada bahwa mungkin saja terdapat beberapa connected component pada graf yang diberikan.
Kembali ke soal JOINTS, kita diminta menghitung banyaknya cara melabeli (=mewarnai) seluruh node. Anggap saja warna 1 terdiri dari jenis A dan C, lalu warna 2 terdiri dari jenis B dan X. Pertama, gunakan strategi greedy yang dijelaskan sebelumnya untuk memeriksa sifat bicolorable sambil menghitung banyaknya node pada setiap komponen.
Ketika suatu connected component pada graf yang memiliki \(m\) node bersifat bicolorable, berarti banyaknya cara melabeli seluruh node pada komponen tersebut adalah \(2^m \cdot 2\). Sebab setiap node memiliki dua pilihan label, entah A/C atau B/X, serta kita boleh membalik kedua warna tersebut.
Koleksi Filem Alamsyah
Ini soal termudah dari set soal ini. Cukup perlu dikuasai teknik membaca/memanipulasi string dan membuat compare function pada sorting. Karena malas, solusi yang saya gunakan adalah dengan pair pada STL C++. Kodenya tidak sedap dipandang tapi singkat untuk ditulis.Komentar
Tingkat kesulitan set soal ini jauh lebih tinggi dari semifinal. Kelihatannya soal Kelas Matematika dan Smart Village menjadi decider problem untuk kontes ini. Tim yang mampu menyelesaikannyalah yang menjadi pemenang.Seluruh kode solusi dapat diunduh di sini.
Tidak ada komentar :
Posting Komentar