UVa 10271 - Chopsticks

Soal menarik kali ini bersumber dari UVa 10271 - Chopsticks. Karena tidak banyak orang yang membahas soal ini di internet, maka saya akan membahasnya. Sedikit curhat, pertama kali saya membaca soal ini adalah pada tahun 2010. Pada saat itu saya benar-benar tidak ada ide bagaimana mengerjakannya. Di tahun 2011 akhir akhirnya saya kembali menantang soal ini, dan akhirnya accepted :D

Tugas: diberikan N batangan sumpit dengan panjang tertentu. Bentuk K triplet sumpit sedemikian sehingga biayanya seminimal mungkin. Biaya membentuk sebuah triplet sumpit sama dengan kuadrat dari selisih dua sumpit terpendek.

Misalkan kita tidak perlu mencari sumpit terpanjang untuk setiap set. Persoalan kita sekarang adalah:
Diberikan N bilangan. Buat K pasangan bilangan sedemikian sehingga jumlah kuadrat dari selisih mereka seminimal mungkin! Untuk kemudahan, anggap saja kita ingin meminimalkan biaya pemilihannya.

Observasi 1:
Untuk solusi optimal, jika bilangan-bilangan itu sudah terurut dari besar ke kecil, setiap pasangan bilangan yang kita pilih pasti bersebelahan. Dengan kata lain jika A adalah array yang menampung bilangan dan A[0] ≤ A[1] ≤ ... ≤ A[N-1], maka setiap pasangan bilangan yang kita pilih pasti berbentuk (A[i], A[i+1]) dengan 0 ≤ i < N-1. Pernyataan ini mudah untuk dibuktikan dan cukup intuitif

Cara termudah untuk mendapatkan pasangan-pasangan optimal adalah dengan dynamic programming (DP). Kita buat fungsi f(x,d) yang menyatakan biaya minimal jika kita memiliki bilangan A[0], A[1], ..., A[x] dan harus membuat d pasangan bilangan. Kita punya dua pilihan, yaitu membuat pasangan bilangan baru (A[x-1],A[x]) atau tidak membuat pasangan baru. Di antara dua pilihan itu, pilih yang menghasilkan biaya minimal. Hubungan tersebut dapat dinyatakan dalam fungsi rekursif:

\(
f(x,d) =
\left\{
\begin{array}{ll}
\infty&,x+1 \le 2d\\
0&,(x=0) \wedge (d=0)\\
min(f(x-2,d-1) + (A[x]-A[x-1])^2, f(x-1,d))&,(x \gt 0) \wedge (d \gt 0)
\end{array}
\right.
\)

Jawabannya ada di \(f(N-1,K)\). Lalu bagaimana jika kita butuh sumpit paling panjang?

Observasi 2:
Misalkan di f(x,d) kita memutuskan untuk membuat pasangan baru, yaitu (A[x],A[x-1]). Berhubung kita masih harus membuat d set sumpit, artinya kita sudah membuat K-d set sumpit sebelumnya. Sumpit yang tersisa tinggal (N-x-1)-3(K-d). Jika ada sumpit yang tersisa, dijamin sumpit ini memiliki panjang ≥ A[x]. Singkatnya, sumpit panjang untuk melengkapi pasangan (A[x],A[x-1]) ada jika (N-x-1) > 3(K-d).

Dengan begitu, kita tinggal memodifikasi hubungan rekursifnya menjadi:

\(
f(x,d) =
\left\{
\begin{array}{ll}
\infty&,x+1 \le 2d\\
0&,(x=0) \wedge (d=0)\\
min(f(x-2,d-1) + (A[x]-A[x-1])^2, f(x-1,d))&,(x \gt 0) \wedge (d \gt 0) \wedge (N-x-1 \gt 3(K-d))\\
f(x-1,d)&,lainnya
\end{array}
\right.
\)

Dengan DP tersebut, kompleksitas algoritma kita adalah \(O(NK)\). Cukup untuk mendapatkan accepted