Final KP UnPar 2010

Update : Soal Final [RAR]

Practice Contest

2 soal :

  1. keluarin bilangan fibonacci di antara a dan b
  2. dikasi 2 sequence bilangan, temukan letak pertama sequence A ada dalam sequence B

pas lg ngerjain soal 2, bengong jg liat constraintnya. bisa ada sejuta testcase, tiap sequence bisa ada sejuta bilangan. lah, ini kan baca input doang ud ga muat time limitnya? yaud gw jd koding versi ngasal brute forcenya (total sejuta ^ 3 kalo ada sejuta testcase), ternyata AC (constraintnya ngaco berarti). sisa waktu pake buat iseng2 ngoding Knuth-Morris Pratt, pake array sejuta. eh, ga bisa :)) aneh, padahal itu kan masih jauh < 16 MB? setelah ditanya, kata panitianya, “memory limitnya 1 MB“. gw bengong =))

setelah practice contest selese, gw menyimpulkan ‘ga usa peduliin constraintnya, hajar aja, wong sejuta ^3 aja muat’ =))’

click more untuk write-up soal final…

*berdasarkan urutan pengerjaan*

Problem H

cukup straight forward aja – cari jarak yang bisa ditempuh mobil bila dipercepat maksimal (a) dan cari jarak yang bisa ditempuh mobil bila diperlambat maksimal (b). bila a melewati  (x+10), maka percepat. bila b tidak melanggar (x), maka perlambat. else, berdoa.

tricky : penggunaan > atau >=, < atau <=. agak rancu sih soalnya(buktinya ngga ada yg bener one-shot), jd gw jd agak coba2 kombinasinya aja.

Problem A

straight-forward aja sesuai yang diminta soal, bagian trickynya cuma: bila hasil modulo = 0, maka jadikan 78. untuk soal ini gw sampe WA 4 kali (pake recode pascal segala) – dgn bodohnya ga bs ngeliat bug yg cukup obvious 😦

Problem D

kalo sudah bisa parsing inputnya, sebenarnya cukup mudah. nggak perlu buat tree penuh, tapi cuma perlu simpan parent dari setiap orang. kalo ud simpan parent, jawab querynya obvious – yg agak tricky cuma nephew, karena kalo kakeknya sama belum tentu sepupu, tapi bisa sibling juga.

Problem F

problem pertama yg gw coba, juga adalah problem terakhir yg di-solve (beberapa menit sesudah freeze). karena filosofi penyisihan tadi, gw langsung hajar bikin DFS (yg emang ud pasti ga lewat kl testcasenya bener=D) … akhirnya gw baru implemen algoritma Tarjan untuk Strongly Connected Component, dan langsung accepted.

Problem yg dicoba tapi nggak accepted:

Problem C

problem ini, gw masih yakin solusi gw bener…. gw implementasi dynamic programming dengan state (posisi, alien terakhir), dengan fungsi:

1)kalau alien terakhir mengenali s[posisi], maka f(posisi,alien terakhir) = f(posisi+1,alien terakhir).

2) kalau tidak, f(posisi,alien terakhir) = min(f(posisi+1, alien terakhir),f(posisi+1, alien yg mengenali s[posisi]))+1.

*keterangan : f(posisi+1,alien terakhir) di kondisi 2 adalah bila berganti 1 huruf, f(posisi+1,alien yg mengenali s[posisi]) adalah bila berganti permanen.

Problem B

penerjemahan ke bahasa indonesia dan piglatin mudah, tapi untuk persyaratan awalnya ambigu sekali… badly written problem – ngga pernah liat problem ICPC / olimpiade yang nyampur aduk banyak hal gini, juga dgn problem description yg sangat open to reinterpretation.

nggak tersentuh:

problem E ttg matriks, problem G ttg geometri – dua2nya bidang yg plg gw benci dan tau bakal ga bisa solve =)) langsung disingkirin dari awal.

============================

overall, problem set yang persebaran kesulitannya sangat nggak rata. IMO, hanya problem A dan F yang solvable pra-OSN, problem D masih lumayan, walaupun perlu jam terbang ngoding (parsing, dkk) dan solusi problem F (kecuali ada solusi yang lebih sederhana), baru ada di Pelatnas 2. kontes ini jadi ajang cepet2an dan bersih2an koding (untuk soal A dan F), jam terbang (problem D), pengetahuan algo (problem E *kayaknya gauss-jordan?*, G dan F) dan tebak2an soal (problem B). ke-nggak rataan persebarannya bs diliat dari score akhir, selain gw maksimal cuma solve 2 soal, pdhl kalo persebarannya bagus kan harusnya nggak sesedikit itu.

gw pribadi lebih setuju kalo lomba nasional di luar olimpiade nggak banyak pake pengetahuan algo, tapi lebih ke logikanya – banyak2 greedy, DP sederhana, atau ad hoc, karena rasanya lebih ‘fair’ untuk semua peserta. kalaupun ada beberapa, juga ditakar kesulitannya supaya rada2 bertingkat. mungkin lain kali problemset perlu ditest dulu sama ICPCers dari uni lain untuk mengurangi ambiguitas soal?

anyw, props untuk panitia yang penyelenggaraannya kemarin cukup berhasil, terutama dari sisi teknis PC^2, komputer, dkk, dan panitia2 yang ramah2, bikin kita welcome banget 😀 (apalagi ngga ada panitia rese yg suka ganggu2in ga jelas kayak di binus) walau sayang ngga ada snack2 di luar ruangan lomba… jd ga ada bahan refreshing, ke toilet aja diikutin =)) pdhl biasanya gw ditotal2 mungkin bs ngabisin stenga jem di luar ruang kontes, jalan2 ato mondar mandir ga jelas =))

well, walopun menang, tp tetep aj gw unhappy bgt akan performance kemaren – bugs2nya bodoh2, dan konsentrasi gw spanjang contest ud melayang ke mana2. kelemotan di problem F bikin sedih banget. bad day 😦

random tidbits :

  • rank 1-4nya dari SMAK 1 semua (1 dan 3 dari jakarta, 2 dan 4 dari bandung), bangga ya jadi anak penabur 😀
  • ngabisin > 10 Frozz sepanjang contest
  • kompetisi pertama tanpa TOKI 2008-2009 di sebelah gw, rasanya aneh juga ya… biasanya ada foto pake jaket coklat muda buluk dari UGM :))
  • gw merasa tua banget euyyy… tnyata cuma 2 anak klas XII di lomba ini =)) gile, pdhl kynya baru kemaren gw slalu jd anak klas X sendiri di podium.
Advertisements

7 Responses to Final KP UnPar 2010

  1. Ven, gw baca sama sekali gak ngerti. hahaha

  2. Janson says:

    Soalnya gak bisa di-download, ven? haha

  3. suhendry says:

    “apalagi ngga ada panitia rese yg suka ganggu2in ga jelas kayak di binus”.

    Buat pembaca sekalian yang ingin mengetahui siapakah oknum panitia di binus yang suka ganggu2in peserta: Eko “buluk” Wibowo O:-)

  4. Felix J says:

    Woghhh.. :-O Jangan2 itu Mr. Yang-Kasi-Tau-Oknum ya 😛

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

%d bloggers like this: