Seperti biasa, coba kerjakan sendiri dulu sebelum membaca tulisan ini.
Coin Exchange
Maksud soal ini adalah mencari nilai terkecil dan terbesar yang berada di antara 1 dan N (eksklusif), sehingga nilai tersebut saling prima dengan N. Sebenarnya kondisi ini tidak menjamin seluruh nilai tukar bisa direpresentasikan. Misalnya untuk N=100, nilai terkecil yang saling prima dengannya adalah 3. Meskipun demikian, kita tidak bisa menggunakan 100 dan 3 untuk transaksi senilai 1, 2, 4, 5, 7, 8, dsb.Untuk mencari bilangan yang saling prima, cukup periksa dari 2 sampai N-1 untuk bilangan yang FPB-nya dengan N sama dengan 1. Begitu ditemukan, langsung hentikan pencarian. Nilai inilah yang menjadi nilai terkecil. Lakukan cara serupa dengan pencarian dari N-1 sampai 2 untuk mencari nilai terbesarnya. Terakhir, cetak selisih mereka.
Solusi ini terkesan \(O(N)\), tetapi sebenarnya jauh lebih cepat dari itu. Sebab sangat besar kemungkinan \(N-k\) untuk \(k\) yang cukup kecil mengakibatkan FPB-nya dengan N sama dengan 1. Sebagai contoh, nilai 99 sudah saling prima dengan N=100. Demikian pula 1000000 dan 999999.
Hitung Kata
Ini soal DP yang cukup sederhana. Idenya seperti longest common subsequence (LCS), tetapi kali ini seluruh karakter di string kedua wajib dicocokkan. Apabila berhasil dicocokkan, tambahkan kemungkinan jawaban dengan 1.
Misalkan kedua string memiliki indeks yang dimulai dari 1. Seperti pada LCS, kita proses karakter demi karakter dari belakang.
Jika \(f(i, j)\) menyatakan banyaknya subsequence dari \(S[1..i]\) yang sama dengan \(P[1..j]\), maka pilihannya adalah:
\[ f(i,j) = \left\{\begin{array}{ll}
1 & ,j = 0\\
0 & ,i=0 \land j>0\\
f(i-1,j) + f(i-1,j-1) & ,S[i]=P[j]\\
f(i-1,j) & ,S[i] \ne P[j]\\
\end{array}\right. \]
Sebelum mengimplementasikannya, saya menyadari kalau tidak ada modulo. Lalu saya bertanya-tanya apakah jawabannya muat ditampung dalam integer 64 bit. Jawaban terbesar dicapai apabila \(S\) berisi 'A' sebanyak 1000 karakter, dan \(P\) berisi 'A' pula sebanyak 10 karakter. Jawabannya adalah 1000 kombinasi 10, yang mana melebihi batas atas integer 64 bit.
Karena malas menggunakan big integer, saya coba submit saja. Ternyata accepted :))
Kompleksitas solusi ini \(O(|S||P|)\).
Misalkan kedua string memiliki indeks yang dimulai dari 1. Seperti pada LCS, kita proses karakter demi karakter dari belakang.
Jika \(f(i, j)\) menyatakan banyaknya subsequence dari \(S[1..i]\) yang sama dengan \(P[1..j]\), maka pilihannya adalah:
- Buang \(S[j]\), sehingga banyaknya cara pencocokan menjadi \(f(i-1, j)\).
- Cocokkan \(S[i]\) dengan \(P[j]\), sehingga banyaknya cara pencocokan mejadi \(f(i-1, j-1)\). Pilihan ini hanya tersedia kalau \(S[i] = P[j]\).
Base case dicapai apabila:
Secara matematis, bisa dituliskan:- \(j\) bernilai 0, yang artinya pencocokan berhasil.
- \(i\) bernilai 0, tetapi \(j\) bukan 0, yang artinya pencocokan tidak berhasil.
\[ f(i,j) = \left\{\begin{array}{ll}
1 & ,j = 0\\
0 & ,i=0 \land j>0\\
f(i-1,j) + f(i-1,j-1) & ,S[i]=P[j]\\
f(i-1,j) & ,S[i] \ne P[j]\\
\end{array}\right. \]
Sebelum mengimplementasikannya, saya menyadari kalau tidak ada modulo. Lalu saya bertanya-tanya apakah jawabannya muat ditampung dalam integer 64 bit. Jawaban terbesar dicapai apabila \(S\) berisi 'A' sebanyak 1000 karakter, dan \(P\) berisi 'A' pula sebanyak 10 karakter. Jawabannya adalah 1000 kombinasi 10, yang mana melebihi batas atas integer 64 bit.
Karena malas menggunakan big integer, saya coba submit saja. Ternyata accepted :))
Kompleksitas solusi ini \(O(|S||P|)\).
Kerja Pak Blangkon
Observasi yang penting adalah setiap pekerjaan dapat diselesaikan dalam 1 hari, sehingga pekerjaan yang lebih menguntungkan pasti dipilih terlebih dahulu.
Observasi kedua, suatu pekerjaan dipilih pasti lebih baik kalau pengerjaannya ditunda selama mungkin (kalau bisa dikerjakan saat deadline saja). Strategi ini memaksimalkan kemungkinan pengerjaan kerjaan lain deadline-nya lebih ketat.
Dari kedua observasi tersebut, kita bisa menggunakan algoritma greedy sebagai berikut:
Untuk mencari hari terdekat dengan deadline, dibutuhkan struktur data yang menyimpan sejumlah elemen dan mendukung operasi berikut secara efisien:
Masalah ini dapat diatasi dengan path compression seperti pada struktur data disjoint set. Lalu kenapa kita tidak menggunakan disjoint set saja?
Observasi kedua, suatu pekerjaan dipilih pasti lebih baik kalau pengerjaannya ditunda selama mungkin (kalau bisa dikerjakan saat deadline saja). Strategi ini memaksimalkan kemungkinan pengerjaan kerjaan lain deadline-nya lebih ketat.
Dari kedua observasi tersebut, kita bisa menggunakan algoritma greedy sebagai berikut:
- Urutkan semua pekerjaan dari yang penghasilannya terbesar.
- Periksa pekerjaan satu per satu dari yang penghasilannya terbesar, lalu rencanakan pengerjaannya sedekat mungkin dengan deadline (kalau bisa saat deadline). Kalau ada hari yang mungkin, berarti pilih pekerjaan ini.
Untuk mencari hari terdekat dengan deadline, dibutuhkan struktur data yang menyimpan sejumlah elemen dan mendukung operasi berikut secara efisien:
- Tandai elemen ke-x sebagai terhapus.
- Cari elemen ke-x. Apabila elemen ke-x telah terhapus, cari elemen terbesar yang kurang dari x dan belum terhapus.
Ini seperti tugas yang cocok untuk linked list. Namun perhatikan bahwa elemennya tidak pernah dibuang, dan hanya ditandai sebagai terhapus. Kalau menggunakan linked list, operasi kedua bisa jadi tidak O(1). Perhatikan gambar berikut:
 |
| Setelah elemen ke-4 dan ke-3 dihapus, operasi pencarian elemen yang belum dihapus sebelum elemen ke-4 menjadi tidak O(1). |
Masalah ini dapat diatasi dengan path compression seperti pada struktur data disjoint set. Lalu kenapa kita tidak menggunakan disjoint set saja?
Kedua operasi itu dapat dilayani dengan sempurna dengan disjoint set.
Awalnya setiap elemen menunjuk ke dirinya sendiri. Operasi pertama dilakukan dengan menggabungkan elemen ke-x dengan kelompok elemen ke-(x-1). Penggabungan ini wajib dilakukan dengan mengganti parent dari x menjadi ujung dari parent elemen ke-(x-1).
 |
| Setelah penghapusan elemen ke-4 dan ke-3, penghapusan elemen ke-5 dilakukan dengan mengganti parent-nya menjadi parent dari elemen ke-4. Pencarian parent elemen ke-4 akan memicu path compression sehingga dia langsung menunjuk ke elemen ke-2, sehingga operasi yang melibatkan pencarian parent elemen ke-4 di masa depan efisien. |
Strategi ini menjamin ujung dari parent elemen ke-x selalu menunjuk ke elemen sebelumnya yang belum terhapus. Sehingga untuk melayani operasi kedua, cukup cari ujung dari parent x. Teknik ini saya pelajar di Pelatnas 2 TOKI 2011.
Solusi ini dapat diimplementasikan dalam \(O(N \log{N})\) dengan pengurutan dan disjoint set.
Smart City
Nilai terbesar \(N\) pada soal ini adalah 100. Jadi bisa saja kalau kita coba semua kemungkinan pasangan titik, dan periksa apakah jalurnya mengandung dua titik rusak. Kompleksitasnya \(O(N^3)\), dan cukup untuk accepted.
Optimisasi sederhana adalah mencoba semua kemungkinan titik awal, lalu DFS ke seluruh titik sambil menghitung titik akhir mana saja yang bisa dicapai. Kompleksitasnya \(O(N^2)\). Ini adalah solusi yang saya gunakan.
Optimisasi sederhana adalah mencoba semua kemungkinan titik awal, lalu DFS ke seluruh titik sambil menghitung titik akhir mana saja yang bisa dicapai. Kompleksitasnya \(O(N^2)\). Ini adalah solusi yang saya gunakan.
Your Classical OSP Problem
Berhubung pergerakannya hanya bisa ke atas atau kanan, maka setiap petak yang dimaui pasti dikunjungi dengan suatu urutan tertentu. Yang memiliki jarak manhattan terdekat dengan \((1, 1)\) akan dikunjungi pertama, disusul dengan yang terdekat kedua, dan seterusnya. Secara umum, kita dapat mengurutkan seluruh petak dimaui berdasarkan nilai baris ditambah kolomnya.
Dengan observasi tersebut, kita dapat menggunakan DP yang umum untuk soal ini secara bertahap. Kalau kalian sudah tahu apa DP yang saya maksud, silakan lompat ke paragraf selanjutnya. Misalkan \(f(i,j)\) menyatakan banyaknya cara dari \((1, 1)\) sampai \((i, j)\). Untuk mencapai \((i, j)\), kita pasti berasa dari petak di bawahnya atau di kirinya. Jadi banyaknya cara sama saja dengan penjumlahan dari banyaknya cara ke \((i-1, j)\) dan banyaknya cara ke \((i, j-1)\). Base case terjadi saat \(i=1\) dan \(j=1\), yang mana ada 1 cara untuk mencapainya. Khusus soal ini, kalau petak \((i, j)\) merupakan jurang, berarti \(f(i, j)=0\). Nilai \(f(i, j)\) juga nol apabila \(i\) atau \(j\) keluar peta. Secara matematis dirumuskan:
\[ f(i,j) = \left\{\begin{array}{ll}
1 & ,i=1 \land j = 1\\
0 & , i < 1 \lor j < 1 \\
0 & , (i, j) \in Jurang \\
f(i-1,j) + f(i,j-1) & ,(i, j) \notin Jurang\\
\end{array}\right. \]
Misalkan petak yang dimaui ke-\(i\) berada di \((r_i, c_i)\). Mulailah dengan mencari banyaknya cara dari \((1, 1)\) ke \((r_1, c_1)\) dengan DP biasa. Selanjutnya, cari banyaknya cara dari \((r_1, c_1)\) ke \((r_2, c_2)\) dengan cara yang sama, dan seterusnya sampai petak dimaui ke-\(Q\). Terakhir, lakukan hal serupa dari \((r_Q, c_Q)\) ke \((N, M)\).
Setiap DP hanya boleh memedulikan nilai yang ada di antara ujung kiri bawah dan ujung kanan atasnya. Hati-hati untuk tidak menggunakan nilai dari DP tahap sebelumnya.
Secara kolektif, solusi ini bekerja dalam \(O(NM)\).
Ada sedikit jebakan di soal ini, yaitu daftar petak yang dimaui bisa tidak unik. Jadi hati-hati kalau solusi Anda bergantung pada nilai Q.
Dengan observasi tersebut, kita dapat menggunakan DP yang umum untuk soal ini secara bertahap. Kalau kalian sudah tahu apa DP yang saya maksud, silakan lompat ke paragraf selanjutnya. Misalkan \(f(i,j)\) menyatakan banyaknya cara dari \((1, 1)\) sampai \((i, j)\). Untuk mencapai \((i, j)\), kita pasti berasa dari petak di bawahnya atau di kirinya. Jadi banyaknya cara sama saja dengan penjumlahan dari banyaknya cara ke \((i-1, j)\) dan banyaknya cara ke \((i, j-1)\). Base case terjadi saat \(i=1\) dan \(j=1\), yang mana ada 1 cara untuk mencapainya. Khusus soal ini, kalau petak \((i, j)\) merupakan jurang, berarti \(f(i, j)=0\). Nilai \(f(i, j)\) juga nol apabila \(i\) atau \(j\) keluar peta. Secara matematis dirumuskan:
\[ f(i,j) = \left\{\begin{array}{ll}
1 & ,i=1 \land j = 1\\
0 & , i < 1 \lor j < 1 \\
0 & , (i, j) \in Jurang \\
f(i-1,j) + f(i,j-1) & ,(i, j) \notin Jurang\\
\end{array}\right. \]
Misalkan petak yang dimaui ke-\(i\) berada di \((r_i, c_i)\). Mulailah dengan mencari banyaknya cara dari \((1, 1)\) ke \((r_1, c_1)\) dengan DP biasa. Selanjutnya, cari banyaknya cara dari \((r_1, c_1)\) ke \((r_2, c_2)\) dengan cara yang sama, dan seterusnya sampai petak dimaui ke-\(Q\). Terakhir, lakukan hal serupa dari \((r_Q, c_Q)\) ke \((N, M)\).
 |
| Eksekusi DP secara bertahap sesuai dengan banyaknya peta yang dimaui. Petak hitam menyatakan jurang, dan petak merah menyatakan petak dimaui. |
Secara kolektif, solusi ini bekerja dalam \(O(NM)\).
Ada sedikit jebakan di soal ini, yaitu daftar petak yang dimaui bisa tidak unik. Jadi hati-hati kalau solusi Anda bergantung pada nilai Q.
Komentar
Rasanya batasan untuk soal-soalnya dapat ditingkatkan, supaya hanya solusi yang efisien bisa accepted. Misalnya untuk soal Smart City, bisa saja dibuat nilai terbesar N=1000 supaya solusi \(O(N^3)\) tidak accepted. Demikian pula untuk soal Your Classical OSP Problem.
Secara umum soalnya menarik, dan komentar saya mirip seperti pada soal penyisihan.
Seluruh kode solusi dapat diunduh di sini.
Secara umum soalnya menarik, dan komentar saya mirip seperti pada soal penyisihan.
Seluruh kode solusi dapat diunduh di sini.
Tidak ada komentar :
Posting Komentar