Nov 102010
 

I – Maximum Sum in Matrix

Author: Suhendry Effendy

Deskripsi Permasalahan

Soal I adalah soal tambahan yang gw siapkan untuk menyeimbangkan proporsi soal mudah dan susah.

Solusi soal I tidak susah, cukup dengan dynamic programming (DP) sederhana, kalau belum ngerti DP coba belajar dulu :-). Permasalahan soal ini bisa dinyatakan dalam relasi rekurens f(r,c,k) yang artinya berapa jumlah maksimum yang bisa didapatkan jika sekarang kita berada di baris ke r dan kolom c dan maksimum kita hanya bisa berpindah k kali.

Dari baris ke r, kita harus bergerak ke baris ke r+1. Kita bisa memilih apakah kolom yang ditempati di baris r+1 sama dengan kolom pada r yaitu c atau berbeda/pindah dengan catatan k masih lebih besar dari 0. Sehingga relasi rekurens f(r,c,k) bisa dinyatakan dengan:

f(r,c,k) = max{Ar,c + f(r+1,i,x)} dengan i = 1..C, x = k jika i = c dan x = k-1 jika i != c. x harus lebih besar sama dengan 0.

Kompleksitas program DP yang diperlukan adalah O(R.C2.K), cukup untuk mendapatkan accepted di soal ini.

Statistik Problem I
YES = 20
NO – Wrong Answer = 22
NO – Time Limit Exceeded = 21
NO – Runtime Error = 5
NO – Compile Error = 4


  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)