Mengingat week 1 yang nilainya beda-beda tipis, saya rasa semua masih punya kesempatan masuk IOI. Karena belum ada perbedaan yang terlalu signifikan, saya masih santai-santai saja (ke depannya juga santai terus tapi).Minggu ini, kami diajari teknik-teknik yang udah cukup well-known sebenarnya, cuma tingkatannya emang agak tinggi. Materinya adalah:
- Convex Hull Tricks a.k.a. DP Convex Hull
- Self-Balancing Binary Search Tree a.k.a. BBST
- Randomized Algorithm
Untuk latihan minggu ini, ada yang rada berbeda.Kalau biasanya tiap hari soal latihannya sesuai dengan materi yang diajarkan, beberapa hari ini ada soal latihan yang bener-bener off-topic sama materinya, tapi gak papa lah daripada sense ngerecognize soal jadi tumpul :v
DP Convex Hull ini menggabungkan nama 2 hal yang menurut saya killer, yakni DP sama Convex Hull.Dan bener aja, karena asumsi saya itu saya juga dibantai soalnya.Untuk latihannya, kami ngerjain soal Commando (APIO 2010) sama suatu soal lainnya yang ajigile susah banget :'(
Untuk soal BBSTnya, paling cuma bermasalah sama ngodingnya yang rawan ngebug :v Ada satu soal yang menurut saya menarik dan sebenernya cuma perlu common sense biar AC :)
Utnuk soal-soal Randomized Algorithm, pengerjaannya juga penuh dengan rand(), mungkin scoringnya juga pake rand(). Ada satu soal yang sebenernya bisa pake greedy, tapi karena topiknya random jadinya ngerjainnya pake random :v Ada juga kejadian kocak, jadi ada satu soal yang minta pake monte-carlo atau apa lupa deh, intinya suatu solusi dianggap benar kalo nilainya paling parah beda 30% sama solusi sebenarnya.Di soal itu udah ada warning begini :
"Dilarang mencari solusi di internet mataupun menggunakan OEIS/website semacamnya untuk mengerjakan soal ini! Selain itu, program yang hanya mengeluarkan suatu nilai tanpa melakukan komputasi (ataupun suatu nilai yang benar-benar acak juga tidak diperkenankan, meskipun programnya diperpanjang dengan menambahkan kode-kode redundan (misal MST, MaxFlow, dkk., yang hanya diletakkan di dalam kode dengan tujuan mengecoh). Peserta yang melanggar diberikan nilai -100 secara manual."
Karena iseng, dari BF saya sama MW nemu rasi gaje.Kami pake, dapet 100, tapi kena warning dari kak Ashar, jadinya reset ke BF deh :p Habis itu dikasih tau kalo solusinya pake random walk, yang jadinya kayak sampling gitu intinya.
Hari Rabu, tau-tau Kuda a.k.a. Sal hubungin Agus, katanya dia lagi di Depok, tapi gak tau kenapa nyuruh Agus nyetel TVRI, katanya dia bakal muncul di situ.Ya kalik Sal masuk TV ~_~ Terus Sal mampir ke kamar saya, katanya besoknya dia mau ke Jakarta nyari kosan buat magang di traveloka.Terus saya lupa kek gimana caranya, malam itu (dan juga besoknya) Sal sukses menggusur Agus dan menguasai kasurnya.Mending kamu tidur di sofa aja terus Gus, haha.
Karena Sabtu APIO, kuis yang waktu sakralnya harusnya sabtu digeser ke hari Kamis.
Untuk Kuis 2 ini, bisa saya bilang bahwa : ini merupakan titik terbawah saya selama Pelatnas 3.
Total skor saya 100-0-25, saya terlalu terfokus di P3 sampai lupa nyampah P2.Berujung di rank 8.Bahkan, 3 jam pertama kontes nilai saya masih 0.Saya masih ingat betapa downnya saya di tengah kontes karena benar-benar buntu, sampai rasanya di pikiran saya ada tangan yang mengangkat saya, lalu ada suara "Kamu itu gak pantes masuk IOI!" dan tangan itu membanting saya sekuat-kuatnya ke tanah.After-contest, saya masih cukup merasa down tapi karena saya gak suka bicarain masalah saya, masalah down ini saya diamkan saja (saya cuma cerita ke cewek saya).
Jum'atnya, kayak biasa repeating sama speed practice.Untuk Repeating,saya bisa mengAC-kan soal Rekonstruksi Heap (thanks Agus) dan Rangkaian Kelereng Bebek (thanks MW).Speed practicenya.. gak bisa dibilang speed practice juga deh rasanya, lebih kayak training menjelang ACM-ICPC, soalnya durasinya 5 jam dan dikasih 8 soal kalo gak salah :v tapi juga cuma AC 2 sih :/
Sabtunya, APIO.Sebelum APIO ini saya udah mikir "Ini juga bawa nama Indonesia, seenggaknya jangan sampai se-fail kuis 2 lah" Oiya, saya udah gak terlalu mikir masuk 4 besar Pelatnas 3 atau nggak, sudah cukup trauma gara-gara kuis 2 :'( soal-soal APIOnya :
- Palindromes (Suffix Array)
- Split The Sequence (DP Convex Hull)
- Beads and Wires (DP on Tree)
*Update : sudah ada problem set + test data
Untuk APIO ini, saya ngelakuin blunder bego lagi : P2 saya coba solve dengan greedy yang gak ada proofnya sama sekali.Ya jelas WA lah, masalahnya sampe 2 jam nyoba ngeproof ujung-ujungnya gagal D: Saya juga sering submit dengan lupa meng-uncomment freopen, jadinya banyak yang otomatis WA dan mengurangi submission yang bisa saya pakai D: ujung-ujungnya, dari DP O(N^3*K^2) nemu pattern kalo bisa O(N^2*K), dan sadar kalo bisa DP Convex Hull jadi O(N*K).Karena lupa gimana, jadinya cuma bisa bikin pseudonya, yang gak tembus subtask terakhir :/ P1 cuma nyampah, dan P3 keliatan kalo ribet, jadi gak dikerjain.Skor akhir jadinya 23-71-0, gak tau bisa dapet medal apa nggak pas itu :/
Minggunya, aslinya mau paintball, karena bingung tempatnya di mana (nanya pun gak membantu) ujung-ujungnya ke Margo City, makan-makan sama aslinya mau nonton, tapi karena penuh gak jadi nonton.Kami makan di Hanamasa, tempat yang menurut saya enak tapi aneh, karena bisa makan sepuasnya tapi masak-masak sendiri :/ dan masalah buat saya adalah : harus pake sumpit! Mana saya gak bisa pake sumpit lagi D: Untung MW baik, dia masak banyak-banyak terus mempersilahkan kami ngambil yang udah dia masak, jadinya saya gak usah terlalu repot repot make sumpit untuk masak dan makan :') Oiya, seinget saya Radit juga eksperimen aneh, manggang jagung rebus, gak ngerti maksudnya apa :/
Sekian dulu postnya, ngeblognya nanti lagi ya
0 komentar:
Posting Komentar