May 122014
 

Lain-lain

Pemenang

  • Peringkat 1: 7NoTrump dari Universitas Kristen Maranatha.
  • Peringkat 2: surya01 dari Surya University.
  • Peringkat 3: MikroHolic dari STMIK-STIE Mikroskil.

Advancers ACM-ICPC Regional
5 besar dari kompetisi ini diberikan hak khusus untuk melaju ke ACM-ICPC 2014 Regional Jakarta (bulan Desember) tanpa melalui babak penyisihan di ACM-ICPC Indonesia National Contest (INC). Selain 5 besar, tim dari USU dan IT Del juga diberikan hak khusus untuk melaju ke ACM-ICPC Regional sebagai tiga perguruan tinggi (termasuk Mikroskil) dengan peringkat terbaik dari Sumatera di kompetisi ini.

  • 7NoTrump dari Universitas Kristen Maranatha.
  • surya01 dari Surya University.
  • MikroHolic dari STMIK-STIE Mikroskil.
  • ZeroHero dari Universitas Kristen Duta Wacana Yogyakarta.
  • WaterproofWombatWarrior dari Universitas Katolik Parahyangan.
  • GLHF dari Universitas Sumatera Utara.
  • DelBoys dari Institut Teknologi Del.

  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)