Nov 102010
 

E – Playing with Boxes

Author: Suhendry Effendy

Deskripsi Permasalahan

Soal E sebenarnya tidak terlalu susah, tapi akan susah jika tidak bisa melihat bagaimana cara menyelesaikannya. Tapi jadi mudah karena bisa diselesaikan dengan mencari pola :). Saya merasa sebagian besar peserta berhasil menyelesaikan soal E bukan dengan mencari solusi yang benar secara langsung, tapi dengan mencari pola dari jawaban pada kasus kecil. Felix Halim salah satu pembuat soal juga menyelesaikan soal E dengan cara yang sama (mencari pola) :).

Perhitungan kombinasinya akan sulit ditemukan jika kita memandang soal ini secara langsung (memecah tumpukan balok hingga menjadi N tumpukan). Kalaupun ditemukan, biasanya akan bingung bagaimana bisa menyelesaikan perhitungan kombinasi tersebut dengan cepat karena N bisa mencapai 100000.

Solusi soal ini jauh lebih mudah ditemukan jika kita melihat soal ini secara terbalik, bukan dari satu tumpukan dipecah-pecah menjadi N tumpukan tapi dari N tumpukan digabung-gabung hingga menjadi satu tumpukan. Mula-mula ada N balok dan kita diminta untuk memilih dua balok untuk ditumpuk jadi satu, ada berapa cara memilihnya? Tentunya ada C(N,2) dengan C adalah fungsi kombinasi (pilih 2 dari N item). Setelah kita menggabungkan dua balok, kita kembali disuruh memilih dua tumpukan dari N-1 tumpukan yang ada, ada berapa cara memilihnya? Tentunya ada C(N-1,2). Lakukan proses ini hingga menjadi tinggal 1 tumpukan.

Dengan demikian total kombinasi yang ada bisa dihitung dengan: C(N,2) * C(N-1,2) * C(N-2,2) * … * C(3,2) * C(2,2). Seperti yang kita ketahui C(K,2) bisa dihitung dengan K*(K-1)/2, sehingga untuk menghitung jawaban yang diminta kita hanya perlu melakukan iterasi satu kali saja. Total kompleksitas yang diperlukan adalah O(N).

Statistik Problem E
YES = 19
NO – Wrong Answer = 54
NO – Time Limit Exceeded = 12
NO – Runtime Error = 23
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)