May 122014
 

Soal dan pembahasan

Babak final terdiri dari 10 soal (A..J) yang dipersiapkan oleh saya dan Yudi Umar.

A. Candy Businessman (link soal)

Ini adalah soal yang paling mudah di dalam kontes ini.

Diberikan sebuah array yang terdiri dari N bilangan bulat, anda diminta untuk mencari selisih dari bilangan terbesar (highest price) dengan bilangan terkecil (lowest price) yang ada di dalam array yang diberikan. Tentunya solusi untuk soal ini cukup jelas, kita hanya perlu melakukan iterasi ke semua elemen di dalam array dan mencari elemen yang paling besar dan yang paling kecil.

B. Drilling Man (link soal)

Ini adalah soal yang paling sulit di dalam kontes ini (disclaimer: Yudi Umar yang mengatur penempatan soal, katanya sengaja ditempatkan di sebelah soal paling mudah :P).

Untuk menyelesaikan soal ini, kita memerlukan algoritma Dijkstra (untuk mencari jalur terpendek). Input peta grid yang diberikan bisa direpresentasikan ke dalam graph dengan cell sebagai node dan 4 arah pergerakan pemain sebagai edge yang menghubungkan satu node (cell) dengan node (cell tetangga) lainnya. Biaya dari sebuah edge adalah 1 jika dan hanya jika node yang dituju berisi dinding, jika tidak maka biayanya adalah 0. Dengan demikian, soal ini menjadi mencari shortest path (jalur dengan biaya terkecil, di mana biaya di sini adalah jumlah dinding yang dihancurkan sepanjang perjalanan) dari node awal (S) menuju node akhir (E).

Untuk menangani kunci kita bisa menambahkan informasi apakah pemain sudah mendapatkan kunci atau belum di setiap state pada graph (jadi di setiap state ada dua informasi: posisi pemain, dan apakah pemain memiliki kunci).

Alternatif lain (yang saya gunakan), adalah dengan mencari shortest path dari node awal (S) ke semua posisi kunci, dan shortest path dari node akhir (E) ke semua posisi kunci — dua kali Dijkstra dengan node mula-mula yang berbeda. Kemudian, untuk setiap posisi yang memiliki kunci, jumlahkan kedua biaya shortest path (dari S ke x dan dari E ke x di mana x adalah posisi tersebut). Biaya ini adalah biaya terkecil yang diperlukan oleh pemain untuk bergerak dari S, menuju kunci K di posisi x, dan kemudian menuju E. Cari posisi K yang memiliki biaya terkecil, itulah output yang diminta.

C. You Can’t Go Around! (link soal)

Kondisi yang diharuskan oleh sang raja (setiap kota hanya memiliki maksimal satu cara untuk pergi ke kota lain) adalah properti dari tree di dalam graph theory.

Perhatikan, komplemen dari jalan-jalan yang harus ditutup sedemikian sehingga total biaya jalan yang ditutup seminimal mungkin adalah jalan-jalan yang bisa dibuka sedemikian sehingga total biaya jalan yang dibuka semaksimal mungkin. Dengan demikian, permasalahan ini bisa diselesaikan dengan mencari maximum spanning tree dari graph jalan yang diberikan. Maximum spanning tree memiliki solusi yang sama dengan minimum spanning tree (MST) dengan prioritas biaya yang terbalik. MST bisa diselesaikan dengan menggunakan algoritma Kruskal.

D. Hard Word (link soal)

Ini adalah soal termudah kedua di dalam kontes ini.

Solusi dari soal ini cukup mudah, kita hanya perlu melakukan iterasi dan pengecekan terhadap jumlah 2 vokal dan 3 konsonan yang bersebelahan.

Meskipun soal ini mudah, beberapa peserta mengalami kesulitan pada soal ini. Dari pemeriksaan secara acak, saya menemukan dua jenis kesalahan yang umum:

  • Index array out of bound. Untuk memeriksa 2 vokal atau 3 konsonan yang bersebelahan tentunya kita perlu mengakses elemen array A[i], A[i+1], dan A[i+2] (pada kasus 3 konsonan). Jika iterasi i dilakukan dari 0 hingga posisi akhir string, maka i + 1 dan i + 2 nilainya akan melebihi panjang string.
  • Beberapa solusi yang menggunakan C/C++ mendeklarasikan array untuk string input dengan ukuran yang TEPAT (50). Padahal string di C memerlukan 1 elemen extra untuk menyimpan karakter NULL sebagai penanda akhir string.

E. Longest Continuous Subsequence (link soal)

Solusi naif untuk soal ini dengan melakukan pengecekan secara brute-force untuk setiap substring dari string yang diberikan. Ada O(N2) substring dan untuk mengecek satu substring diperlukan iterasi O(N), maka kompleksitas solusi ini adalah O(N3) dengan N adalah panjang string yang diberikan. Perhatikan, kita tidak perlu mengulang pengecekan untuk setiap substring (i, j), tapi kita bisa menggunakan hasil dari pengecekan untuk substring (i, j-1). Dengan kata lain, jika (i, j-1) masih memenuhi persyaratan, kita coba tambahkan elemen ke-j — menjadi substring (i, j) — dan cek apakah substring tersebut masih memenuhi persyaratan. Karena kita hanya menambahkan satu elemen, tentunya pengecekannya juga bisa dilakukan dalam O(1); hentikan pemeriksaan untuk substring yang dimulai dari i ketika (i, j) sudah tidak memenuhi persyaratan, tidak perlu dilanjutkan ke (i, j+1). Dengan demikian solusi ini menjadi O(N2), kasus terburuk terjadi ketika string (semua) yang diberikan memenuhi persyaratan, program kita akan menguji semua substring yang ada.

Solusi O(N2) untuk soal ini masih belum cukup, karena N bisa mencapai 50,000 (N2 = 2,500,000,000; rule-of-thumb: 100,000,000 memerlukan 1 detik).

Solusi di atas masih harus dioptimasi. Ketika pemeriksaan substring (i, j-1) berhasil yang kemudian diikuti oleh pemeriksaan substring (i, j) yang gagal, kita tidak perlu mengulang semua pemeriksaan untuk substring (i+1, i+1 .. j-1) — ingat, ketika (i, j) gagal di solusi sebelumnya, kita akan mengulang pemeriksaan dengan substring yang diawali oleh i+1, dimulai dari (i+1, i+1). Kita bisa mempertahankan posisi j dan memajukan posisi i hingga substring (i’, j) memenuhi persyaratan. Dengan kata lain, ketika j dimajukan, kita menambahkan satu elemen (elemen ke-j) ke dalam substring yang diperiksa, dan ketika i dimajukan, kita membuang satu elemen (elemen ke-i) dari substring yang diperiksa. Pemeriksaan substring tentunya bisa dilakukan dalam O(1) — konstan — dengan menyimpan informasi berapa jumlah kemunculan masing-masing karakter (ditambah ketika j maju, dan dikurangi ketika i maju).

Perhatikan contoh berikut, misalkan string yang diberikan adalah “AAABCCDDDE” dengan K = 3 dan pemeriksaan kita sudah sampai pada (0, 5) seperti pada contoh berikut.

...

A A A B C C D D D E
i         j              [A = 3, B = 1, C = 2]

A A A B C C D D D E
i           j            [A = 3, B = 1, C = 2, D = 1]; substring (0, 6) gagal, majukan i -- 1 (kurangi A)

A A A B C C D D D E
  i         j            [A = 2, B = 1, C = 2, D = 1]; substring (1, 6) gagal, majukan i -- 2 (kurangi A)

A A A B C C D D D E
    i       j            [A = 1, B = 1, C = 2, D = 1]; substring (2, 6) gagal, majukan i -- 3 (kurangi A)

A A A B C C D D D E
      i     j            [B = 1, C = 2, D = 1]; substring (3, 6) berhasil, majukan j -- 7 (tambah D)

A A A B C C D D D E
      i       j          [B = 1, C = 2, D = 2]

...

Karena i dan j hanya bergerak maju (dari 1 hingga N), maka total kompleksitas solusi ini adalah O(N). Stategi ini dikenal dengan nama sliding window.

F. Repairing Bridge (link soal)

Soal ini bisa diselesaikan secara langsung dengan teknik dynamic programming (yang sudah menguasai teknik DP pasti langsung menyadari solusi untuk soal ini).

G. How Many Stars? (link soal)

Hitung “gradien” semua titik terhadap titik pengamat, namun simpan “gradien” ini dalam bentuk pasangan yang disederhanakan. Contoh: (dx, dy), (2, 3), (5, 2), (3, 5), dll. (4, 6) bukanlah bentuk yang sederhana karena FPB(4, 6) adalah 2, jadi (4, 6) harus disederhanakan menjadi (2, 3) — dengan kata lain, ubah ke dalam bentuk pecahan dx/dy yang paling sederhana.

Untuk mencari bentuk sederhana dari setiap “gradien”, kita perlu mencari FPB dari setiap dua angka tersebut. FPB bisa dicari dengan mudah dengan algoritma Euclidean yang memiliki kompleksitas O(lg N).

int gcd(int a, int b) {
  return b == 0 ? a : gcd(b, a % b);
}

Pengguna C++ bisa menggunakan fungsi __gcd di library <algorithm&gt (Java juga memiliki fungsi yang serupa).

printf( "%d\n", __gcd(4, 6) );

Output untuk soal ini adalah jumlah “gradien” yang unik. Untuk mendapatkan nilai ini, urutkan semua “gradien” yang ada dan hitung ada berapa yang unik.

Beberapa peserta menggunakan perhitungan gradien (dx dibagi dengan dy). Cara ini bisa bekerja namun kita harus berhati-hati dengan kasus simetrisnya. dx-positif dan dy-positif memiliki gradien yang sama dengan dx-negatif dan dy-negatif, padahal dua titik ini tidak saling menutupi (berlawanan arah dari titik pengamat).

H. I Have a Dream (link soal)

Soal ini awalnya diajukan oleh Yudi Umar sebagai soal penyisihan, namun tingkat kesulitan soal ini jauh berbeda dengan soal-soal penyisihan yang lain, sehingga diputuskan untuk memindahkan soal ini ke final (soal Text Formatter yang ada di penyisihan seharusnya ada di final).

Begitu membaca soal ini, saya langsung memikirkan solusi DP-nya (saya pernah menemukan problem yang serupa sebelumnya). Namun batasan input yang kecil membuat soal ini bisa diselesaikan dengan cara yang jauh lebih mudah: bruteforce + greedy.

Yang perlu kita bruteforce adalah continuous subsequence (potongan array) yang akan diambil. Karena ada O(N2) potongan, maka algoritma ini memiliki kompleksitas Ω(N2) — artinya: minimal N2. Kemudian kita perlu mengevaluasi setiap potongan, dengan K yang diberikan, berapa nilai maksimum yang bisa didapatkan untuk potongan tersebut?

Perhatikan, batasan input K hanya berguna hingga N. Jadi meskipun di soal disebutkan K ≤ 1,000,000, namun K yang akan digunakan hanya K ≤ N; hanya ada N elemen yang bisa diubah.

Untuk mendapatkan nilai maksimum dari satu potongan, mula-mula kita urutkan data pada potongan tersebut secara ascending sedemikian sehingga bilangan terkecil (negatif terbesar) berada di paling depan. Kemudian, gunakan K yang diberikan untuk mengubah tanda bilangan, prioritaskan bilangan dengan negatif terbesar, abaikan bilangan yang positif. Jumlahkan bilangan-bilangan yang ada pada potongan tersebut setelah kita menggunakan K pembalik tanda yang diberikan, maka kita akan mendapatkan nilai maksimum untuk potongan tersebut. Tahap ini memiliki kompleksitas O(N lg N), karena kita perlu mengurutkan datanya. Cari potongan yang memberikan nilai maksimum. Dengan demikian kompleksitas total untuk solusi soal ini adalah O(N3 lg N).

I. Beautiful Gift (link soal)

Perhatikan, setiap nomor node anak memiliki node parent yang nomornya setengah lebih kecil, contoh: node 4 dan 5 memiliki parent node 2 (4/2 = 5/2 = 2). Dari observasi ini, maka yang kita perlu lakukan hanya menjumlahkan nomor-nomor (parent) node dari A dan B satu per satu hingga parent A dan parent B bertemu. Di setiap tahapnya, pindahkan node yang lebih besar nilainya karena node ini tidak mungkin merupakan parent dari node yang lebih kecil.

Tinggi dari complete binary tree yang memiliki N node adalah log N, dengan demikian total kompleksitas solusi ini adalah O(lg A + lg B) — kasus terburuk ketika parent A dan parent B bertemu di root, sehingga kita harus menelusuri semua node dari A hingga ke root (lg A) dan dari B hingga ke root (lg B).

J. Breaking Factorial (link soal)

Bilangan prima terbesar yang membentuk N! (N faktorial) tentunya adalah bilangan prima terbesar yang nilainya tidak lebih dari N. Dengan demikian kita hanya perlu mencari bilangan prima ini. Ada beberapa cara untuk melakukannya:

  • Generate semua bilangan prima dari 1..50000 (batasan input) dengan algoritma sieve of eratosthenes (cukup 1 kali), dan kemudian untuk setiap kasus, kita hanya perlu melakukan binary search untuk mencari elemen paling besar yang nilainya tidak lebih dari N.
  • Uji bilangan prima untuk setiap bilangan x dari x = N menurun (hingga ke 2). Pengujian perlu dilakukan secara menurun (dari N) karena jarak antar dua bilangan prima bersebelahan dari 1..50000 tidak besar, jika kita menguji secara menaik (dari 2 hingga N), maka untuk sekali pencarian kita bisa memerlukan iterasi dari 2 hingga N, terutama ketika N sendiri adalah bilangan prima. Uji bilangan prima bisa dilakukan dengan kompleksitas O(√N) — cukup menguji dari 2 hingga √N.

  46 Responses to “ACM-ICPC 2014 Provincial Sumatra”

  1. Bang, kok untuk problem H ku salah kemarin Yah.
    Padahal aku buat caranya dah persis kayak pembahasannya.

  2. bang, itu link soal no 4 kok ga bsa ya?

  3. Bang?
    Ada ga tempat submit code untuk soal ini?
    (udah diarsipkan belum bang)?

  4. Bang?
    aku agak bingung untuk pembahasan B – Drilling Man.
    abang bilang dia pake Dijkstra, nah setahuku untuk yang make Dijkstra data di Graph itu disimpan
    dalam bentuk node1, node2, weight (Adjacency List). Nah, aku bingung nyimpannya gimana bang.
    masa harus cek tiap tetangga (atas,bawah,kiri,kanan) lalu simpan.
    Aku malah lihat problem ini bisa disolved pake BFS biasa bang (belum yakin sih bisa), cuman dia ga hitung step, tapi hitung weight dari pattern yang dijalaninnya.

    CMIIW.

    • woops, baru sadar ada komen baru (ga dapat notificationnya).

      Graphnya kan sama dengan grid yang diberikan, tiap cell itu adalah node nya; jadi nggak perlu construct graph nya lagi secara terpisah.

      Kalau mau BFS, harus hati-hati, BFS itu sama dengan Dijkstra di mana cost edge nya semua uniform. Jadi kalau BFS plain, outputnya akan salah kalau ada jalan memutar jauh yang cost nya 0.

      Alternatifnya kamu bisa lakukan BFS berulang. Jadi mulai dari start, BFS ke semua tempat yang bisa dikunjungin tanpa menghancurkan tembok (record tembok mana aja yang di”kunjungi”). Putaran kedua, BFS dari tembok yang dikunjungi di putaran pertama dan kunjungi semua tempat tanpa menghancurkan tembok, dst sampai goal tercapai. — ini yang dilakukan ujung2nya sama dengan Dijkstra.

  5. bang,solusi buat soal2 ini ada ga ya?:D

    • Solusi dalam bentuk apa yang kamu cari? Di atas saya ada berikan pembahasan dan solusi untuk setiap soal (link: “Soal dan pembahasan”). Kalau yang kamu cari itu codingnya, saya nggak ada rencana untuk share itu, dan lagi, saya juga nggak punya coding solusi untuk semua soalnya.

  6. Saya coba solusi kakak untuk soal Longest Continuous Subsequence dengan code http://ideone.com/XR3nWu tapi hasilnya TLE, hint salahnya dong kak…

    • Line-20, fungsi strlen() itu kompleksitasnya O(N) dengan N = panjang string. Di line itu fungsi strlen() akan terus dipanggil di setiap perulangan. Karena perulangannya juga ada sebanyak panjang string, jadi total kompleksitasnya O(N^2). Bakal TLE u/ input N = 50,000 seperti di soal.

      Simpan nilai strlen() nya di variable, jangan compute ulang.

  7. Bang kira2 2016 kapan ya diadakan lomba ini

  8. Kak, mohon bantuannya untuk problem H nya dong.. Menurut sy udah benar dan sesuai dengan contoh test case yg ada, tapi masih wrong answer.. Salah dimana ya Kak? http://ideone.com/i673qV

    • Ini code mau nyari apa ya? Ada swap-swap gitu, rada ga nyambung sama soalnya; soalnya udah dibaca belum? ga ada swap (tukar kartu) yang diizinkan di soal, hanya flip sign (dari negatif jadi positif atau sebaliknya).

      2 1
      10 -10

      Itu outputnya koq begin > end? (1 0)

      Kalaupun kamu swap begin dan endnya, coba dengan input ini:

      5 1
      -10 -9 1 1 8

      Itu outputnya koq bisa (0 4), harusnya kan cuma (1 4). Angka yang paling kecil (-10) belum tentu bagian dari solusi.

      • Yg di swap itu sorting Kak hehe.. Bukan begitu ya caranya? Sy masih kurang paham sm maksudnya yg begin sm end Kak.. Sy cuma nyari index angka yg terkecil sm terbesar.. Mohon penjelasannya ya Kak šŸ˜€

      • Kak, mohon penjelasannya dong untuk problem H nya.. Masih kurang paham sama begin index sama end index

  9. Bg mau minta penjelasan nya bg tentang soal ideafuse
    ACM-ICPC Provincial Sumatra IdeaFuse 2014 – Penyisihan problem nya acouting

    Trimaksih Bg
    Salam

  10. Pak, boleh tanya? itu yang permasalahan E sebenarnya cuma mencari length dengan k kata yang berbeda dan menyambung?

  11. Pak, itu yang permasalahan drilling man w bingung, kalo misalnya w bikin matriks yang terdiri dari 1 dan 0 kayak flood fill kalo mau jalan melewati tembok kan harus bikin # jadinya 1, kalo gitu semua matriksnya 1 dong

    • maksudnya “semua matriksnya 1”?

      • Idenya bikin matriks baru yang sizenya sama dengan inputnya,,kalo # nilai 0, sisanya 1..kalo 1 berarti bisa jalan..
        jadi kalau mau hancurkan dinding, kita kan harus set # ke 1, otomatis matriks baru tersebut nilainya 1 semua dong kalau record yang seperti bapak bilang w g ngerti..

    • ya mana bisa gitu? kita kan mau cari berapa # yang harus ditabrak, kalo semua # diubah jadi 1 (bisa lewat), ya jadi berlebihan donk? kan ga semua # perlu diubah jadi 1.

      anw, approach kamu aneh. ini ga ngerefer ke penjelasan yang saya tulis di blog atas kan ya?

      • iya pak,, solusinya g bisa pake flood fill y?

      • Pak, statement yang bapak bilang ini “Input peta grid yang diberikan bisa direpresentasikan ke dalam graph” maksudnya gimana sih??apakan harus membentuk matriks baru untuk menyimpan nilai 0 dan 1 seperti yang saya bilang di atas, atau ada cara lain?soalnya w liat algoritma djikstra biasanya orang memakai vector<pair >

      • Di problem shortest path, biasanya cost-nya ada pada edge; tapi di soal ini cost-nya ada pada vertex (cell), jadi setiap kali kita mengunjungi sebuah cell, kita dikenakan cost pada cell tersebut.

        vector yang kamu liat itu biasanya digunakan u/ menyimpan tetangga dari suatu node. tapi di soal ini, tetangga-nya kan udah jelas: (maksimum) 4 cell yang bersebelahan: atas-bawah-kiri-kanan.

        jadi peta grid di soal ini hanya bentuk khusus dari graph general. kalau bisa menyelesaikannya pada graph general, harusnya bisa menyelesaikannya pada peta grid juga.

        di soal ini, representasi graphnya:
        – node : setiap cell.
        – edge : (at most 4) setiap cell bertetangga dengan 4 cell di sebelahnya.
        – weight/cost ada pada setiap node.

        note: cell yang di pinggir2 punya tetangga kurang dari 4.

    • floodfill itu ketika kita mau mencari area mana saja yang bisa dikunjungi tanpa mengeluarkan cost apapun. di soal ini, kita bisa melewati beberapa tempat yang sebelumnya tidak bisa dilewati dengan membayar (jadi ada cost).

      ide solusinya “mirip” floodfill, tapi harus bisa handle cost, dan cost yang kita inginkan adalah cost minimum.

      di blog atas saya ada sebut tentang Dijkstra (algoritma u/ mencari shortest path).

      • Pak, kalau lain kali ketemu soal graph dalam bentuk matriks, lebih baik pake djikstra y, dan permasalah repairing bridge itu sorting y?soalnya masih pemula dalam DP

  12. Pak, output untuk problem H yang bagian indeks itu maksudnya gimana y?apakah index untuk array yang belum disort?

  13. Pak, untuk yang repaired bridge, idenya pakai array 1 dimensi untuk merekam harga untuk indeks masing2? indeksnya berupa panjang ke berapa

    • maaf, ngga ngerti; ini pertanyaan atau apa ya?

      anw, untuk soal “repairing bridge”, state dp nya f(x,r) yang artinya berapa panjang jembatan erpanjang yang bisa diperbaiki jika posisi yang terakhir diperbaiki adalah x-1 dan masih ada tersisa budget sebesar r.

 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)