Pembahasan Beberapa Soal Penyisihan Arkavidia

Pada event Arkavidia yang diadakan HMIF ITB saya menjadi salah satu panitia lomba programming. Pada babak penyisihan kemarin ini saya kebetulan diminta membuat beberapa buah soal. Berikut adalah sedikit pembahasan dari 5 soal yang saya buat. Saya yakin banyak peserta yang solusinya lebih baik dari saya. Maklum saya masih cupu 😦

Anti Kasiski

Ini soal orisinal yang kepikiran waktu mendengarkan kuliah kriptografi. Awalnya saya tidak berniat mensubmit soal ini karena belum ketemu solusinya -_-; tapi beberapa hari (atau minggu..) kemudian akhirnya solusinya ketemu juga dan kebetulan solusi yang saya buat bisa kuat untuk string sepanjang 30.000 🙂 Pada soal tersebut dikatakan “jarak antar substring yang panjangnya minimal 2 huruf”, tapi sebenarnya substring yang panjangnya lebih dari 2 huruf tidak perlu dihitung karena substring tersebut pasti mengandung substring 2 huruf juga kan. Jadi yang perlu dihitung hanyalah substring2 yang panjangnya 2 huruf saja. Jadi pertama hitung semua jarak yang ada pengulangannya, dengan cara meloop berdasarkan pengulangan seperti pseudocode di bawah:

set all flags to false
for i <- 1 to panjang_string - 1
  for j <- 0 to panjang_string - i - 1
    if string[j] = string[j+i] then
      if ketemu_satu then
        flag[i]<- true
        max <- i
        break
      else
        ketemu_satu <- true
    else
      ketemu_satu <- false

Saat ini variable max menyimpan jarak terbesar yang terulang. Artinya bilangan (max+1) tidak akan menjadi faktor dari kumpulan bilangan yang telah diberi flag. Selanjutnya mulai dari max kita bergerak ke bawah sampai bilangan 1, sambil memberi flag semua faktor dari bilangan-bilangan yang telah diberi flag. Bilangan tanpa flag terkecil merupakan jawabannya. Kompleksitas algoritma tersebut sepertinya sekitar O(N3/2) jika menggunakan algoritma pencarian faktor yang kompleksitasnya O(N1/2). Source code lengkapnya dapat diunduh di sini.

Dansa Yo Dansa

Soal ini terinspirasi dari soal matematika yang memanfaatkan Catalan Number. Solusinya menggunakan definisi rekursif dari Catalan Number tersebut (bisa dilihat sendiri di Wikipedia). Ternyata soal ini berhasil dikerjakan dengan sempurna oleh sangat banyak peserta, berarti peserta Arkavidia ini memang hebat-hebat (atau soalnya yang kegampangan?).

Hiking

Soal hiking dapat dikerjakan menggunakan DFS dengan menghitung jalur terpanjang yang dapat dimulai dari sebuah titik. Fungsi DFS-nya sebagai berikut

function dfs(p)
  if (p.panjangmax = 0)
    p.panjangmax <- 1
    p.tinggimax <- p.tinggi
    foreach k in keempat_titik_yang_mengelilingi p
      if k.tinggi > p.tinggi and k.tinggi + p.tinggi < batascuram then
        dfs(k)
        if k.panjangmax + 1 > p.panjangmax then
          p.panjangmax <- k.panjangmax + 1
          p.tinggimax <- k.tinggimax
        else if k.panjangmax + 1 = p.panjangmax
          p.tinggimax = max(p.tinggimax, k.tinggimax)

Sebelumnya panjangmax dan tinggimax semua titik diassign dengan nilai 0. Setelah selesai, tinggal mencari titik dengan panjang dan ketinggian maksimum. Source code lengkapnya di sini.

Lebar Jaringan

Soal lebar jaringan bisa dikerjakan dengan algoritma Floyd-Warshall yang mencari jarak terpendek dari semua titik ke semua titik, kemudian tinggal cari jarak terpendek yang paling jauh.

Out Of Fuel

Soal ini kelihatannya agak menimbulkan kerancuan yang ingin saya pertegas di sini. Pada format masukan dituliskan “diikuti oleh M baris masing-masing berisi 3 angka P1, P2, S (0 ≤ P1, P2 ≤ N + 1, 1 ≤ S ≤ 10000) menandakan jarak jalan S dari SPBU P1 ke P2, tapi tidak sebaliknya”. Yang saya maksud di sini adalah jarak pada masukan tersebut berlaku seperti directed graph, yaitu hanya satu arah. Kata-kata tersebut sama sekali tidak menyiratkan bahwa graph yang dibentuk pasti asiklik. Cycle masih bisa terjadi jika pada masukan terdapat jarak dari A ke B dan juga B ke A misalnya. Pertama-tama kita perlu melakukan perhitungan cost antara 2 SPBU. Cost perjalanan dari SPBU A ke B adalah bensin yang diisikan di SPBU A dikurangi bensin yang terpakai pada perjalanan dari A ke B. Setelah itu kita melakukan pengecekan berulang. Pertama node finish diberi nilai 0, sedangkan node yang lain diberi nilai INFINITY. Nilai di sini menunjukkan jumlah bensin minimal yang harus tersedia untuk menempuh perjalanan dari node tersebut ke titik finish. Kita juga menggunakan sebuah array flag yang menandakan apakah sebuah node perlu dicek lagi atau tidak. Awalnya semua flag diberi nilai true. Lalu lakukan algoritma berikut, dimulai dari node finish.

while masih_ada_flag_bernilai_true
  p <- next_node_yang_berflag
  foreach v in nodes_yang_tujuannya_ke_p
    if value(p) > 0 and value(p) - cost(v,p) < value(v) then
      value(v) <- max(0, value(p) - cost(v,p))
      flag(v) <- true
  flag(p) <- false

Algoritma di atas berjalan sebagai berikut: jika node p bernilai X, maka node v yang menuju node tersebut dapat memiliki nilai X – cost(v,p) (dengan batasan nilai sebuah node tidak pernah lebih kecil dari 0). Jika nilai sebuah node berubah, maka node-node yang menuju node tersebut perlu diperiksa kembali. Algoritma ini dijamin berhenti karena pada setiap pengecekan terjadi pengurangan nilai sebuah node yang dengan batas bawah 0. Source codenya dapat diunduh di sini.

Pembahasannya mungkin cukup sekian. Soal-soal yang lain tidak saya bahas karena bukan saya yang buat, atau lebih tepatnya karena saya sendiri tidak bisa mengerjakan @^@. Kalau kurang jelas harap dimaklumi dan dipikirkan sendiri karena agak sulit menyampaikannya dengan kata-kata 😀 Untuk babak final semoga saja pembuat soalnya lebih berkompeten dari saya (kalau ada alumni TOKI atau siapapun yang mau menyumbang soal akan diterima dengan senang hati, asal bukan peserta dan tidak membocorkan ke peserta tentunya).

Advertisements
This entry was posted in Programming and tagged , , , . Bookmark the permalink.

6 Responses to Pembahasan Beberapa Soal Penyisihan Arkavidia

  1. marcadian says:

    @evan :yang anti kasiski kok bisa N^3/2 ??

    for i <- 1 to panjang_string – 1
    for j <- 0 to panjang_string – i – 1
    if string[j] = string[j+i] then

    untuk bagian ini kan jumlah loopnya
    len – 1 + len-2 + len – 3 + len – 3 + … + 1 = (1 + len – 1) * (len-1 ) / 2
    = len * (len – 1) / 2 = N^2

    O(N^3/2) +O( N^2) = O(N^2)

  2. evangozali says:

    hmm… iya juga ya. Saya juga tidak begitu yakin dengan kompleksitasnya. Kalau begitu diralat aja ya

  3. mail says:

    bisa minta testcase-nya mas??

  4. evangozali says:

    testcasenya tidak diberikan, sesuai peraturan 🙂

  5. meliza766hi says:

    dewa evaaann 😉

  6. evangozali says:

    biasa aja mel.. pesertanya yg dewa2, soal yg kubikin berhari2 dikerjain dlm beberapa menit -_-

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s