Nov 102010
 

F – Searching in Tree

Author: Felix Halim

Deskripsi Permasalahan

Soal F adalah soal tersulit di ACM-ICPC INC 2010 dan hanya ada satu tim yang berhasil menyelesaikannya!

Dari sisi algoritma sebenarnya soal ini tidak terlalu susah, tapi codingnya akan panjang. Felix Halim yang membuat soal ini solusinya sekitar 200 baris. Eko Wibowo yang juga membuat solusi soal ini dan memerlukan sekitar 120 baris. Dan tim Dongskar Pedongi II yang berhasil menyelesaikan soal ini mengirim code dengan panjang lebih dari 400 baris.

Mencari nilai k-th terkecil dari sebuah subtree bisa diselesaikan dengan membangun AVL-Tree atau Red Black Tree dari subtree yang dicari. AVL-Tree atau RB-Tree memiliki tinggi yang balance sehingga pencarian nilai ke-k bisa dilakukan dalam O(lg N).

Karena querynya ada banyak (bisa mencapai 10000) maka tidak mungkin kita membangun AVL-Tree untuk setiap query karena dengan demikian total kompleksitasnya menjadi O(Q . N . lg N). Untuk mengatasi hal ini, kita harus memproses setiap query secara post-order. Ketika kita memproses sebuah node, kita harus merge AVL-Tree dari semua child node kita. Saat merge, kita harus mempertahankan AVL-Tree dari child yang memiliki node terbanyak (node dari child lain dipush ke AVL-Tree tersebut). Dengan demikian setiap node akan berpindah tree tidak lebih dari log(N) kali, sehingga total kompleksitas yang diperlukan adalah O(Q.lg N + N.lg2 N).

Solusi Eko Wibowo sedikit berbeda, dia menggunakan Segment Tree. Gw ga terlalu ngerti dan katanya dia mau ngeblog (entah jadi apa kagak), jadi ya kita tunggu aja blog dia :-D.

Statistik Problem F
YES = 1
NO – Wrong Answer = 5
NO – Time Limit Exceeded = 15
NO – Runtime Error = 1
NO – Compile Error = 3


  13 Responses to “ACM-ICPC Indonesia National Contest 2010”

  1. hahay,,,,akhirnya clear,,,sampe mas felix nulis status “SUSU MANTAP” !! 😀

  2. Solusi F gw bukan 200 baris… itu banyak functions yang gak kepake.

    Solusi gw sekitar 100 baris setelah gw bersihin:

    http://felix-halim.net/story/inc10/f.php

  3. BTW, bukankah di tabel soal D, baris ke-0 dan kolom ke-0
    semestinya -1?

  4. Soal F solusi “standard” nya pake segment tree.

    jadi pertama treenya di label (awal, akhir) dulu, misal:

    int v = 0;
    void dfs(int node)
    {
    label[node].awal = v++;
    for each child c
    dfs(c);
    label[node].akhir = v++;
    }

    Maka semua descendants dari node x bisa didefine as semua node y dimana x.awal = y.akhir. Kondisinya bisa disederhanakan jadi: x.awal <= y.awal dan x.akhir >= y.awal. In other words, untuk tiap query x, kita perlu proses nodes y dimana x.awal <= y.awal awalnya doank yg penting.

    Pertanyaannya, bagaimana cara akses nodes tsb dengan cepat?
    Solusinya bisa pakai segment tree.

    Pertama.. semua “label” tadi bisa dibagi jadi segment2
    [0, N)
    [0, N/2) [N/2, N]
    [0, N/4) [N/4, N/2) [N/2, 3N/4) [3N/4, N]

    Jadi untuk query x, kita bisa cari O(lg N) disjoint segments yg meng-cover semua descendants of x. Untuk mencari k-th smallest element, bisa pake binary search, i.e., tembak angka a, cek berapa node yg <= a di tiap segment. Jawabannya adalah smallest integer a dimana (jumlah angka = k.

    Next, bagaimana mencari jumlah node yg O(N lg N) per level dengan space complexity O(N lg N) –> O(N) per level.
    Karena angkanya sudah urut, maka tiap segment bisa diproses dalam O(lg^2 N).

    Total time complexity = Q lg^3 N + N lg^2 N. Faktor lg^3 nya kayaknya bisa dikurangi kalo perlu..

  5. well.. kayaknya ada bbrp tulisan yg kehapus gara2 pake lebih kecil dan lebih besar hehehe… silakan ditebak2 deh :p

  6. @ardian : shakehand , punya gua yang F juga gtu hahaha

  7. Kayaknya yang Sum To Zero itu inputnya belum tentu “set” ya … Satu set yg n bilangan itu kayaknya ada yg dobel.

  8. @lego : iya,bukan “set”secara matematis

  9. Soal D: notasi ‘triplet’-nya ambigu, {1, 2, 3} saya kira sama dengan {2, 3, 1} soalnya pakai notasi set. Wikipedia: A triplet is a set of three items.

    • Di wiki disebutnya: A triplet is a set of three items. It may refer to: … # Tuple of length 3 in mathematics
      Dan definisi Tuple adalah: In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an (ordered) n-tuple is a sequence (or ordered list) of n elements, where n is a positive integer
      Dari sana jelas bahwa triplet ini adalah *ordered* set. Karena ordered set itu termasuk set, notasi set sah-sah aja, karena sudah disebut sebagai triplet.

  10. saya pake map. ga TLE :p

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)