Jun 092015
 

A. A Simple Query Problem (link soal)

Dberikan sebuah array yang terdiri dari N integer (N ≤ 100,000) dan Q (Q ≤ 1,000,000) buah query dalam bentuk (i, j); untuk setiap query, output elemen terbesar yang berada pada index [i, j] (i hingga j) beserta dengan indexnya.

Batasan N dan Q yang cukup besar tidak memungkinkan kita menyelesaikan soal ini secara naif dengan kompleksitas O(N * Q) – looping dari i ke j untuk setiap query.

Soal ini bisa diselesaikan secara langsung dengan struktur data Segment Tree atau RMQ (Range Minimum/Maximum Query). Dengan Segment Tree, kita hanya memerlukan memory sebesar O(N) dan setiap query bisa dijawab dalam O(log N); sedangkan, dengan RMQ, kita memerlukan memory sebesar O(N lg N), namun kita bisa menjawab setiap query dalam O(1).

Saya tidak akan membahas kedua struktur data tersebut di sini; sebaiknya pelajari struktur data ini jika kalian belum menguasainya. TopCoder memiliki satu tutorial mengenai kedua struktur data ini.

B. ACM Race (link soal)

Diberikan sebuah directed acyclic graph (DAG) dengan N nodes (N ≤ 1,000), tentukan banyaknya kemungkinan perjalanan dari S menuju T yang melewati K buah intermediate nodes (diberikan).

Kunci dari penyelesaiain soal ini adalah bahwa graph yang diberikan adalah DAG. Jika graph ini bisa memiliki cycle, maka soal ini menjadi #P-Complete (counterpart decision problemnya adalah Traveling Salesman Problem), yang belum diketahui solusi polinomialnya; dengan N ≤ 1,000 tentunya solusi exponensial seperti O(2log N) atau O(N!) tidak dapat menyelesaikan soal ini.

Karena graph yang diberikan adalah DAG, maka hal yang pertama yang perlu kita lakukan adalah mengurutkan node-node yang diberikan secara topologi (topological sort). Setelah node-node tersebut diurutkan, kita tinggal mengevaluasi setiap node sesuai urutan yang diberikan.

C. Credit Card Number (link soal)

Diberikan sebuah nomor kartu kredit dengan tepat satu digit yang hilang. Tentukan digit yang hilang tersebut apabila nomor kartu kredit yang diberikan mengikuti aturan Luhn formula (diberikan di soal).

Di soal dijelaskan jika tidak ada digit yang memenuhi maka output -1, dan jika ada lebih dari satu digit yang memenuhi maka output -2. Kedua poin tersebut hanyalah tambahan yang tidak penting; tidak akan ada output yang demikian.

Soal ini bisa diselesaikan baik dengan cara langsung (membalik algoritma Luhn) atau dengan mencoba-coba nilai yang mungkin.

D. Days After Wedding (link soal)

Diberikan sebuah tanggal (DD MM YYYY), tentukan jumlah hari yang telah berlalu dari tanggal 19 DEC 2009.

Tidak ada trik dalam soal ini, kita hanya harus mengimplementasikannya dengan hati-hati.

E. Distributing Gift (link soal)

Diberikan N (N ≤ 1,000) buah suvenir yang masing-masing berjenis Ai (Ai ≤ 1,000,000,000), tentukan jumlah suvenir maksimum yang bisa diberikan kepada setiap anak apabila semua anak harus mendapatkan set suvenir yang sama.

Kita perlu menghitung jumlah masing-masing suvenir yang diberikan. Untuk melakukan hal ini, kita bisa mengurutkan datanya terlebih dahulu (agar nilai yang sama bersebelahan), atau melihat nilai N yang cukup kecil, kita bisa menghitungnya secara langsung (dalam O(N2)).

Saya memperhatikan ada beberapa tim ketika kontes yang terus-terusan mendapatkan RTE di soal ini. Mereka menghitung banyaknya suvenir untuk setiap jenis dengan menggunakan array counter (jumlah[data[i]]++). Meskipun N hanya 1,000 namun jenis suvenirnya bisa mencapai 1,000,000,000. Tentunya kita tidak bisa menggunakan array of integer dengan ukuran 1 milyar (> 4GB memory) mengingat compiler yang kita gunakan adalah 32-bit (ukuran program maksimum adalah 4GB); meskipun kita bisa melakukan hal ini, kemungkinan besar solusi ini tetap akan mendapatkan TLE karena alokasi memory-nya cukup lama.

Solusi alternatif yang bisa digunakan adalah dengan menggunakan struktur data map (STL di C++, atau HashMap pada Java).

F. Lora Jones the Adventurer (link soal)

Diberikan sebuah peta grid berukuran N kolom x M baris, Tentukan jumlah langkah minimum yang diperlukan untuk mencapai sel tujuan dari sel mula-mula dan mengunjungi minimal satu sel yang berisi artifact.

Ini adalah tipikal soal yang bisa diselesaikan dengan BFS (Breadth-First Search): mencari shortest path pada uniform cost graph. Yang dimaksud uniform cost graph adalah graph dengan cost yang uniform/seragam untuk setiap edge-nya; pada soal ini, cost untuk bergerak dari satu sel ke sel yang bersebelahan adalah 1.

Untuk menangani syarat pengambilan artifact, kita bisa menambahkan satu state TRUE/FALSE pada proses pencariannya yang menandakan apakah sudah ada artifact yang diambil. Dengan demikian, state yang bisa digunakan dalam pencarian secara BFS adalah: <baris, kolom, artifact>, di mana baris dan kolom menandakan posisi Lora saat ini pada peta, dan artifact adalah boolean value yang menandakan apakah Lora sudah mengambil artifact. Goal statenya tentu saja <baris_goal, kolom_goal, TRUE>.

Solusi alternatifnya adalah dengan melakukan BFS dua kali (tanpa state artifact), sekali dari posisi awal Lora (BFS1), dan sekali lagi dari posisi akhir (BFS2); untuk setiap BFS, catat jarak yang diperlukan untuk mencapai setiap sel. Jawaban untuk soal ini bisa ditemukan dengan menjumlahkan jarak dari BFS1 dan BFS2 pada setiap sel yang berisi artifact (di soal ini, jarak dari A ke B adalah sama dengan jarak dari B ke A, sehingga jarak dari artifactk ke goal == jarak dari goal ke artifactk); tentunya yang kita output adalah yang paling minimum.

G. Monster Hunting (link soal)

Diberikan S kekuatan player mula-mula, dan N monster yang masing-masing memiliki kekuatan Mi dan bonus Bi kekuatan jika kita berhasil mengalahkan monster tersebut; tentukan kekuatan akhir maksimal yang bisa diperoleh oleh player tersebut.

Di soal ini mengalahkan seekor monster (jika kita bisa mengalahkannya) tidak ada kerugiannya sama sekali. Dengan demikian, kita bisa menggunakan pendekatan greedy yang sederhana di soal ini: bantai monsternya satu per satu mulai dari yang paling lemah (hingga kita tidak bisa mengalahkan monster yang ada).

H. Paint (link soal)

Diberikan N (N ≤ 30) buah lingkaran pada bidang 100 x 100, tentukan luas gabungan seluruh lingkaran tersebut.

Ada beberapa solusi yang bisa digunakan untuk menyelesaikan soal ini, yang paling populer di antara para juri dan pembuat soal adalah dengan metode line sweep. Namun pembuat soal (dan yang mempersiapkan data uji) mengizinkan solusi yang kurang akurat untuk dapat accepted di soal ini. Salah satunya adalah dengan recursive subdivision:

  • Bagi bidang A (awalnya 100 x 100) tersebut menjadi 4 bidang bujur sangkar yang sama besar: A’1, …, A’4.
  • Evaluasi setiap bidang A’: apakah bidang tersebut penuh (ada lingkaran yang memenuhi bidang tersebut); apakah kosong; atau tidak tahu.
  • Jika evaluasi di atas adalah “tidak tahu”, maka lakukan rekursif pada bidang tersebut (bagi 4 lagi, dan seterusnya).
  • Lakukan rekursif hingga tingkat akurasi tertentu (solusi dari juri menggunakan threshold luas bujur sangkar = 0.001).

Solusi ini tentunya tidak akurat, namun data uji yang disiapkan mengizinkan solusi yang demikian untuk accepted.

Beberapa tim di kontes ini “salah” mengartikan soalnya, mereka berasumsi lingkaran-lingkaran yang diberikan sama sekali tidak overlap. Selain itu, saya juga menemukan bahwa sebagian kontestan menggunakan 3.14 atau 22/7 sebagai konstanta nilai pi, yang tentunya tidak cukup akurat. Pi adalah bilangan irasional, yang artinya tidak dapat dinyatakan dalam bentuk pecahan, jadi 22/7 bukanlah nilai exact dari pi, namun hanya pendekatannya saja (yang biasa digunakan ketika kita di bangku sekolah). Untuk nilai pi yang lebih akurat, kita bisa menggunakan beberapa opsi:

  • const double PI = 2 * acos(0);
  • const double PI = 4 * atan(1);
  • const double PI = 3.141592653589793238463;
  • M_PI

I. Palindrome Emornilap (link soal)

Diberikan sebuah string S (|S| ≤ 100), cari string S’ yang palindrome dengan menambahkan maksimal (at most) satu karakter di posisi manapun pada string S. Jika ada lebih dari satu solusi, output yang paling kecil secara leksikografis.

Kita tentunya diizinkan untuk tidak menambahkan karakter apapun pada string S, tapi perlu diingat, yang diinginkan soal adalah string S’ yang paling kecil secara leksikografis. Contoh: S = “MM“, tentunya kita tidak perlu menambahkan karakter apapun untuk membuat S menjadi palindrome (S sudah palindrome), namun kita bisa membuat S menjadi “MAM” yang juga palindrome, tapi lebih kecil secara leksikografis.

Contoh lain:

  • PAP → PAAP
  • AAA → AAA
  • RTR → RTR
  • TRT → TRRT

Untuk menyelesaikan soal ini, kita cukup melakukan pencarian secara exhaustive (brute force). Sisipkan setiap kemungkinan karakter (A-Z) pada setiap posisi, dan cek apakah string yang dihasilkan adalah palindrome. Cari palindrome terkecil yang dihasilkan.

J. Yule Ball (link soal)

Diberikan sebuah integer N (N ≤ 100,000) yang menyatakan jumlah orang, tentukan berapa banyak kombinasi pasangan 2-orang yang berbeda yang bisa dihasilkan.

Soal ini bisa diselesaikan dengan pendekatan dynamic programming. Mari kita definisikan F(N) sebagai banyaknya kombinasi yang demikian dengan N orang, maka:

  • F(2) = 1
    jika hanya ada 2 orang, tentunya hanya ada 1 pasangan yang bisa dihasilkan.
  • F(4) = 3 * F(2)
    jika ada 4 orang, orang pertama bisa berpasangan dengan 3 orang lainnya, dan sisanya sama dengan kasus pada F(2).
  • F(6) = 5 * F(4)
    jika ada 6 orang, orang pertama bisa berpasangan dengan 5 orang lainnya, dan sisanya sama dengan kasus pada F(4).
  • F(N) = (N – 1) * F(N-2)

Untuk kasus di mana N adalah ganjil, kita hanya perlu “membulatkannya” ke atas (McGonagall ikut berdansa).


  24 Responses to “ACM-ICPC 2015 Provincial Sumatra”

  1. Permisi pak, bagi yg sdh mendapat tiket Asia Jakarta melalui ideafuse tapi mau ikut INC, kira” tiket ideafusenya akan gugur tidak pak. terimakasih

  2. Selamat pagi pak, saya ingin menanyakan. Kebetulan tim saya lolos ICPC Asia Jakarta lewat Ideafuse. Dan juga tim saya tahun ini akan mengikuti ICPC Asia – Singapore. Namun ketika saya ingin mendaftar INC mengapa saya tidak bisa mendaftar dikarenakan saya sudah mendaftar 2 regional yang merupakan batasan maksimal regional untuk tahun ini? Padahal INC dan Ideafuse sama saja yaitu Regional Asia Jakarta. Terima kasih pak

    • (a) ikut IdeaFuse
      (b) lolos ke ICPC Jakarta
      (c) daftar di ICPC Singapore
      (d) mencoba daftar di INC

      Apa ada tim lain -dari universitas kamu, atau yang kamu tahu- yang juga (a), (c), (d), dan berhasil mendaftar? Kalau iya, apa tim itu juga (b)?

      • Sejauh ini belum sih pak. Teman saya ada yang kasusnya sama seperti saya dan tidak bisa mendaftar INC. Apakah memang peraturan seperti ini ya? Soalnya saya rasa tujuan INC dan Ideafuse sama sama ICPC Jakarta harusnya sih bisa dianggep 1 regional. Terima kasih

      • “Sejauh ini belum sih pak. Teman saya ada yang kasusnya sama seperti saya dan tidak bisa mendaftar INC.” — ini tim yang beda dari kamu kan? apa tim ini juga (b)?

        Kalau aturan dari ICPC Asia, memang partisipasi hanya dibatasi di level regional. Tapi nggak tau gimana cara kerja sistem di icpc.baylor nya.

        Kemungkinan besar, tim kamu sudah di-“lock” oleh sistemnya karena sudah terdaftar di dua regional (coba cek apakah tim kamu ada di daftar ICPC Jakarta dan ICPC Singapore), dan sistemnya ngga liat lagi registrasi berikutnya itu u/ provincial atau regional mana. — tapi ini baru hipotesa awal, diperkuat kalau teman kamu juga (b).

      • OK, informasinya jadi simpang siur. Saya barusan cek di daftar tim ICPC Jakarta, ternyata tim pemenang IdeaFuse kemarin belum dipromote ke ICPC Jakarta (akan dilakukan menjelang ICPC). Jadi dugaan yang di atas sepertinya salah.

        Keliatannya sudah direport ke committee INC ya, katanya sedang ditelusuri penyebabnya. Kita liat deh kelanjutannya gimana.

      • UPDATE. Barusan dapat tanggapan langsung dari direktur ICPC Asia. Ternyata memang ada kesalahan teknis di setting pedaftaran IdeaFuse dan langsung diperbaiki. Harusnya sekarang udah OK.

        Silakan dicoba kembali pendaftarannya.

        • Oke bapak akan saya coba lagi. Terima kasih banyak pak. Saya sangat mengapresiasi itu. Untuk selanjutnya akan saya tanyakan lagi ke Bapak. Selamat malam πŸ™‚

  3. Permisi pak, saya ingin mengklarifikasi mengenai submission saya pada soal D INC 2015, saya sdh mencoba dicompile melalui DevC++ dan ideone, hasilnya success, tapi stelah saya submit ke grader kontes INC, hasilnya malah Compile Error, pdahal sgala isinya sdh memenuhi, mulai dri nama filenya “D” sama jga mnggunakan int main(), terima kasih pak
    kode : http://ideone.com/mksXts

  4. mohon maaf pak, ternyata sudah direvisi oleh pihak INC menjadi Accepted, terima kasih πŸ˜€

    • Hi Sidiq, saya baru baca pertanyaan kamu di sini (dan juga email notificationnya). Saya baru saja pulang dari liburan (tidak membawa laptop atau memeriksa email sama sekali) selama seminggu lebih dari sehari sebelum INC.

      Untuk urusan INC atau ICPC yang sifatnya urgent, sebaiknya langsung ditanyakan ke panitianya saja πŸ™‚

      Untuk pertanyaan mengenai inti lombanya (soal, submission, dll), bisa ditanyakan melalui sistem klarifikasi di sistem lombanya. Untuk pertanyaan lain (login, pendaftaran, dll), bisa ditanyakan melalui contact person yang tertera di websitenya.

  5. untuk ikut event ini harus dibawah nama universitas?

    • ICPC, singkatan dari International Collegiate Programming Contest yang diselenggarakan oleh ACM (Association for Computing Machinery), adalah lomba pemrograman dan problem solving antar universitas. Satu tim terdiri dari 3 mahasiswa dari universitas yang sama yang disertai oleh 1 coach (dosen, pembimbing, atau pendamping yang juga dari univ. yang sama).

      Jadi jawaban u/ pertanyaan kamu: YA.

      ICPC itu multi-tier contest, dan ICPC Provincial Sumatra adalah salah satu provincial contest u/ ICPC Regional Jakarta (hanya yang lolos dari provincial contest bisa mengikuti regional level), yang akan berlangsung sekitar 2-3 minggu lagi. dan hanya yang berhasil lolos (juara) dari regional level yang akan diundang u/ tingkat world final.

  6. Selamat siang bapak suhendry saya sudah menghubungi sebagai panitia utama ICPC Asia jakarta. Saya dari Universitas Gadjah Mada ingin mengajukan dana ke fakultas kami untuk keberangkatan menuju Binus. Namun sesuai peraturan, proposal harus menyertakan surat bukti kelolosan 5 tim kami di ICPC Asia Jakarta (yang mana 2 dari 5 berasal dari Ideafuse 2015). Saya sudah menghubungi Ibu Alvina selaku koordinator namun belum mendapat jawaban. Dapatkan saya mendapat surat pernyataan kelolosan tim kami ke ICPC Jakarta?
    Berikut nama tim kami :
    1. Afatu Al Ilmi An Nisyan (Ideafuse 2015 juara 1)
    2. Panitia (Ideafuse 2015 juara 3)
    3. WedhusQwonyol Reunian
    4. Wamallazatu illa ba’da ta’abi
    5. Tim Bebas
    Terima kasih atas perhatian Bapak

  7. Halo Pak Suhendry, soal-soal Ideafuse ini bagus-bagus dan menarik.

    Apakah ada online judge yang menerima soal Ideafuse ini?

    • Hmm, nggak yakin. IdeaFuse (tepatnya ICPC Provincial Sumatera), soal-soalnya nggak diarsipkan di ICPC LiveArchieve. Jadi mungkin harus cek di online judge local (tokilearning, jollybeeoj, dll). Setahu saya sih belum ada :p

  8. Selamat pagi Pak Suhendry, untuk ACM ICPC Regional 2015 belum ada pembahasannya pak? Apakah ada rencana untuk mempost pembahasannya dan bila ada, dapatkan bapak berkenan memberikan ETA nya?

    Terima kasih

    D.

  9. untuk kompetisi ini harus bayar ya?

 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)