Rasanya sudah lama sekali semenjak terakhir kali saya mempublikasi tulisan. Mohon maaf karena kesibukan yang luar biasa di kampus, jadinya ngeblognya tertunda.
Kali ini saya akan membahas soal dari UVa 12357 - Ball Stacking. Seperti biasa, karena soal ini menarik dan diskusinya di internet masih sangat sedikit.
Pada soal ini, terdapat N(N+1) bola yang bertumpuk. Lapisan paling bawah memiliki N bola, disusul dengan lapisan berikutnya dengan N-1 bola, lalu N-2 bola, dan seterusnya hingga 1 bola di paling atas. Setiap bola memiliki nilai. Perhatikan gambar berikut untuk kejelasan:
Kita dapat mengambil sejumlah bola, dengan syarat bahwa jika suatu bola diambil, bola-bola di lapisan atasnya yang bersentuhan langsung dengan bola tersebut harus diambil juga. Sebagai contoh, pengambilan bola bernilai -2 mengharuskan kita mengambil bola 2, -8, -5, 3, dan 3. Total nilai yang didapat sama dengan total nilai setiap bola yang diambil. Tentukan total nilai maksimal yang mungkin kita dapatkan!
Untuk mempermudah visualisasi, kita ubah tampilan tumpukan di gambar 1 menjadi:
Observasi:
Jika bola B[x][y] kita ambil, maka seluruh bola B[x][i], dimana i < y, juga harus diambil dan bola B[x][j], dimana j > y, tidak bisa diambil lagi. Observasi ini melahirkan pernyataan bahwa untuk setiap kolom, kita bisa memilih suatu bola yang dijadikan acuan sehingga seluruh bola di atas dan bola acuan itu sendiri akan diambil. Kita sebut bola ini "bola acuan".
Kita coba pilih bola-bola acuan tersebut dari kiri ke kanan. Jika dipilih B[x][y], maka bola acuan di sebelah kanan yang mungkin adalah salah satu dari:
B[x+1][y+1]
B[x][y+1]
B[x-1][y+1]
B[x-2][y+1]
:
B[y+1][y+1],
Untuk memperjelas, perhatikan gambar berikut
Mengapa demikian? Jika bola yang terakhir diambil adalah bola hijau, bola d tidak bisa menjadi acuan karena nantinya bola cokelat menjadi tidak terambil.
Pilihan mana yang paling optimal? Kita gunakan DP untuk memilihnya. Definisikan f(x, y) sebagai total nilai maksimum yang bisa didapatkan dengan memilih bola acuan di kolom 0 sampai y, dan terakhir kali kita mengambil bola B[x][y] sebagai acuan. Jawaban kita berada di nilai maksimum f(x,y), untuk sembarang x dan y.
Bila dituliskan, rumusnya memang agak kompleks. Namun bila diaplikasikan ke bentuk kode dengan mengacu pada ilustrasi gambar 2, tentunya akan lebih mudah.
Terdapat O(N2) kemungkinan untuk x dan y di fungsi f. Di setiap f(x, y), kita mencari nilai optimalnya dengan iterasi i mulai dari y+1 sampai x+1. Paling ekstrim untuk x = N-1 dan y = 0, banyaknya iterasi menjadi O(N). Selain itu, di setiap iterasi i kita perlu mengiterasi j untuk menghitung nilai yang didapatkan dengan memilih bola acuan B[i][y+1]. Iterasi j maksimal O(N) dan akan dilakukan O(N) kali (karena i), sehingga secara keseluruhan untuk menghitung f(x, y) diperlukan O(N2). Kompleksitas solusi ini adalah O(N4). Karena nilai N bisa sampai 1000, kompleksitas ini masih sangat buruk.
Optimisasi pertama dapat dilakukan dengan menggunakan teknik partial sum. Buat P[x][y] dengan definisi:
Sehingga rumus DP sebelumnya dapat disederhanakan menjadi:
Nilai P[i][y+1] - P[y][y+1] selalu konstan, jadi bisa dikeluarkan dari pencarian max:
Sekarang, kompleksitas algoritma DP kita menjadi O(N3). Masih saja belum cukup untuk mendapatkan accepted karena N bisa sampai 1000.
Optimisasi berikutnya dapat dilakukan dengan memperhatikan bagaimana cara tabel DP itu diisi secara bottom up. Sebagai contoh, bila tabel diisi sesuai dengan rumus di atas, kodenya kurang lebih seperti (saya gunakan pseudocode dengan indeks array zero based):
Terdapat redundansi di bagian loop ke-3:
Ketimbang melakukannya berulang kali, kita akan menjaga (keep track) sebuah variabel K yang menyimpan nilai maksimal dari dp[i][y+1] untuk i dari y+1 sampai x+1 saat ini. Untuk iterasi x berikutnya, nilai ini diperbaharui dengan cara membandingkannya dengan dp[x+1][y+1]. Kodenya kurang lebih seperti ini.
Sebagai tambahan, kompleksitas memori DP ini juga dapat dioptimisasi dengan menggunakan teknik flying table. Perhatikan nilai dp[x][y] hanya dipengaruhi dp[][y+1], tetapi tidak dipengaruhi dp[][y+2], dp[][y+3], dst. Oleh karena itu, sebenarnya tabel DP kita cukup 1000 * 2 saja, dua kolom itu akan digunakan bergantian. Artinya, pada awalnya dp[][N-1] ditempatkan di dp[][0], lalu dp[][N-2] di dp[][1]. Berikutnya dp[][N-3] ditempatkan lagi di dp[][0] dengan referensi untuk perhitungannya di dp[][1] (ingat bahwa dp[][1] berisi informasi dp[][N-2]). Teknik ini hanya bisa digunakan untuk pengisian tabel DP tertentu secara bottom up.
Berikut ini implementasi saya dalam C++:
Kali ini saya akan membahas soal dari UVa 12357 - Ball Stacking. Seperti biasa, karena soal ini menarik dan diskusinya di internet masih sangat sedikit.
Pada soal ini, terdapat N(N+1) bola yang bertumpuk. Lapisan paling bawah memiliki N bola, disusul dengan lapisan berikutnya dengan N-1 bola, lalu N-2 bola, dan seterusnya hingga 1 bola di paling atas. Setiap bola memiliki nilai. Perhatikan gambar berikut untuk kejelasan:
Kita dapat mengambil sejumlah bola, dengan syarat bahwa jika suatu bola diambil, bola-bola di lapisan atasnya yang bersentuhan langsung dengan bola tersebut harus diambil juga. Sebagai contoh, pengambilan bola bernilai -2 mengharuskan kita mengambil bola 2, -8, -5, 3, dan 3. Total nilai yang didapat sama dengan total nilai setiap bola yang diambil. Tentukan total nilai maksimal yang mungkin kita dapatkan!
Untuk mempermudah visualisasi, kita ubah tampilan tumpukan di gambar 1 menjadi:
3 -5 3 -8 2 -8 3 9 -2 7Sekarang didapatkan sebuah "matriks" yang hanya terisi separuh. Mari kita sebut angka yang tertulis di bola baris ke-i dan kolom ke-j sebagai B[i][j]. Bola paling atas adalah B[0][0] dan bola di barisan paling bawah adalah B[N-1][i] (untuk i dari 0 sampai N-1).
Observasi:
Jika bola B[x][y] kita ambil, maka seluruh bola B[x][i], dimana i < y, juga harus diambil dan bola B[x][j], dimana j > y, tidak bisa diambil lagi. Observasi ini melahirkan pernyataan bahwa untuk setiap kolom, kita bisa memilih suatu bola yang dijadikan acuan sehingga seluruh bola di atas dan bola acuan itu sendiri akan diambil. Kita sebut bola ini "bola acuan".
Kita coba pilih bola-bola acuan tersebut dari kiri ke kanan. Jika dipilih B[x][y], maka bola acuan di sebelah kanan yang mungkin adalah salah satu dari:
B[x+1][y+1]
B[x][y+1]
B[x-1][y+1]
B[x-2][y+1]
:
B[y+1][y+1],
Untuk memperjelas, perhatikan gambar berikut
- Jika sebelumnya dipilih bola acuan ungu, maka calon bola acuan di sebelah kanan adalah bola a.
- Jika sebelumnya dipilih bola acuan biru, maka calon bola acuan di sebelah kanan adalah bola a dan b.
- Jika sebelumnya dipilih bola acuan hijau, maka calon bola acuan di sebelah kanan adalah bola a, b, dan c.
- Jika sebelumnya dipilih bola acuan cokelat, maka calon bola acuan di sebelah kanan adalah bola a, b, c, dan d.
- Jika sebelumnya dipilih bola acuan jingga, maka calon bola acuan di sebelah kanan adalah bola a, b, c, dan d.
Mengapa demikian? Jika bola yang terakhir diambil adalah bola hijau, bola d tidak bisa menjadi acuan karena nantinya bola cokelat menjadi tidak terambil.
Pilihan mana yang paling optimal? Kita gunakan DP untuk memilihnya. Definisikan f(x, y) sebagai total nilai maksimum yang bisa didapatkan dengan memilih bola acuan di kolom 0 sampai y, dan terakhir kali kita mengambil bola B[x][y] sebagai acuan. Jawaban kita berada di nilai maksimum f(x,y), untuk sembarang x dan y.
\(\displaystyle
f(x,y) = \left\{
\begin{array}{ll}
0&, y = N\\
\max_{y+1 \le i \le x+1}\left(\left( \sum\limits_{j=y+1}^{i} B[j][y+1] \right)+ f(i,y+1) \right)&, y < N \end{array} \right. \)
f(x,y) = \left\{
\begin{array}{ll}
0&, y = N\\
\max_{y+1 \le i \le x+1}\left(\left( \sum\limits_{j=y+1}^{i} B[j][y+1] \right)+ f(i,y+1) \right)&, y < N \end{array} \right. \)
Bila dituliskan, rumusnya memang agak kompleks. Namun bila diaplikasikan ke bentuk kode dengan mengacu pada ilustrasi gambar 2, tentunya akan lebih mudah.
Terdapat O(N2) kemungkinan untuk x dan y di fungsi f. Di setiap f(x, y), kita mencari nilai optimalnya dengan iterasi i mulai dari y+1 sampai x+1. Paling ekstrim untuk x = N-1 dan y = 0, banyaknya iterasi menjadi O(N). Selain itu, di setiap iterasi i kita perlu mengiterasi j untuk menghitung nilai yang didapatkan dengan memilih bola acuan B[i][y+1]. Iterasi j maksimal O(N) dan akan dilakukan O(N) kali (karena i), sehingga secara keseluruhan untuk menghitung f(x, y) diperlukan O(N2). Kompleksitas solusi ini adalah O(N4). Karena nilai N bisa sampai 1000, kompleksitas ini masih sangat buruk.
Optimisasi pertama dapat dilakukan dengan menggunakan teknik partial sum. Buat P[x][y] dengan definisi:
\(\displaystyle
P[x][y] = \left\{
\begin{array}{ll}
0 & ,x=0 \\
P[x-1][y] + B[x][y]& ,x>0
\end{array}
\right.
\)
P[x][y] = \left\{
\begin{array}{ll}
0 & ,x=0 \\
P[x-1][y] + B[x][y]& ,x>0
\end{array}
\right.
\)
Sehingga rumus DP sebelumnya dapat disederhanakan menjadi:
\(\displaystyle
f(x,y) = \left\{
\begin{array}{ll}
0&, y = N\\
\max_{y+1 \le i \le x+1}\left( P[i][y+1] - P[y][y+1] + f(i,y+1) \right)&, y < N \end{array} \right. \)
f(x,y) = \left\{
\begin{array}{ll}
0&, y = N\\
\max_{y+1 \le i \le x+1}\left( P[i][y+1] - P[y][y+1] + f(i,y+1) \right)&, y < N \end{array} \right. \)
Nilai P[i][y+1] - P[y][y+1] selalu konstan, jadi bisa dikeluarkan dari pencarian max:
\(\displaystyle
f(x,y) = \left\{
\begin{array}{ll}
0&, y = N\\
(P[i][y+1] - P[y][y+1]) + \max_{y+1 \le i \le x+1} f(i,y+1) &, y < N \end{array} \right. \)
f(x,y) = \left\{
\begin{array}{ll}
0&, y = N\\
(P[i][y+1] - P[y][y+1]) + \max_{y+1 \le i \le x+1} f(i,y+1) &, y < N \end{array} \right. \)
Sekarang, kompleksitas algoritma DP kita menjadi O(N3). Masih saja belum cukup untuk mendapatkan accepted karena N bisa sampai 1000.
Optimisasi berikutnya dapat dilakukan dengan memperhatikan bagaimana cara tabel DP itu diisi secara bottom up. Sebagai contoh, bila tabel diisi sesuai dengan rumus di atas, kodenya kurang lebih seperti (saya gunakan pseudocode dengan indeks array zero based):
for y <- N-2 .. 0
for x <- y .. N-1
maxVal = 0
for i <- y+1 .. x+1
maxVal = max(maxVal, dp[i][y+1])
dp[x][y] = P[i][y+1] - P[y][y+1] + maxValTerdapat redundansi di bagian loop ke-3:
- Misalkan saat ini nilai y = 2, dan x = 10. Loop ke-3 akan menjalankan i dari 3 (hasil y+1) sampai 11 (hasil x+1), memeriksa dp[i][y+1] yang paling maksimum.
- Untuk loop ke-2 berikutnya, nilai y = 2 dan x = 11 dan yang dilakukan look ke-3 adalah menjalankan i dari 3 (hasil y+1) sampai 12 (hasil x+1), memeriksa dp[i][y+1] yang paling maksimum.
Ketimbang melakukannya berulang kali, kita akan menjaga (keep track) sebuah variabel K yang menyimpan nilai maksimal dari dp[i][y+1] untuk i dari y+1 sampai x+1 saat ini. Untuk iterasi x berikutnya, nilai ini diperbaharui dengan cara membandingkannya dengan dp[x+1][y+1]. Kodenya kurang lebih seperti ini.
for y <- N-2 .. 0
maxVal = max(0, dp[y][y+1])
for x <- y .. N-1
maxVal = max(maxVal, dp[x+1][y+1])
dp[x][y] = P[i][y+1] - P[y][y+1] + maxValSekarang kompleksitas DP kita adalah O(N2), cukup untuk mendapatkan accepted!Sebagai tambahan, kompleksitas memori DP ini juga dapat dioptimisasi dengan menggunakan teknik flying table. Perhatikan nilai dp[x][y] hanya dipengaruhi dp[][y+1], tetapi tidak dipengaruhi dp[][y+2], dp[][y+3], dst. Oleh karena itu, sebenarnya tabel DP kita cukup 1000 * 2 saja, dua kolom itu akan digunakan bergantian. Artinya, pada awalnya dp[][N-1] ditempatkan di dp[][0], lalu dp[][N-2] di dp[][1]. Berikutnya dp[][N-3] ditempatkan lagi di dp[][0] dengan referensi untuk perhitungannya di dp[][1] (ingat bahwa dp[][1] berisi informasi dp[][N-2]). Teknik ini hanya bisa digunakan untuk pengisian tabel DP tertentu secara bottom up.
Berikut ini implementasi saya dalam C++:
Tidak ada komentar :
Posting Komentar