Nov 102010
 

Yohooooo! cepat ya write-up nya selesai, gw keren B-). Kali ini yang ngeganggu kehidupan gw di YM makin banyak: Felix Halim, Eko Wibowo, Evan Leonardi, Ashar Fuadi, Ryan Leonel, Petruk Risan dan Ilham. Untung kelar, jadi bisa menikmati hidup damai untuk beberapa saat.

Soal INC 2010 udah diupload di grader TOKI, cek di sini.

Eko Wibowo juga udah ngeblog tentang INC 2010, silakan liat di sini.

Soal dan pembahasan solusi bisa dilihat di sini:

Sedikit cerita tentang babak final bisa dibaca di sini: cerita

Scoreboard bisa dilihat di sini: scoreboard

  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)