Seperti yang pernah saya janjikan sebelumnya, inilah pembahasan CP CompFest tingkat Mahasiswa. Seluruh kode sumber untuk pembahasan di bawah ini bisa diunduh dari sini.
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.
Menggunakan algoritma O(N2) 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.
Soal ini dapat dimodelkan menjadi:
Diberikan sejumlah titik pada bidang dan sejumlah pertanyaan yang berbunyi:
"Nilai dot product minimum dari titik P dengan salah satu titik yang ada pada bidang adalah ...."
Selain yang ada pada soal, rumus dot product yang lain adalah:
\(\vec{a} \cdot \vec{b} = |\vec{a}||\vec{b}| \cos{\theta}\)
Bila \(\vec{a}\) merupakan vektor titik P (yang ada pada pertanyaan), maka rumusnya menjadi:
\(\vec{P} \cdot \vec{b} = |\vec{P}||\vec{b}| \cos{\theta}\)
Karena \(|\vec{P}|\) konstan, tinggal dicari \(|\vec{b}| \cos{\theta}\) yang paling minimum. Perhatikan gambar berikut dan misalkan P adalah titik yang berwarna merah:
Observasi 1:
Berhubung \(|\vec{b}| \cos{\theta}\) sama dengan panjang proyeksi vektor \(\vec{b}\) terhadap vektor \(\vec{P}\), maka supaya hasilnya minimum titik b harus merupakan titik pertama yang dijumpai garis g, dengan g adalah garis yang tegak lurus dengan vektor \(\vec{P}\) dan bergerak menuju ke arah sumbu x dan y positif. Perhatikan rangkaian gambar untuk 3 kemungkinan P berikut:
Observasi tersebut merupakan observasi yang penting, karena setelah mengetahuinya, kita bisa membuang semua titik yang tidak penting. Titik-titik yang tidak penting adalah titik-titik yang bukan anggota "kaki kiri" convex hull dari semua titik itu. Yang dimaksud "kaki kiri" dari convex hull adalah yang ditandai pada gambar berikut:
Dikatakan tidak penting karena titik-titik selain anggota kaki tersebut tidak mungkin menjadi solusi untuk b.
Observasi 2:
Untuk menjawab pertanyaan, perhatikan bahwa jawabannya sangat bergantung pada gradien titik (0, 0) ke P. Titik P dengan gradien terbesar akan optimal bila dipasangkan dengan titik paling kanan "kaki" tersebut. Sebaliknya, semakin kecil gradiennya maka akan optimal bila dipasangkan dengan titik di daerah kiri.
Misalkan:
K = [T1, T2, ..., Tm] adalah kaki kiri convex hull, terurut dari yang koordinat x-nya paling kecil.
L = [P1, P2, ..., PQ] adalah pertanyaan-pertanyaan yang sudah terurut berdasarkan aturan yang dijelaskan sebelumnya.
Pertama kita cari pasangan optimal untuk P1. Dipastikan, Tm adalah pasangan optimalnya. Untuk menghitung P2, pasangannya mungkin Tm lagi, atau Tm-1, atau bahkan Tm-x, dimana (x < m). Oleh karena itu, kita dapat menggunakan:
i <- m
selama dot(P2, Ti-1) < dot(P2, Ti)
i <- i-1
Catatan: dot(A, B) menyatakan dot product dari vektor posisi titik A dan B
Maka selepas dari while itu, i dijamin berhenti pada pasangan optimalnya. Strategi ini juga dapat dilanjutkan untuk mencari P3, P4, dan seterusnya. Sebagai catatan, nilai i di sini akan terus berkurang (karena observasi 2). Berhubung m bisa sama dengan N, kompleksitas untuk menjawab pertanyaan dengan cara ini adalah O(Q + N).
Terdapat cara lain untuk menjawab pertanyaan, yaitu dengan binary search. Untuk mencari pasangan Pi, lakukan binary search pada K. Dijamin, bentuk grafik dot(Pi, Tj) adalah kurva berbentuk U. Sehingga tinggal dicari titik terendahnya. Kompleksitas untuk menjawab pertanyaan adalah O(Q log N).
Secara keseluruhan, diperlukan O(N log N) untuk melakukan convex hull, dan O(Q + N) atau O(Q log N) untuk menjawab pertanyaan. Dengan kata lain, kompleksitas akhirnya O(N log N + Q) atau O((N + Q) log N).
Soal ini menuntut kita menentukan pemilihan seoptimal mungkin di antara banyak pilihan. Sayangnya, DP tidak dapat diterapkan karena state yang dimiliki terlalu besar.
Bila diperhatikan lebih lanjut, persoalan ini bisa direduksi menjadi permasalahan menjodohkan. Terdapat sekumpulan soal, dan sekumpulan pilihan jawaban. Pilihan jawaban ke-i hanya dapat dijodohkan maksimal Bi kali. Tentukan penjodohan semaksimal mungkin!
Masalah semacam ini dapat diselesaikan dengan bipartite matching, atau dalam soal ini bisa dikatakan max flow.
Buat bipartite graph, dengan himpunan node pertama adalah himpunan soal (1..N), dan yang kedua adalah himpunan pilihan jawaban (1..P). Bila soal ke-i memiliki pilihan jawaban benar ke-j, maka buat edge dari node himpunan pertama yang ke-i, menuju ke node himpunan kedua yang ke-j, dengan kapasitas 1. Setelah itu, hubungkan semua node di himpunan pertama ke node dummy sebagai supersource dengan kapasitas 1, dan hubungkan semua node di himpunan kedua ke node dummy lain sebagai supersink dengan kapasitas Bj.
Setelah graph itu dikonstruksi, lakukan max flow dari supersink ke supersource. Karena banyaknya node dan edge kecil, penggunaan algoritma max flow sederhana seperti Ford-Fulkerson seharusnya cukup untuk AC.
Kalimat yang penting pada soal ini adalah:
"Probabilitas selai ini independen satu dengan selai lainnya."
Dengan begitu, penyelesaian untuk kue ke-j dapat ditinjau dari tiap-tiap selai.
Untuk selai ke-i, peluang dia baru digunakan pada kue yang ke-j adalah:
\(p = X_i (1-X_i)^{j-1}\)
Sementara nilai expected-nya untuk seluruh selai pada kue yang ke-j:
\(\displaystyle E[j] = \sum_{i=1}^{N} (1 \times p + 0 \times (1 - p))\)
Atau cukup ditulis saja:
\(\displaystyle E[j] = \sum_{i=1}^{N} (X_i (1-X_i)^{j-1})\)
Dengan rumus itu, jawaban bisa dicari dalam O(NM). Sayangnya ini terlalu lambat dan mendapatkan TLE.
Untuk mempercepat, perhatikan bahwa maksimal hanya ada 101 nilai \(X_i\) yang berbeda. Oleh karena itu, perhitungan untuk beberapa \(X_i\) yang sama bisa dilakukan secara bersamaan. Rumus itu bisa dirubah menjadi:
\(\displaystyle E[j] = \sum_{i=0}^{100} ( i (1-i)^{j-1} K_i)\)
Dengan \(K_i\) adalah banyaknya selai yang peluang digunakannya i%. Kompleksitas akhir solusi ini O(100M), cukup untuk mendapatkan AC. Jawabannya adalah E[1] + E[2] + ... + E[M].
Bila Anda sudah terbiasa dengan soal DP, maka soal ini Selesaikan dengan DP:
f(i,s) adalah banyaknya representasi s dengan i buah bilangan yang berada di antara 1 sampai 9. Hubungan rekursifnya:
\(\displaystyle
f(i,s) = \left\{
\begin{array}{ll}
1 &, i = 0 \wedge s = 0\\
0 &, i = 0 \wedge s \ne 0\\
\sum_{d=1}^{9} {f(i-1, s-d)} &, i > 0
\end{array} \right. \)
Kompleksitas DP itu O(NM). Berhubung kasus ujinya banyak, perhitungan DP untuk setiap kasus akan mendapatkan TLE. Sebenarnya, tabel DP tidak perlu dihitung ulang untuk kasus uji yang berbeda. Hal ini disebabkan karena formulasi DP sudah berlaku secara umum (tinggal nilai N dan M saja yang menentukan jawabannya). Sehingga kita bisa melakukan prekomputasi untuk mendapatkan semua kemungkinan jawaban, lalu ditanya tinggal melihat isi tabelnya saja. Dengan cara ini, kompleksitas solusi secara keseluruhan kasus uji O(T + NM).
Untuk memeriksa apakah suatu DNA stabil atau tidak, bisa dengan cara:
Sayangnya, pemeriksaan seperti itu membutuhkan O(N), dengan N adalah panjang untaian DNA. Bila ada Q operasi pemeriksaan, diperlukan O(QN) yang sudah jelas TLE.
Untuk mempercepat, sepertinya dapat digunakan struktur data segment tree. Mengapa "sepertinya"? Karena biasanya soal semacam ini memang diselesaikan dengan struktur data berwujud tree.
Observasi 1:
String DNA yang diberikan bisa dinyatakan dalam array bilangan yang isinya +1 atau -1 (seperti yang dijelaskan di atas). Untuk mempermudah pemrosesan, nilai yang disimpan adalah jumlahan kumulatifnya dari posisi pertama. Untuk selanjutnya, "elemen ke-i" mengacu pada jumlahan kumulatif dari posisi pertama sampai posisi ke-i.
Observasi 2:
Mengubah suatu karakter di posisi ke-i dari '(' menjadi ')' sama saja dengan mengganti +1 menjadi -1. Akibatnya, elemen ke-i sampai seterusnya akan berkurang sebanyak 2. Hal yang serupa bila perubahan karakternya adalah dari ')' menjadi '(', elemen ke-i sampai seterusnya akan bertambah sebanyak 2.
Observasi 3:
Untuk memeriksa kestabilan DNA, diperlukan informasi nilai jumalahan kumulatif yang terkecil (mininum dari elemen ke-0, elemen ke-1, ..., elemen ke-(N-1)) dan jumlahan seluruh +1/-1 pada string (sama saja dengan elemen ke-(N-1)).
Berdasarkan observasi tersebut, kita membutuhkan segment tree dengan kemampuan:
Untuk mendukung kemampuan itu, buat segment tree yang menyimpan 4 nilai agregat:
Dengan penerapan lazy propagation, kompleksitas untuk setiap operasi update dapat dilaksanakan dalam O(log N). Sehingga kompleksitasnya bisa menjadi O(Q log N).
Tambahan:
Solusi yang saya jelaskan di atas adalah solusi dari Cakra. Bila saya yang mengerjakannya, saya akan membuat 2 struktur data:
Kode sumber untuk solusi alternatif ini bisa Anda lihat pada berkas G2.cpp pada tautan di atas.
Cara paling sederhana adalah mencoba setiap pasang node, lalu cari jaraknya. Kompleksitasnya O(N3). Seperti biasa, cara brute force ini akan mendapatkan TLE. Cara yang lebih baik dengan mencoba setiap node, lalu DFS ke seluruh node lainnya juga kurang cepat untuk AC, karena kompleksitasnya O(N2).
Untuk meningkatkan efisiensi, kita pandang persoalan ini dari sisi yang lain: untuk setiap jalan, hitung nilai kontribusi jalan itu pada hasil akhirnya.
Dengan kata lain, untuk setiap jalan kita hitung berapa pasang kota a dan b yang harus melewati jalan itu bila seseorang berjalan dari kota a itu ke kota b. Perhitungan itu bisa dilakukan dalam O(1) setelah melakukan prekomputasi.
Prekomputasi yang perlu dilakukan:
Perhatikan kedua gambar berikut. Bila jalan yang sedang ingin dihitung kontribusinya adalah jalan (u, v), maka banyaknya pasangan kota yang harus melewati jalan itu untuk berpergian adalah (child[r] - child[u]) × child[v].
Prekomputasi child dapat dilakukan dalam O(N), dan pencarian jawaban juga dalam O(N). Sehingga kompleksitas akhirnya adalah O(N).
Soal yang paling berkesan bagi saya adalah soal pembiakan hibrida. Soal ini saya rancang ketika sedang menunggu kereta untuk pulang dari Depok ke Jakarta, dan memang bagi saya kereta adalah sumber inspirasi yang baik untuk pembuatan soal.
Cukup kaget ketika ada tim yang berhasil menyelesaikan soal ini karena biasanya soal-soal geometri cukup dihindari peserta, berdasarkan pengalaman di COMPFEST 2012 (Penelitian Semut) dan penyisihan CompFest 2013 (Bocah Pantai) buatan saya.
Saya juga was-was ketika banyak tim yang mencoba mengerjakannya dengan cara "kurang diharapkan", seperti dengan break ketika sudah melakukan sekian iterasi (monte carlo), menggunakan heuristik sudut-sudut, dan sebagainya. Beruntungnya kasus uji maut yang berbentuk "funnel" sudah disiapkan dapat menahan mereka >:-)
Terima kasih kuliah komputasional geometri!
A. Pangeran Berti
Pembuat soal: Alham Fikri AjiCukup 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 PramanaMenggunakan algoritma O(N2) 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.
C. Pembiakan Hibrida
Pembuat soal: William GozaliSoal ini dapat dimodelkan menjadi:
Diberikan sejumlah titik pada bidang dan sejumlah pertanyaan yang berbunyi:
"Nilai dot product minimum dari titik P dengan salah satu titik yang ada pada bidang adalah ...."
Selain yang ada pada soal, rumus dot product yang lain adalah:
\(\vec{a} \cdot \vec{b} = |\vec{a}||\vec{b}| \cos{\theta}\)
Bila \(\vec{a}\) merupakan vektor titik P (yang ada pada pertanyaan), maka rumusnya menjadi:
\(\vec{P} \cdot \vec{b} = |\vec{P}||\vec{b}| \cos{\theta}\)
Karena \(|\vec{P}|\) konstan, tinggal dicari \(|\vec{b}| \cos{\theta}\) yang paling minimum. Perhatikan gambar berikut dan misalkan P adalah titik yang berwarna merah:
Observasi 1:
Berhubung \(|\vec{b}| \cos{\theta}\) sama dengan panjang proyeksi vektor \(\vec{b}\) terhadap vektor \(\vec{P}\), maka supaya hasilnya minimum titik b harus merupakan titik pertama yang dijumpai garis g, dengan g adalah garis yang tegak lurus dengan vektor \(\vec{P}\) dan bergerak menuju ke arah sumbu x dan y positif. Perhatikan rangkaian gambar untuk 3 kemungkinan P berikut:
Observasi 2:
Untuk menjawab pertanyaan, perhatikan bahwa jawabannya sangat bergantung pada gradien titik (0, 0) ke P. Titik P dengan gradien terbesar akan optimal bila dipasangkan dengan titik paling kanan "kaki" tersebut. Sebaliknya, semakin kecil gradiennya maka akan optimal bila dipasangkan dengan titik di daerah kiri.
Misalkan:
K = [T1, T2, ..., Tm] adalah kaki kiri convex hull, terurut dari yang koordinat x-nya paling kecil.
L = [P1, P2, ..., PQ] adalah pertanyaan-pertanyaan yang sudah terurut berdasarkan aturan yang dijelaskan sebelumnya.
Pertama kita cari pasangan optimal untuk P1. Dipastikan, Tm adalah pasangan optimalnya. Untuk menghitung P2, pasangannya mungkin Tm lagi, atau Tm-1, atau bahkan Tm-x, dimana (x < m). Oleh karena itu, kita dapat menggunakan:
i <- m
selama dot(P2, Ti-1) < dot(P2, Ti)
i <- i-1
Catatan: dot(A, B) menyatakan dot product dari vektor posisi titik A dan B
Maka selepas dari while itu, i dijamin berhenti pada pasangan optimalnya. Strategi ini juga dapat dilanjutkan untuk mencari P3, P4, dan seterusnya. Sebagai catatan, nilai i di sini akan terus berkurang (karena observasi 2). Berhubung m bisa sama dengan N, kompleksitas untuk menjawab pertanyaan dengan cara ini adalah O(Q + N).
Terdapat cara lain untuk menjawab pertanyaan, yaitu dengan binary search. Untuk mencari pasangan Pi, lakukan binary search pada K. Dijamin, bentuk grafik dot(Pi, Tj) adalah kurva berbentuk U. Sehingga tinggal dicari titik terendahnya. Kompleksitas untuk menjawab pertanyaan adalah O(Q log N).
Secara keseluruhan, diperlukan O(N log N) untuk melakukan convex hull, dan O(Q + N) atau O(Q log N) untuk menjawab pertanyaan. Dengan kata lain, kompleksitas akhirnya O(N log N + Q) atau O((N + Q) log N).
D. Pilihan Ganda Campuran
Pembuat soal: William GozaliSoal ini menuntut kita menentukan pemilihan seoptimal mungkin di antara banyak pilihan. Sayangnya, DP tidak dapat diterapkan karena state yang dimiliki terlalu besar.
Bila diperhatikan lebih lanjut, persoalan ini bisa direduksi menjadi permasalahan menjodohkan. Terdapat sekumpulan soal, dan sekumpulan pilihan jawaban. Pilihan jawaban ke-i hanya dapat dijodohkan maksimal Bi kali. Tentukan penjodohan semaksimal mungkin!
Masalah semacam ini dapat diselesaikan dengan bipartite matching, atau dalam soal ini bisa dikatakan max flow.
Buat bipartite graph, dengan himpunan node pertama adalah himpunan soal (1..N), dan yang kedua adalah himpunan pilihan jawaban (1..P). Bila soal ke-i memiliki pilihan jawaban benar ke-j, maka buat edge dari node himpunan pertama yang ke-i, menuju ke node himpunan kedua yang ke-j, dengan kapasitas 1. Setelah itu, hubungkan semua node di himpunan pertama ke node dummy sebagai supersource dengan kapasitas 1, dan hubungkan semua node di himpunan kedua ke node dummy lain sebagai supersink dengan kapasitas Bj.
Setelah graph itu dikonstruksi, lakukan max flow dari supersink ke supersource. Karena banyaknya node dan edge kecil, penggunaan algoritma max flow sederhana seperti Ford-Fulkerson seharusnya cukup untuk AC.
E. Selai Kue
Pembuat soal: Irvan JahjaKalimat yang penting pada soal ini adalah:
"Probabilitas selai ini independen satu dengan selai lainnya."
Dengan begitu, penyelesaian untuk kue ke-j dapat ditinjau dari tiap-tiap selai.
Untuk selai ke-i, peluang dia baru digunakan pada kue yang ke-j adalah:
\(p = X_i (1-X_i)^{j-1}\)
Sementara nilai expected-nya untuk seluruh selai pada kue yang ke-j:
\(\displaystyle E[j] = \sum_{i=1}^{N} (1 \times p + 0 \times (1 - p))\)
Atau cukup ditulis saja:
\(\displaystyle E[j] = \sum_{i=1}^{N} (X_i (1-X_i)^{j-1})\)
Dengan rumus itu, jawaban bisa dicari dalam O(NM). Sayangnya ini terlalu lambat dan mendapatkan TLE.
Untuk mempercepat, perhatikan bahwa maksimal hanya ada 101 nilai \(X_i\) yang berbeda. Oleh karena itu, perhitungan untuk beberapa \(X_i\) yang sama bisa dilakukan secara bersamaan. Rumus itu bisa dirubah menjadi:
\(\displaystyle E[j] = \sum_{i=0}^{100} ( i (1-i)^{j-1} K_i)\)
Dengan \(K_i\) adalah banyaknya selai yang peluang digunakannya i%. Kompleksitas akhir solusi ini O(100M), cukup untuk mendapatkan AC. Jawabannya adalah E[1] + E[2] + ... + E[M].
F. Jumlahan Bilangan
Pembuat soal: Muhammad Febrian RamadhanaBila Anda sudah terbiasa dengan soal DP, maka soal ini Selesaikan dengan DP:
f(i,s) adalah banyaknya representasi s dengan i buah bilangan yang berada di antara 1 sampai 9. Hubungan rekursifnya:
\(\displaystyle
f(i,s) = \left\{
\begin{array}{ll}
1 &, i = 0 \wedge s = 0\\
0 &, i = 0 \wedge s \ne 0\\
\sum_{d=1}^{9} {f(i-1, s-d)} &, i > 0
\end{array} \right. \)
Kompleksitas DP itu O(NM). Berhubung kasus ujinya banyak, perhitungan DP untuk setiap kasus akan mendapatkan TLE. Sebenarnya, tabel DP tidak perlu dihitung ulang untuk kasus uji yang berbeda. Hal ini disebabkan karena formulasi DP sudah berlaku secara umum (tinggal nilai N dan M saja yang menentukan jawabannya). Sehingga kita bisa melakukan prekomputasi untuk mendapatkan semua kemungkinan jawaban, lalu ditanya tinggal melihat isi tabelnya saja. Dengan cara ini, kompleksitas solusi secara keseluruhan kasus uji O(T + NM).
G. DNA Misterius
Pembuat soal: Cakra Wishnu WardhanaUntuk memeriksa apakah suatu DNA stabil atau tidak, bisa dengan cara:
- Ubah semua '(' menjadi +1
- Ubah semua ')' menjadi -1
- Lakukan jumlahan kumulatif dari ujung kiri ke kanan. Bila pernah ada nilai negatif atau total jumlahannya bukan 0, berarti DNA tidak stabil. Selain daripada itu, berarti stabil.
Sayangnya, pemeriksaan seperti itu membutuhkan O(N), dengan N adalah panjang untaian DNA. Bila ada Q operasi pemeriksaan, diperlukan O(QN) yang sudah jelas TLE.
Untuk mempercepat, sepertinya dapat digunakan struktur data segment tree. Mengapa "sepertinya"? Karena biasanya soal semacam ini memang diselesaikan dengan struktur data berwujud tree.
Observasi 1:
String DNA yang diberikan bisa dinyatakan dalam array bilangan yang isinya +1 atau -1 (seperti yang dijelaskan di atas). Untuk mempermudah pemrosesan, nilai yang disimpan adalah jumlahan kumulatifnya dari posisi pertama. Untuk selanjutnya, "elemen ke-i" mengacu pada jumlahan kumulatif dari posisi pertama sampai posisi ke-i.
Observasi 2:
Mengubah suatu karakter di posisi ke-i dari '(' menjadi ')' sama saja dengan mengganti +1 menjadi -1. Akibatnya, elemen ke-i sampai seterusnya akan berkurang sebanyak 2. Hal yang serupa bila perubahan karakternya adalah dari ')' menjadi '(', elemen ke-i sampai seterusnya akan bertambah sebanyak 2.
Observasi 3:
Untuk memeriksa kestabilan DNA, diperlukan informasi nilai jumalahan kumulatif yang terkecil (mininum dari elemen ke-0, elemen ke-1, ..., elemen ke-(N-1)) dan jumlahan seluruh +1/-1 pada string (sama saja dengan elemen ke-(N-1)).
Berdasarkan observasi tersebut, kita membutuhkan segment tree dengan kemampuan:
- Tambahkan setiap elemen pada suatu interval dengan suatu bilangan (dalam kasus ini, +2 atau -2).
- Cari nilai minimum dari seluruh elemen
- Cari nilai dari suatu elemen
Untuk mendukung kemampuan itu, buat segment tree yang menyimpan 4 nilai agregat:
- Jumlahan dari seluruh +1/-1 pada segmen yang bersangkutan
- Nilai terkecil dari elemen-elemen pada segmen yang bersangkutan
- Nilai lazy yang perlu diteruskan ke bawah (untuk [1])
- Nilai lazy yang perlu diteruskan ke bawah (untuk [2])
Dengan penerapan lazy propagation, kompleksitas untuk setiap operasi update dapat dilaksanakan dalam O(log N). Sehingga kompleksitasnya bisa menjadi O(Q log N).
Tambahan:
Solusi yang saya jelaskan di atas adalah solusi dari Cakra. Bila saya yang mengerjakannya, saya akan membuat 2 struktur data:
- Segment tree untuk keperluan update interval dan ekstraksi nilai terkecil. Bila Anda pernah mengerjakan soal yang pernah saya rekomendasikan pada postingan tentang variasi nilai agregat (Circular RMQ), maka teknik untuk menyelesaikan soal itu dapat diaplikasikan untuk soal ini.
- Binary Indexed Tree untuk keperluan memeriksa apakah jumlahan kumulatif keseluruhannya 0.
Kode sumber untuk solusi alternatif ini bisa Anda lihat pada berkas G2.cpp pada tautan di atas.
H. Pulau Sederhana
Pembuat soal: William GozaliCara paling sederhana adalah mencoba setiap pasang node, lalu cari jaraknya. Kompleksitasnya O(N3). Seperti biasa, cara brute force ini akan mendapatkan TLE. Cara yang lebih baik dengan mencoba setiap node, lalu DFS ke seluruh node lainnya juga kurang cepat untuk AC, karena kompleksitasnya O(N2).
Untuk meningkatkan efisiensi, kita pandang persoalan ini dari sisi yang lain: untuk setiap jalan, hitung nilai kontribusi jalan itu pada hasil akhirnya.
Dengan kata lain, untuk setiap jalan kita hitung berapa pasang kota a dan b yang harus melewati jalan itu bila seseorang berjalan dari kota a itu ke kota b. Perhitungan itu bisa dilakukan dalam O(1) setelah melakukan prekomputasi.
Prekomputasi yang perlu dilakukan:
- Pilih root dari tree tersebut
- Untuk setiap node, hitung berapa banyak node yang ada pada subtree yang memiliki root di node tersebut. Selanjutnya nilai tersebut untuk node akan disebut dengan child[i].
Perhatikan kedua gambar berikut. Bila jalan yang sedang ingin dihitung kontribusinya adalah jalan (u, v), maka banyaknya pasangan kota yang harus melewati jalan itu untuk berpergian adalah (child[r] - child[u]) × child[v].
Prekomputasi child dapat dilakukan dalam O(N), dan pencarian jawaban juga dalam O(N). Sehingga kompleksitas akhirnya adalah O(N).
Komentar
Soal-soal tingkat mahasiswa ini dibuat oleh lebih banyak orang, sehingga variasi gaya soalnya lebih bervariasi daripada soal-soal tingkat SMA. Beruntungnya, tidak ada tim yang berhasil menyelesaikan seluruh soal, sehingga sampai pada akhir pertandingan semuanya masih tetap berjuang :DSoal yang paling berkesan bagi saya adalah soal pembiakan hibrida. Soal ini saya rancang ketika sedang menunggu kereta untuk pulang dari Depok ke Jakarta, dan memang bagi saya kereta adalah sumber inspirasi yang baik untuk pembuatan soal.
Cukup kaget ketika ada tim yang berhasil menyelesaikan soal ini karena biasanya soal-soal geometri cukup dihindari peserta, berdasarkan pengalaman di COMPFEST 2012 (Penelitian Semut) dan penyisihan CompFest 2013 (Bocah Pantai) buatan saya.
Saya juga was-was ketika banyak tim yang mencoba mengerjakannya dengan cara "kurang diharapkan", seperti dengan break ketika sudah melakukan sekian iterasi (monte carlo), menggunakan heuristik sudut-sudut, dan sebagainya. Beruntungnya kasus uji maut yang berbentuk "funnel" sudah disiapkan dapat menahan mereka >:-)
Terima kasih kuliah komputasional geometri!
Tidak ada komentar :
Posting Komentar