Friday, 18 October 2013

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 N2 kemungkinan path, lalu mengalikan keseluruhannya dalam O(N). Sehingga kompleksitas akhirnya O(N3) dan jelas TLE. Cara yang lebih cepat adalah mengalikan sambil mencoba semua kemungkinan jalur, sehingga kompleksitasnya O(N2). 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 c1, c2, ..., cadalah:
f(x) = f(c1) + f(c2) + ... + f(ck) + 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(N2).

Sekarang kita coba mengurangi loop O(N2) di bagian perhitungan pass(x). Untuk mempermudah penulisan rumus, definisikan:
  • c1, c2, ..., ck adalah child dari x
  • δi menyatakan w[x][ci]*g(ci)
Jika nilai k = 4, maka nilai yang perlu dihitung adalah: 
δ1δ+ δ1δ+ δ1δ+ δ2δ+ δ2δ+ δ3δ4

Persamaan dapat disederhanakan menjadi:
δ1+ δ+ δ4) + δ2+ δ4)+ δ34)

Perhatikan pola variabel yang berada di dalam kurung! Polanya untuk sembarang k:
δ1+ δ+ ... + δk) + δ2+ δ4 + ... + δk)+ ... + δk-1k) + δk(0)

Nilainya terus berkurang sesuai dengan δyang sedang menjadi pengali. Jika diketahui nilai-nilai δ1, δ2, ..., δ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(N2) 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

3 comments :

  1. Thanks a lot. Nice explanation.

    ReplyDelete
    Replies
    1. You're welcome
      Glad to know that the translation works well :)

      Delete
    2. Sir it's amazing explanation . Had it originally been in English, out would have been much better :) still, thanks again!!

      Delete