Dec 232010
 

Day 3: Kontes!

Contest day! Menu makan paginya mirip dengan kemarin, tapi lumayan enak, ya sudalah…

Selesai breakfast kita langsung melaju ke kampusnya dengan taksi. Registrasi ulang, dan dikasi light breakfast lagi, gw cuma sanggup minum (teh tarik lho…). Pas breakfast di kampusnya gw ketemu si Aji, akhirnya sampe juga dia ke sini 😀 Gw juga ketemu sama tim UNPAR (Coach Beatrix, Olivia, Jacobus, dan satu lagi yang ngobrol ama gw justru gw lupa namanya =.=, Edwin?). Di jadwal kontesnya mulai jam 9, jadi masih lama dan ada waktu nganggur.

Jam 9 lewat peserta diarahkan ke ruang lombanya, sedangkan gw diusir ke auditorium di lantai 3. Ternyata jam 9 itu bukan langsung kontes, tapi masih practice session. Panitianya memutuskan untuk mengulang practice session sekitar 30 menit karena kemarin practice sessionnya berantakan. Karena gw ga ada kerjaan ya wes gw ke auditorium aja. Di auditorium, Steven Halim dan Felix Halim ternyata disuruh sama panitianya presentasi bukunya ke coach-coach yang ada di situ. Jadi deh kita sekitar 10-15 menit dengerin mereka bercerita, ga cuma tentang buku, tapi juga pengalaman mereka solving, coaching, dll, seru :-D. Jam 10 tiba-tiba ada satu peserta yang masuk ke ruang auditorium coach, lho.. berarti kontesnya masih belum dimulai yah. Sampe jam 11 pun kontes masih belum dimulai, mulai bosen… Kontes dimulai jam 11:30, ngaretnya parah amat =.=.

Di auditorium gw dapat sinyal wifi, tapi anehnya ga bisa buka scoreboard kontes. Setelah gw tanya, ternyata emang account guest yang coach pake itu ga bisa buka scoreboard, uaneh… Jadinya gw cuma bisa ngeliatin scoreboard yang ada di layar depan. Setelah beberapa lama baru scoreboard bisa dibuka dari wifi, asik :-D. Tapi bosen juga ngeliatin scoreboard tanpa liat soalnya. Setelah kurang lebih 2 jam, gw mulai ngantuk dan tertidur. Pas gw tertidur gw sempat dibangunin karena dapat kopi soal, tapi karena masih ngantuk gw lanjut tidur lagi….

Satu jam sebelum kontes berakhir gw bangun dan baru liat soal…

A. Overalapping Scenes
Diberikan N (N ≤ 6) buah string yang masing-masing panjangnya tidak lebih dari 10 karakter, concate semua string tersebut hingga menjadi sebuah string dengan panjang paling pendek. Ketika dua buah string diconcate, jika suffix dari string A dan prefix dari string B sama, maka mereka bisa dibuat overlap sehingga panjang string gabungannya jadi lebih pendek. Karena N nya kecil dan panjang stringnya juga pendek, maka solusi bruteforce dengan next_permutation dan mengecek suffix-prefix setiap pasang string sudah cukup. Si Hutomo melakukan kesalahan bodoh di soal ini, cara ngecek suffix-prefixnya dia O(n), sakti 😐

B. Language Detection
Aish, ini soal bonus banget, cuma IF IF IF aja. If input apa, output apa. Yang gw heran adalah Love AC soal ini di menit 19???? Grrr x(

C. Scientific Experiment
John ingin mengetahui seberapa kuat telur dengan menjatuhkannya dari gedung yang memiliki N (N ≤ 1000) lantai. Semua telur memiliki kekuatan yang sama. Jika telur tersebut pecah ketika dijatuhkan dari lantai K, maka telur tersebut juga pasti pecah jika dijatuhkan dari lantai > K. Jika telur tersebut tidak pecah, maka telur tersebut juga tidak akan pecah jika dijatuhkan dari lantai < K. Kalau telurnya pecah, ia harus membeli telur baru di dalam gedung seharga X, jika tidak maka iya harus menggunakan telur yang sama untuk percobaan berikutnya. Jika ia memasuki gedung (setelah keluar untuk mengecek telur tersebut pecah/tidak) dengan membawa telur maka ia harus membayar Z, jika tidak membawa telur ia harus membayar Y. Minimize biaya terburuk John untuk mengetahui lantai tertinggi yang tidak menyebabkan telur tersebut pecah. Gw pernah liat soal yang mirip kayak gini di GCJ entah tahun berapa, bedanya di situ ga ada X, Y, Z dan yang ditanya apa gw ga ingat. Soal ini nggak bisa dibinary-search karena biaya kalau telur pecah dan tidak pecah itu berbeda. Dynamic Programming bisa digunakan. f(k) = min{ max{ f(i-1)+y+x, f(k-i)+z } for all 1 ≤ i ≤ k. } f(k): berapa biaya minimum untuk mengetahui lantai tertinggi dari 1..k di mana telur tersebut tidak akan pecah. DP yang gw gunakan adalah DP 1 dimensi. Kalau bingung, coba ikuti penjelasan berikut: misalkan g(a,b) adalah biaya minimum untuk mengetahui lantai tertinggi dari a..b di mana telur tersebut tidak akan pecah, maka g(a,b) bisa diselesaikan dengan cara g(a,b) = min{ max{ g(a,i-1)+y+x, f(i+i,b)+z } for all a ≤ i ≤ b. }. Kalau kita perhatikan g(5,9) itu nilainya akan sama dengan g(2,6) dan g(0,4), sehingga daripada menyimpan a,b lebih baik kita menyimpan selisih tingginya saja yaitu f(4). D. ABC Tiles
Soalnya ga susah, kita disuruh masang-masang tile dan ga boleh tile bersebelahan yang warnanya sama, yah… cuma bicoloring doank (tilenya cuma 2 warna).

E. Simple Encryption
Ok, soal tersusah yang sampe sekarang gw ga tau gimana caranya. Diberikan sebuah bilangan bulat K1 (1 ≤ K1 ≤ 50000), tentukan nilai K2 sedemikian sehingga K1K2 = K2 (mod 1012) dan K2 adalah bilangan 12 digit.

F. Electricity Connection
Diberikan sebuah grid 10 x 10 yang terdapat sejumlah rumah ( maks. 8 ) dan sebuah generator listrik. Cell lainnya adalah tanah kosong atau air. Tugas kita adalah menghubungkan semua rumah dengan generator listrik. Membangun jalur listrik di atas tanah costnya berbeda dengan melalui air. Cari cost minimumnya.

Felix Halim suggests soal ini diselesaikan dengan A* karena kayaknya statenya ga banyak. Entah sih, musti dicoba itu.

G. Underwater Snipers
Diberikan N (N ≤ 10000) koordinat musuh yang semuanya terletak di atas garis horizontal y = k (y > k). Kita harus meletakkan sejumlah S (S ≤ 10000) sniper untuk membunuh semua musuh tersebut. Sniper kita hanya bisa diletakkan di bawah garis horizontal y = k (y < k) dan memiliki jangkauan D, yang artinya kalau ada musuh dalam rentang euclidian distance D maka musuh tersebut akan mati. Tingkat keberbahayaan posisi seorang sniper adalah k - yi di mana yi adalah posisi y dari sniper tersebut. Tugas anda adalah meminimize tingkat keberbahayaan terburuk dari posisi semua sniper. Output IMPOSSIBLE jika tidak mungkin dilakukan.

Soal ini nggak susah juga, jawabannya bisa kita binary search. Untuk setiap jawaban p, kita letakkan semua sniper kita di posisi baris k – p. Trus untuk setiap musuh, kita cek dimana rentang kiri dan kanan posisi sniper harus ditempatkan di garis k-p tadi, gunakan persamaan pitagoras. Kalau sudah, tugas kita adalah mengcover semua rentang yang ada dengan jumlah sniper sesedikit mungkin, jika jumlah sniper lebih kecil S maka bisa (binary search perbesar), jika tidak maka gagal (binary search perkecil). Mengcover semua rentang ini sama dengan interval selection problem, bisa diselesaikan dengan greedy sederhana.

H. Making Quadrilaterals
Aih, soal gampang. Intinya fibonacci dengan tiga elemen terakhir (tribonacci).

I. The Queue
Soal yang ini mirip banget dengan soal B di ICPC Jakarta yang barusan. Jadi kalau soal B di Jakarta bisa, harusnya soal I bisa. Si Hutomo melakukan kesalahan BODOH di sini, cara modulonya salah =.=.

J. Air Pollution Problem
Soal yang J gw ga baca, udah mau kelar kontesnya. Sekilas lihat sih kayaknya soal geometri.

Overall gw lebih suka soal-soal Kuala Lumpur daripada soal Kaohsiung, ya iya problem setternya beda sih :p.

Huah! Love cuma solve 2! memalukan!! Katanya seharusnya bisa solve lima, dua soal ngebug bodoh, satu soal ga sempat coding, SWT. 20 besar saja bahkan ga masuk x( haish, ya sudalah, apa boleh buat…

Sehabis kontes kita dikasi free time buat makan-makan, dan habis itu ke gedung acara penutupan yang sama dengan gedung acara pembukaan. Wogh, rame, gw ngeliat Shariar Manzoor! Ada Derek Kisman (snapdragon)! Ada Jane Alam Jan! Wooooo, serasa World Final :p Om Hwang juga ada :-D. Setelah menunggu beberapa saat, penutupan pun dimulai. Dimulai dengan beberapa kata sambutan yang ga jelas dari siapa. Pas giliran om Hwang yang kasi kata sambutan, semua pada kaget, suaranya gede :), dan orangnya penuh semangat jadi rame deh :-D. Selesai awarding, kita dikasi makan-makan (enak). Di kesempatan ini gw ama Felix Halim minta foto-foto sama si Kisman dan Jane. Si Felix sempat foto sama si Manzoor, gw kagak :p. Gw jadi kasihan sama si Kisman, tiap kali mau makan selalu ada yang ngajak dia foto, kapan dia bisa makan dengan tenang :-D.

Kali ini gw pulang dari kampus ke hotel Citrus nebeng bus yang lain ke hotel De Palma dulu. Soalnya dari hotel De Palma lebih gampang cari taksi daripada di kampusnya. Baru dari De Palma lanjut ke hotel gw.

      

      

      

      

  3 Responses to “ACM-ICPC 2010 Kuala Lumpur”

  1. Dari tanggal 7-10 kita dibookingin sama BINUS tiga kamar (dua twin-bed, satu double), sedangkan untuk tanggal 11-12 nya kita dibookingin dua twin-bed, karena untuk 11-12 itu kita extend (dengan biaya sendiri tentunya).

    ini formasi tidurnya gimana nih ? 2 – 2 apa 3 – 1? hahahaha

  2. btw paspor malay itu ada chipnya, jadi tinggal lewat gate, autoscan =P
    paspor indo mulai 2011 ada tuh yang macam gitu, 600rb katanya

 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)