Hmm… Liat-liat blog di Indo-algo jadi pengen ngepost sesuatu 😀

Note: waktu di sini dalam WIB

Tanggal 7 November 2010 kira-kira jam 10:15 an gw bangun dan menyadari bahwa gw udah telat 15 menitan buat ikut INC. Tapi berhubung masih ngantuk, gw ketiduran lagi. Kira-kira jam 11, gw bangun dan baru betul-betul “sadar”. Lari deh ke North Spine bawa laptop, mouse, dll… Well, tadinya mau kerjain bareng setim tapi ternyata Trung ada tugas yang perlu dikerjain. Akhirnya mesti kerjain sendiri 😦

Sekitar jam 11:15-an gw berhasil dapat tempat di salah satu bench depan LT-LT (tadinya mau di sofa-sofa dekat M* D**ald, tapi ga dapat tempat XD), and the story began:

– Pertama, gw baca soal A. Ternyata bonus, coding, submit:

366 A – The Best Team 2010-11-07 11:15:03 YES

– Lanjut, baca deh soal B. Sekilas kirain ini LCA… Tapi setelah dianalisis, akhirnya nyadar kalau ini soal ad hoc. Coding, AC.

426 B – Largest Labeled Common Ancestor 2010-11-07 11:24:23 YES

– Terus baca soal C… Soal bonus XD. Coding bentar AC.

448 C – Stack Machine Simulator 2010-11-07 11:27:22 YES

– Baca soal I, dp. Coding lagi, AC.

523 I – Maximum Sum in Matrix 2010-11-07 11:38:42 YES

– Baca soal H… Keliatan simulasi biasa. Coding, submit…

623 H – Disconnected Graph 2010-11-07 11:55:24 NO – Time Limit Exceed

Tuing, TLE. Terus hitung kompleksitas… Oh iya, kelebihan satu ordo. Ywdh, aljabar keluar:

(a + b + c + …)^2 = a^2 + b^2 + … + ab + ac + … + ba + …
jawaban = ((a + b + c + …)^2 – (a^2 + b^2 + …)) / 2
Submit, WA.

651 H – Disconnected Graph 2010-11-07 11:59:28 NO – Wrong Answer

– Ywdh, ganti soal dulu. Soal D. Soalnya terlihat manis. Coding O(n^2 lg n) dengan percaya diri – TLE.

692 D – Sum to Zero 2010-11-07 12:05:51 NO – Time Limit Exceed

– Geez, baca lagi code yang untuk soal H, ternyata outputnya mesti pake integer 64-bit. Submit lagi, AC.

704 H – Disconnected Graph 2010-11-07 12:07:38 YES

– Balik ke code soal D, optimize (tapi masih O(n^2 lg n)), submit:

734 D – Sum to Zero 2010-11-07 12:10:52 NO – Time Limit Exceed

Ternyata belum cukup baik. Sebenarnya dari awal udah kepikiran O(N^2), tapi males codingnya XD. Well, kondisi sudah memaksa :)) Akhirnya recode:

931 D – Sum to Zero 2010-11-07 12:36:50 NO – Wrong Answer

Hitung baik-baik, ternyata 2000^3 = 4 Milyar, jadi perlu pake unsigned int. Ganti:

950 D – Sum to Zero 2010-11-07 12:39:46 NO – Wrong Answer

Damn XD ternyata 2^3 itu 8, bukan 4. Ganti pake long long:

1020 D – Sum to Zero 2010-11-07 12:48:37 YES

– Terus langsung ke soal E. DP, coret-coret dikit, coding, submit:

1083 E – Playing with Boxes 2010-11-07 12:58:21 YES

– Terus Timo suruh gw buat yang F… Dan tentu gw ga mau XD. Gw bilang ke dia mau kerjain G dulu… Eh dia bilang gw belum tentu bisa AC soal G. One-Hit-Disproof:

1280 G – Finding The Right Song 2010-11-07 13:26:54 YES

Wew… Langsung senang karena waktu itu di posisi pertama (yang lain belum dapat 8 =D)

– Terus pindah ke soal F (last one). Analisis bentar: Query-querynya itu ada di subtree, salah satu cara buat nangani ini dengan Euler tour (lalu disederhanakan jadi preorder atau postorder terserah). Terus sisanya tinggal k-th query di range [a,b]. Terus bilang ke Timo, gw bisa coding ini dalam 20 menit. Wkwkwk… Ternyata k-th query yang ada di notebook gw beda sama yang ini. Akhirnya batal deh 20 menitnya. Ywdh, bikin struktur data sendiri. Coret-coret, ternyata bisa pake segment tree. Spacenya butuh O(n lg n), per query O(lg^3 n). Terus liat waktu, tinggal 1 jam. Berhubung gw rada males coding segment tree, gw memutuskan pake bucket-bucket (struktur data yang O(sqrt ( n )). Waktu itu, hasil perhitungan gw menyatakan bahwa per querynya O(sqrt( n ) lg n). Setelah coding, tiba-tiba gw nyadar, perlu binary search lagi jadi O(sqrt( n ) lg^2 n). Damn XD Kalau dari awal ga salah hitung gw udah coding segment tree… Ya sudahlah, keliatannya pasti TLE. Tapi karena udah ga sempat recode (tinggal beberapa menit), kelarin aja. Setelah selesai, debug-debug, submit.

1848     F – Searching in Tree     2010-11-07 14:48:57     NO – Wrong Answer

Tada… WA. Dengan optimis (karena ga TLE), gw debug itu di menit-menit terakhir… Contest end.

Akhirnya harus puas solve 8 soal.

Moral story:

  1. Jangan telat satu jam kalau mau ikut contest :))
  2. Hitung kompleksitas dengan baik, walaupun keliatannya gampang
  3. Hati-hati sama long long :))

Selamat untuk para pemenang :-bd Dan thanks buat juri yang udah siapin soal-soal dengan baik dan udah memperbolehkan gw jadi bayangan 😀 (khusus untuk Shu, *ga* thanks untuk password account gw XD. Setelah kontes gw baru sadar kalau kita bisa ganti password -_-“)

1848 F – Searching in Tree 2010-11-07 14:48:57 NO – Wrong Answer
Advertisements