Nov 102010
 

D – Sum to Zero

Author: Suhendry Effendy

Deskripsi Permasalahan

D adalah soal paling favorit dengan total submission 442, tapi yang berhasil mendapatkan YES hanya 5 submission. Sebagian besar peserta mengirimkan program yang memiliki kompleksitas O(N3) yang melakukan looping variable i, j dan k masing-masing dari 1..N (bruteforce). Sudah jelas program yang seperti ini akan mendapatkan Time Limit Exceed karena N bisa mencapai 2000. Sepertinya masih banyak peserta yang belum paham dengan kompleksitas algoritma.

Solusi O(N2 . lg N) pun belum cukup! Solusi O(N2 . lg N) bisa didapatkan dengan terlebih dahulu mengurutkan salah satu array, misalnya array C. Kemudian untuk setiap pasang angka yang ada di array A dan B (ada N(N-1) pasang), kita cari apakah ada pasangannya di array C dengan binary search.

Contoh:
A = {-4, 3, 1, 5}
B = {3, -7, 2, -5}
C = {-5, 1, 6, 7} … C diurutkan terlebih dahulu.

Kemudian, untuk setiap pasang angka di A dan B, kita cari pasangannya di C dengan binary search. Cari apakah -(A[0] + B[0]) = -(-4 + 3) = 1 ada di C dengan binary search, apakah -(A[0] + B[1]) = -(-4 -7) = 11 ada di C dengan binary search, dst. Total pasangan ada N(N-1) dan pencarian di C memerlukan kompleksitas O(log N) sehingga kompleksitas totalnya adalah O(N2 . lg N). Tapi ini belum cukup!! Solusi ini akan mendapatkan Time Limit Exceed.

Solusi yang diharapkan adalah O(N2).

Pertama kita urutkan dulu data di A secara ascending dan data di B secara descending. Kemudian perhatikan tabel di bawah.

    -4   1   3   5  > A ascending
 3  -1   4   6   8
 2  -2   3   5   7
-5  -9  -4  -2   0
-7 -11  -6  -4  -2
 v
 B descending

Kita mulai pencarian setiap pasangan pada array C pada tabel di atas dari kiri-atas di mana i = 0 dan j = 0, dengan i adalah index untuk A dan j adalah index untuk B. Jika kita perhatikan, setiap angka yang ada di kanan dari setiap cell selalu lebih besar dari angka di cell tersebut dan setiap angka yang ada di bawah selalu lebih kecil. Jadi ketika mencari suatu nilai, kita bisa mengetahui apakah kita harus ke kanan atau ke bawah.

Contoh, kita ingin mencari 5 (-5 di array C kita negatifkan karena kita ingin mencari pasangannya di A + B).

    -4   1   3   5
 3  -1   4   6   8
 2  -2   3   5   7
-5  -9  -4  -2   0
-7 -11  -6  -4  -2

Karena -1 lebih kecil dari 5 maka kita harus begerak ke kanan.

    -4   1   3   5
 3  -1   4   6   8
 2  -2   3   5   7
-5  -9  -4  -2   0
-7 -11  -6  -4  -2

Karena 4 lebih kecil dari 5 maka kita harus bergerak ke kanan.

    -4   1   3   5
 3  -1   4   6   8
 2  -2   3   5   7
-5  -9  -4  -2   0
-7 -11  -6  -4  -2

Karena 6 lebih besar dari 5 maka kita harus bergerak ke bawah.

    -4   1   3   5
 3  -1   4   6   8
 2  -2   3   5   7
-5  -9  -4  -2   0
-7 -11  -6  -4  -2

5 ditemukan, artinya -5 di array C memiliki pasangan di A + B.

Pencarian tidak ditemukan jika kita sudah keluar dari tabel pada sisi paling bawah atau sisi paling kanan.

Untuk melakukan sekali pencarian diperlukan O(N), sehingga total kompleksitas yang diperlukan adalah O(N2).

Solusi lain yang juga memiliki kompleksitas O(N2) adalah dengan menggunakan algoritma O(N2 . lg N) di atas namun array C bukan diurutkan melainkan dihashing, sehingga pencarian di array C hanya memerlukan O(1).

Statistik Problem D
YES = 5
NO – Wrong Answer = 52
NO – Time Limit Exceeded = 293
NO – Runtime Error = 72
NO – Compile Error = 20


  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)