SPOJ MTREE - Another Tree Problem

Saat iseng mencari soal di SPOJ, tiba-tiba saya mendapatkan soal yang menarik. Soal itu adalah SPOJ - MTREE. Terlihat mudah, tetapi tidak begitu. Oleh sebab itu saya akan membahasnya. Saya juga menyarankan Anda untuk mencoba mengerjakan soal itu terlebih dahulu.

Cara paling sederhana adalah dengan mencoba semua N² kemungkinan path, lalu mengalikan keseluruhannya dalam O(N). Sehingga kompleksitas akhirnya O(N³) dan jelas TLE. Cara yang lebih cepat adalah mengalikan sambil mencoba semua kemungkinan jalur, sehingga kompleksitasnya O(N²). Cara ini juga jelas TLE.

Untuk ide menyelesaikannya, mari sederhanakan persoalannya terlebih dahulu. Misalkan tree yang diberikan adalah binary tree yang memiliki root (rooted binary tree), dan kita tertarik untuk mencari bobotnya (sesuai dengan deskripsi soal).

Perhatikan gambar berikut untuk penjelasan di bagian-bagian berikutnya:

Untuk suatu node x, bobot dari subtree yang memiliki root di x adalah jumlah dari bobot subtree kanan dan subtree kiri dari x, ditambah dengan bobot semua path yang melewati x. Bila dituliskan:
f(x) = f(x.right) + f(x.left) + pass(x)

Dengan f(x) adalah jumah dari bobot subtree yang memiliki akar di x, dan pass(x) adalah bobot semua path yang melewati x. Bagaimana cara menghitung pass(x)? Idenya adalah dengan "memadukan" semua path dari anak kiri dan anak kanan x.

Bobot semua path dari anak kiri x adalah:
e + ea + eb + ebc + ebd

Atau sebenarnya dapat ditulis ulang
e(1 + a + b + bc + bd)
e(1 + a + b(1 + c + d))
e(1 + a(1) + b(1 + c(1) + d(1)))

Sementara untuk anak kanan x:
f + fg + fh
f(1 + g(1) + h(1))

Dapatkah anda mengamati polanya? Bila bobot untuk semua path dari suatu subtree yang berakar di x adalah g(x), maka:
g(x) = 1 + g(x.left) + g(x.right)

Berhubung pass(x) dapat dihitung dengan:
(e + ea + eb + ebc + ebd)(f + fg + fh)
atau
e(1 + a + b + bc + bd)f(1 + g + h)
atau
e*g(y) * f*g(z)

Namun ada yang kurang, yaitu bobot untuk path yang berujung pada x. Untuk itu, cukup tambahkan dengan:
e*g(y) + f*g(z)

Jadi, bisa disimpulkan:
pass(x) = (e*g(y) * f*g(z)) + (e*g(y) + f*g(z))

Secara umum:
pass(x) = (w[x][x.left]*g(x.left) * w[x][x.right]*g(x.right)) + (w[x][x.left]*g(x.left) + w[x][x.right]*g(x.right))

Dengan w[a][b] adalah bobot untuk edge antara node a dengan b.

Nilai g(x) untuk sembarang x bisa dicari dengan satu kali DFS, kompleksitasnya O(N). Sementara nilai f(x) untuk sembarang x juga dapat dicari dengan satu kali DFS, kompleksitasnya O(N) juga (setelah semua nilai g(x) diketahui). Dengan begitu, kita mendapatkan solusi O(N) untuk persoalan ini jika tree yang diberikan adalah rooted binary tree.

Kembali ke persoalan sebenarnya, dengan banyaknya child dari suatu tree bisa lebih dari dua. Algoritma yang sudah kita dapatkan tadi bisa dikembangkan untuk menyelesaikan persoalan ini. Bobot untuk suatu node x yang memiliki child c₁, c₂, ..., c_k adalah:
f(x) = f(c₁) + f(c₂) + ... + f(c_k) + pass(x)

Dengan:

\(\displaystyle
pass(x) = \left( \sum_{\begin{array}{c} c_1,c_2 \in child[x] \\ c_1 \ne c_2 \end{array}} {(w[x][c_1] \times g(c_1) \times w[x][c_2] \times g(c_2))} \right) + \left( \sum_{c \in child[x]} {(w[x][c] \times g(c))}\right)
\)

(akhirnya saya harus menggunakan LaTeX untuk menulis persamaan kali ini)

Algoritma ini memang berjalan dengan lancar. Namun ketika banyaknya child dari suatu node sangat besar, maka waktu yang diperlukan sangat lambat. Coba perhatikan bagian dalam kurung pertama pada persamaan pass(x). Kasus terburuk untuk algoritma ini adalah tree yang berbentuk seperti bintang (N node, 1 root, dan N-1 node lainnya terhubung pada root tersebut). Kompleksitas terburuknya O(N²).

Sekarang kita coba mengurangi loop O(N²) di bagian perhitungan pass(x). Untuk mempermudah penulisan rumus, definisikan:

• c₁, c₂, ..., c_k adalah child dari x
• δ_i menyatakan w[x][c_i]*g(c_i)

Jika nilai k = 4, maka nilai yang perlu dihitung adalah: 

δ₁δ₂ + δ₁δ₃ + δ₁δ₄ + δ₂δ₃ + δ₂δ₄ + δ₃δ₄

Persamaan dapat disederhanakan menjadi:

δ₁(δ₂ + δ₃ + δ₄) + δ₂(δ₃ + δ₄)+ δ₃(δ₄)

Perhatikan pola variabel yang berada di dalam kurung! Polanya untuk sembarang k:

δ₁(δ₂ + δ₃ + ... + δ_k) + δ₂(δ₃ + δ₄ + ... + δ_k)+ ... + δ_k-1(δ_k) + δ_k(0)

Nilainya terus berkurang sesuai dengan δ_i yang sedang menjadi pengali. Jika diketahui nilai-nilai δ₁, δ₂, ..., δ_k,  perhitungan itu bisa dilakukan dalam O(N) dengan algoritma berikut:

P <- δ₁ + δ₂ + δ₃ + ... + δ_k

total <- 0

untuk i dari 1 sampai k, laksanakan:

   P <- P - δ_i

   total <- total + δ_i*P

return total

Karena kita berhasil mereduksi kompleksitas perhitungan bagian pertama dari pass(x) dari O(N²) menjadi O(N), artinya algoritma sebelumnya berhasil dikembangkan untuk menyelesaikan persoalan sebenarnya dengan kompleksitas O(N) juga.

Sebagai gambaran, berikut ini implementasi saya dalam C++:
syntax highlighting tutorial