Senin, 01 Mei 2017

TOKI Open Contest April 2017

Blog berdebu ya..

*Belum ngeblog ICPC sinting Yangon*
*Belum ngeblog banyak hal*
*Belum mikir soal CPC lagi*

Yah anyway, sekitar 3 minggu yang lalu ada TOC April Mop. Biasanya aku demen kontes ngawur kayak ginian, tapi kebetulan gak bisa ikut karena Sabtu pas kontesnya ke Jogja buat Vocomfest :" Tapi penasaran sama soalnya. Jadinya yaudah, nanya Ammar bisa jadi tester apa nggak, terus dibolehin :P

Tepat seminggu sebelum kontes Ammar ngajak pingpong di Pacil. Yowes, pingpong. Cuma aku baru main bentar aja udah capek :( Habis itu duduk-duduk. Daripada nganggur, aku bilang "mending ngetes TOC deh". Terus yaudah, habis gitu sambil Ammar masuk-masukin soalnya, aku ngetes.

WARNING!

Kalau masih pengen nyoba soalnya, sangat tidak dianjurkan membaca melewati peringatan ini.


Soal yang pertama Ammar masukin Genap Ganjil. Pas baca: "Ah ini RTE-nya pasti masalah underflow atau overflow". Terus aku pikir cin kalo baca input yang jebol bakalan overflow seperti layaknya overflow pas operasi aritmetika. Jadinya handling WA-nya dengan asumsi itu.

I HAVE NEVER BEEN SO WRONG

Wrong Answer terus mampus. Sampai akhirnya aku nyoba lihat behaviournya. Ternyata kalau overflow bakalan dibikin jadi INT_MAX, kalo underflow jadi kebalikannya. Cool stuff C++ :O Kira-kira 20 menitan buat ginian :s

Lanjutnya yang keluar Kuku Kuku Kaki Kaki Kakak Kakak Kakek Kakekku Kok Kaku Kaku. Gak butuh waktu lama untuk nyadar kalo query kata apa yang ngandung huruf k ke-k2.

Lanjutya soal L. Sebelum ngetes, Ammar ada nanya karakter di Death Note yang hurufnya satu doang. Yang kuinget N, terus gak inget Mello itu disingkat juga apa nggak. Terus keluar soal ini. Di soal kan deskripsinya bahasanya ngawur. Ngecek, oh, bahasa Romania. Habis translate, keluarnya cara pakai Death Note. Habis itu kirain ini kayak recon CTF, jadinya nyari "L 50 Death Note." Yang keluar malah beginian:


As you noticed, itu videonya kutonton bentar :" Terus aku nyoba-nyoba hurufnya, ternyata di testcase gak ada "N" :/ Baca tentang L, ada bilang beratnya 50 kg. Yakalik pake berat badan ~_~ Terus nyasar ke Aturan Death Note. Scroll, terus mikir:

"Ini aturan berapa ya?"
"LI, 51"
"...."
"goblok"

Baru nyadar kenapa deskripsinya pake bahasa Romania -_- habis gitu ngetes lagi AC.

Habis itu aku baca soal yang Jangan Jijik. Langsung eneg. Kukira karena tahun sebelumnya ada soal yang agak serius (pake hash gitu), jadinya sekarang ada soal serius lagi. Terus ku-skip, sambil bilang "jijik Mar"

Terus soal Haki!. Awalnya bingung gitu kenapa pake karakter yang gak biasa, terus aku takutnya kalo gak bisa dibaca pake C++ atau Pascal. Tapi ya belom kebayang solusinya, awalnya cuma mikir 4 itu ngeliat sample 4 ada 4 karakter  ░.

Terus Ammar ada soal, yang kami tes ternyata brute forcenya kegampangan. Daripada soal itu yang keluar, aku suggest kalo bikin soal yang harus liat verdict dari juri kalo mau ngerjain. Jadinya ya, soalnya jadi soal Impossible. Terus aku bingung gitu kenapa cuma boleh Pascal.

Ayaz: "Ini napa cuma boleh Pascal?"
Ammar: "Biar gak bisa isProbablePrime Java"
Cerdas kamu Mar.

Habis gitu balik ke Jangan Jijik, percakapannya:

Ayaz: "Ini kalo soal serius aku gak mau ngerjain deh"
Ammar: "Yaudah, coba aja kamu liat submissionku"

Terus aku liat submissionnya, cuma print sample doang.


Ammar terus nyuruh buat baca soal lebih teliti. Baru nyadar kalau ada kalimat "Oh ya, percobaan-percobaan tersebut dapat dilihat pada contoh masukan dan keluaran di bawah ini" --" Habis itu, dia bilang kalau sample itu contoh perpotongan yang bisa dia temuin di internet :") Pas aku ngetes soalnya, masih belum ada cek jawaban pake scorer. Terus aku bilang kalo scorer tetep perlu, yaudah terus ditambahin. Pengennya kemaren bikin statement itu semakin di tengah paragraf, tapi ternyata pas kontesnya juga gak ada yang dapet tanpa perlu begitu :") 

Balik ke soal Haki, aku nyoba ngitung karakter hitamnya. Ternyata ada pas 439 :O Habis gitu nyoba ke sample 2 juga gitu. Baru di sample 3 nggak. Ngeliat karakter abu-abunya. Oh, jadi kayak connected component terpisah gitu. Dari situ dapet kalau cari maksimum hitam di suatu connected component. Lama sih baru dapetnya. Habis gitu aku coba read karakter aneh itu, ternyata satu karakter itu jadi 3 integer :O Yang penting bisa dibaca deh.

Habis itu ngerjain soal Melantunkan Musik. Oh, kayak pantun. Palingan juga cuma nyari karakter terakhir yang munculnya ganjil kali. Eh bener ._. Habis gitu aku nyoba ngetes pake karakter selain huruf kecil. Masih AC. Jadinya minta benerin scorer hehe.

Terus untuk soal terakhir, Nyan Nyan Nyan belum siap, katanya Ammar karena TLX gak support gif. Yaudah, jadinya testingnya nanti dulu.

Habis gitu aku coba ngoding python buat Haki. Terus RTE. Anehnya baca input aja RTE :/ Terus aku lapor Ammar. Habis gitu, aku nyoba juga di soal L pake python. Kadang RTE kadang nggak ._. aneh pisan. Jadinya dicoba diinvestigasi.

Pas pulang, Ammar minta cari lagu wibu buat dipasang di sample. Yaudah aku coba cari. Pertama potongan lagunya Aqours, "Omoi yo Hitotsu ni Nare":

chikadzuitari hanaretari datta ne
umaku ikanakute zutto
tsutaerarenai koto ga atta yo
majime na kao shite

 Di-reject karena polanya "abba", Ammar maunya "abab" atau "aabb". Damn :( Habis gitu dapet potongan lagu dari Gurren Lagann, "Sora-iro Days":

Sugita kisetsu wo nageku hima ha nai
Nido to mayotte shimawanu you ni
Kazoekirenai hon no sasayaka na
Sonna koukai kakaeta mama

Terus karena animenya manly, disaranin cari lagi. Yasudah deh. Akhirnya dapet dari Aqours, potongan "Sky Journey":

yume kanaetai kara itsudemo
akiramenai koto ga daiji da to
naze honki de katareru no darou
yuuki ga tsutawareba daijoubu

Di-approve, pasang di sample terakhir. Tapi kayaknya gak ada yang sadar :P

Nah terus soal Nyan itu udah ada, tapi belom berjalan sesuai keinginan Ammar. Tapi yaudah, aku tetep nyoba. Descnya pas itu: "Find the lost cat first!". Ngeliat nama asset kucing-kucing itu via inspect element, mikir "paling nama filenya juga 404.gif". Ternyata ada. Hehe.

Berapa hari setelahnya, Ammar bilang Nyan udah siap. Sekarang descnya: "Find the lost compressed-cat first!". Yaudah, artinya 404.zip. Nah pas itu aku buka dari HP. Pas extract di HP, gif-nya gak jalan :( Habis itu aku buka laptop terus extract. Oh, gifnya jalan :P Tapi kayak gif biasa gitu. Sambil buka gifnya aku juga buka terminal, terus nyoba strings lah, binwalk lah, buka pake gedit lah, gak ada yang aneh. Terus tau-tau ada frame yang rasanya off. Jadinya aku buka https://ezgif.com/split, terus masukin gifnya. Dapet frame yang aneh itu



Heleh QR-Code. Buka QR scanner di HP, terus bacanya "open nyan.cat for 9001 seconds!". Enak aja. Jadinya cari terkait itu, terus ternyata ada achievementnya. Masukin achievementnya, AC. Niat juga ini. Terus ternyata 404.gif itu masih ada di soal, kata Ammar biar jadi "Red Herring", padahal karena TLX gak bisa delete, bisanya revert. Terus jadi penasaran, ini Ammar obsesi over 9000 atau apaan.

Terus dapet laporan kalo python-nya masih belom tau kenapa. Yaudah, jadi diskusi, enaknya bolehin pake python atau nggak. Ujung-ujungnya bolehin, tapi dikasih warning gede di announcement :v

Pas kontesnya aku masih ngadem di Amplas (Ini correct spelling singkatan Ambarukmo Plaza atau bukan?._.), terus minta Ammar kayak live commentary di chat. Sayang gak bisa ngikutin full :s Kayaknya menarik :s

Oh dan anyway, congrats untuk para pemenang! Selera humor kalian kayaknya kompatibel sama sejenis aku sama Ammar :P

Mungkin postnya ini dulu deh hehe, ngeblog lagi mungkin nanti pas liburan.

Pengen cepet libur :"(

Trivia yang tidak ada hubungannya dengan konten di atas:

  • Pas ngetes, Ammar iseng bikin kayak markdown gitu di chat FB. And holy shit it works!
  • Terus kami ngetes pake status pake akunku. Awalnya set visible to-nya diri sendiri doang. Terus gak bisa
  • Terus ngeshare isengnya Ammar tadi via status. Sudah lama gitu, baru sadar visibility-nya masih buat diri sendiri doang. Aku emang cerdas.

Selasa, 20 Desember 2016

ICPC Regional Jakarta 2016

Jadi beberapa waktu yang lalu (sebulan lel) aku ikut ICPC Regional Jakarta, dan karena pengen nulis, serta biar gak jadi wacana, aku tulis sekarang aja wkwk. Kemaren aku ikut sebagai tim Awrakin, dan Alhamdulillah bisa dapet peringkat 5 serta predikat Best National Team. Rada kaget sih huehue

Awrakin

Tim ini anggotanya aku, Zamil, sama Rakina. Namanya udah tau kan ya plesetan dari mana (code qlean semua suci aku penuh bug). Ini tim rada ga jelas sih, soalnya:

  •  Aku selalu ngejek Rakina. Contoh: "Kin, kok fotomu yang di nametag Gemastik gak ada jerawatnya?"
  • Rakina kerjanya mukul sama nendang aku. Koleksi luka luar tambah banyak semenjak kontes sama Rakina
  • Zamil kayak sudah pasrah sama keadaan ini
Kami udah pernah ikut 2 lomba sih sebelumnya, INC (peringkat 2) dan Gemastik bidang pemrograman (peringkat 3) dengan nama Ristek - Kuikutsaja. Tim ini, entah karena sibuk atau apa, hampir nggak pernah latian :'( Sekalinya latian malah rada fail :''' Cheatsheet juga kami asal aja, jadinya pakai punya Terharu :') dengan sedikit modifikasi :') Strategi nggak ada yang khusus, paling yang sering dibilang:

  • Kalo ada soal query kasih ke Ayaz

H-1

Harusnya kan hari sabtu ada practice session. Jum'at malam, aku baru inget kalo gak nyuci, bisa-bisa aku kehabisan baju dalam. Padahal biasanya nyuci hari sabtu atau minggu. Yaudah, jadinya malam-malam aku nyuci walaupun tepar parah. Terus kan hari itu ada demo, dan malamnya ada kerusuhan. Kupikir paling besok udah beres. Jadinya jam 10 aku tidur..
.
.
Dan terbangun esok harinya untuk mendapati akibat kerusuhan, kegiatannya dipadatin di hari Minggu. Kenapa masalah di Indonesia gak selesai-selesai sih hiks.
Jadinya hari Sabtu aku nonton anime sama ada nge-gym di CF sendirian. Hasilnya gak jelek, cuma aku sadar kalo aku tambah retard. Ngoding modular exponentiation udah ngebug. Malamnya aku tidur agak malam gara-gara keasikan baca :') RIP kontes besok.

Contest Day

Paginya aku bangun agak telat dari yang aku harapkan :' Untungnya gak telat buat ngumpul sih. Jam 6:15, naik bikun, pas belokan FIB bikunnya kayak mau keguling, terus sekalian "ngambilin" orang-orang yang telat. Nah, pas di perjalanan jadinya aku kayak yang tanggung jawab buat perjalanan itu.

Tapi kayaknya ini keputusan yang salah, karena aku bikin nyasar dengan salah nunjuk belokan di peta :'( Alhasil nyampenya jadi sedikit telat, maafkan aku kawan-kawan :'( Ini bukan cara yang baik untuk mengawali pagi. Entah kenapa dari tahun lalu aku selalu kecapekan sebelum tanding pas hari-H :'(

Sampai di Binus, langsung registrasi terus ambil baju sama nametag. Pas ketemu orang-orang, kayaknya pada ngetawain rambutku. Apa salahnya botak!? Botak itu adem parah dan potong laginya butuh waktu lama! #abaikan Habis ganti baju, escortnya ngajakin sarapan dulu, biar fotonya nanti. Aku sendiri walaupun ikut ke tempat makannya cuma ngambil minum, gara-gara udah sarapan sebelum berangkat. Kayak tahun sebelumnya, sarapan ini jadi tempat ngobrol sama ngegosip bareng sahabat-sahabat dari univ lain, sekalian foto-foto.

Lanjutan dari TOKI UI Welcoming Party
Credits: ICPC Regional Jakarta 2016

Udah gak terbang-terbang photoshop lagi :')
Credits: ICPC Regional Jakarta 2016

Selesai sarapan, kami lalu ke tempat fotonya. Untung gaya yang dipropose Rakina gak senajis gaya pas welcoming party.

Normal enough
Credits: ICPC Regional Jakarta 2016

Habis foto, kami masuk ke auditorium buat pembukaan. Selama beberapa lama pas pembukaan aku justru main sih :P Gak terlalu merhatiin pembukaan lel. Habis pembukaan, ada practice session. Kan practice session itu buat ngetes environment dll. Terus entah kenapa, yang bisa ngetik cepet sekarang cuma aku (idk Rakina Zamil kayak kurang pas sama keyboardnya). Practice sessionnya juga kebanyakan ketawa-ketawa doang, mostly aku ngetawain Rakina Zamil ngebug :v yang penting udah tes TL dan ini itu deh.

Selesai practice session, kami dapet makan siang. Kali ini aku nyomot sedikit makanan biar gak kelaparan. Habis itu kami yang muslim sholat. Disini dilema : Dijamak apa nggak? Akhirnya aku gak ngejamak, biar nanti ada waktu dimana aku bisa jalan-jalan keluar cari udara segar. Kadang kalo lagi ngerjain soal atau bikin soal aku juga sering gitu soalnya: jalan-jalan, kosongin pikiran, biar fresh lagi buat mikir, dan seringnya efektif.

Anyway, setelahnya persiapan buat kontes. Kami masuk ke ruangan masing-masing. Kebetulan, kami seruangan sama TeamTam (Agus+Rais+mas-mas Malaysia). Yang enak, kami duduk di paling belakang, dan tim sebelah kami gak datang. Jadinya aku tanpa dosa sering jalan-jalan di belakang. Lagi-lagi, kalo penasaran, ini kebiasaanku di rumah, mikir sambil jalan-jalan keliling rumah (aku gak bisa diem). Terus ada yang lucu, jadi kan nama tim kami Awrakin. Terus di amplop yang isinya cheatsheet tim kami, orangnya itu keliatan banget salah nulis, Awka Awrakin. Sayang gak difoto :(

Lalu, kontes pun dimulai! Karena ICPC Jakarta biasanya taruh soal bonus di A, jadilah aku baca A. So far so good, sampe akhirnya baca:


To punish teams who did not read this problem statement carefully, we'll add one trick input: if the input is 04-05-01, the output should be 1 (not 6).


*Mikir* *Baca soal lagi* *Mikir keras*
(dalam hati) "INI GIMANA CERITANYA OUTPUTNYA JADI 1? KAN ADA 6 CARA? MASAK SALAH NGERTI SOAL SIH?" #emosi

Akhirnya setelah Rakina bilang bisa ngerjain A, aku nyerah dan cari soal lain. Rakina juga nerangin soal L kayak interval-interval apa gitu, cuma aku gak ngerti. Zamil terus bilang E kayaknya gampang, tapi aku gak yakin, dan yaudah dia ngerjain itu dulu. Lalu aku baca soal J. Wah, cuma rumus-rumus deret geometri terus pake mod inverse. Terus aku lupa rumus deret geometri. Jadinya nurunin rumus dulu. Habis itu, A buatan Rakina ngebug, dan jadinya aku minta dia ngeprint dulu, sementara aku kerjain J. Lalu, J - Super Sum Accepted!

Aku terus baca soal K, dan rasanya soal ginian familiar. Tapi habis nyoret-nyoret, ternyata soalnya beda :( Habis itu, aku baca soal L, karena kalo mirip sekelebat yang Rakina jelasin, dan karena TeamTam udah AC, harusnya ini doable. Turns out, selain ada input yang gak penting (agency), ini mirip soal yang pernah kubuat untuk Coderclass tahun ini :/ DP simple, statenya waktu. Karena paranoid, aku tambahin coordinate compression biar statenya gak terlalu banyak, terus submit, dan L - Tale of Happy Man Accepted!

Setelah itu, aku coba bantuin Rakina benerin A. Aku baca codingannya Rakina, dan baru ngeh statement yang bikin aku gak ngerti itu ternyata cuma perlu dibikin if --" Dia suspect kala baca inputnya bermasalah, jadi yaudah kami parse manual. Tapi tetep WA. Aku terus baca soal D. Hmm, mungkin DP on Tree. Tapi constraintnya gede gitu. Mikir bentar, baru nyadar kalau tree-nya gak penting :( dan ini jadi soal kombin yang klasik gitu :( aku coret-coret rumusnya dulu biar gak ngebug, terus ngoding, dan D - Pay Day Accepted!

Aku lalu balik ke soal A. Aku baca codingannya lagi, terus baru sadar: "Kin, kalo ada angkanya yang dobel kayak 03-03-03, lu keluarannya 6 gak sih? bukannya 1?" Dan kami jadi dapet pencerahan gitu :') Aku terus modifikasi kodingannya biar bisa handle itu, dan A - Confusing Date Format akhirnya AC :'))))

Meanwhile, Zamil pake komputer karena mau ngetes soal E. Dia bilang ada soal query-query gitu, yang artinya belum kubaca. Aku baca, dan ternyata soal F. Sekilas baca, keliatan kalau model soal binser. Terus binser satu-satu kelamaan, jadinya mikir, "ah ini kayaknya bisa parallel binser deh. Tapi napa query-nya bentuknya persegi semua ya?". Akhirnya, karena Zamil kayaknya butuh waktu, aku gusur (dan ini bakal terjadi berkali-kali dalam kontes ini), dan ngoding F. Untuk caranya, aku pakai BIT 2D untuk keep-track banyak bilangan yang nilainya <= x dalam suatu interval. Jadinya solusiku O((Q + N^2) log N log MAXVAL). Awalnya gak yakin AC, tapi bodo lah ya, submit aja. Dan kagetnya, F - The Cure AC! Yay ada first solve suatu soal :")))

Habis itu aku baca soal B, dan come up sama solusi yang O(N * length * 26 * log (N * length * 26)) pake hashing. Ngecek TL yang gede, aku cukup confident bisa lolos. Aku terus nggusur Zamil lagi (habis dia ngeprint codenya), terus coding B. Pas coding, Rakina nanya di cheatsheet ada theorem matik atau nggak. Seingetku sih ada, jadi kubilang iya. Terus dia nanya "lu tau McNugget nggak?".
.
.
.
.
Kenapa ini orang nanyain McD? Terus kukacangin dan lanjut ngerjain B. Habis selesai dan tes sample, submit. Terus TLE. Sad. Aku coba mikirin optimizenya, tapi gak dapet. Terus aku nanya ke Rakina dia lagi ngerjain soal apa. Ternyata soal I, dan itu soal yang dia nanya McNugget-McNugget itu. Aku baca deskripsi soalnya, intinya dikasih N bilangan prima, dan K, cari bilangan X terkecil, X >= K, sehingga X bisa dinyatakan sebagai kombinasi linier N bilangan tersebut, dengan konstanta pengalinya non-negatif. Terus Rakina jelasin kalo dia pernah baca McNugget's Theorem yang kayaknya bisa ngebantu ngerjain soal ini, tapi dia lupa theoremnya gimana. Habis ngecerna soalnya, baru nyadar kalo ini mirip parah sama soal pas Pelatnas 4 :'( pelajaran berharga: baca semua soal. Aku ngesolve dengan modelin ini sebagai shortest path, dengan vertexnya merupakan hasil modulo prima terkecil. Terus primanya juga udah dibikin unique, kompleksitasnya kurang lebih O(smallest_prime * (N + smallest_prime)), karena entah kenapa aku paka Dijkstra's O(V^2). Submit, dan I - Peculiar Microwave AC!

Habis itu Rakina bilang B harusnya bisa O(N * length * log (N * length)). Jadi dia ngereduce semua operasi jadi pakai delete, dan itu make sense. Jadi kalau insert, bisa dipandang dengan ngedelete dari string hasil insert. Terus substitue bisa dipandang sebagai banyak string lain yang setelah delete satu karakter, dan kita delete satu karakter dari string ini, hasilnya sama. Aku lalu modifikasi solusi, dan udah stres, kebiasaan namain variabel dengan kata kasar jadi keluar. Habis itu submit, dan ternyata masih TLE. Terus habis itu baru sadar ada double counting juga, tapi karena keluarnya TLE bukan WA, tetep aja bermasalah.

Karena Zamil masih berkutat di soal E, aku sama Rakina lalu coba kerjain soal lain. Kami lalu nyoba soal K. Rakina bilang pakai dp bitmask gitu, cuma kompleksitasnya O(N * 2^15), gak feasible. Tapi jadinya aku kayak dapet hint: Formulasikan dp[mask] sebagai banyak set yang unionnya hasilnya mask, dan anggotanya non-empty (bisa 1). Aku mikir, harusnya compute dp[mask] ini bisa dalam O(3^15). Jadinya, untuk ngitung dp[mask] kita bakal iterasiin per submask-nya dia untuk ngitung subproblemnya. Cuma, aku gak dapet cara untuk nge-enforce orderingnya biar gak double counting :( sekalinya dapet, brutal parah, jadi O(15^2 * 3^15), dan jelas TLE, tapi begonya kusubmit.

At this point karena pusing, aku lalu turun ke bawah buat sholat. Balik-balik, tetep nyoba mikir. Terus Rakina bilang soal C constraintnya aneh, mungkin bisa di-maxflow. Tapi aku gak dapet graph modelling-nya. Aku malah ngerasa ini bisa di-ternary search, cuma gak yakin. Ngeliat scoreboard udah ada yang AC, bodo lah ya, coba aja, gak bakal nyesel juga. Jadinya aku nyoba ternary search + DP on DAG. Pas ngoding, tau-tau udah masuk 1 jam terakhir. Submit. Nunggu. WTF, C - Stress Factor AC.


Habis lapor C AC, Zamil takeover komputer lagi. Aku lalu nyoret-nyoret soal K lagi. Seketika merasa bodoh: Gampang nge-enforce orderingnya. Seandainya mask kita pecah menjadi submask1 dan submask2, kita bisa menganggapnya kita menambahkan elemen dengan nilai submask1 ke dalam set dengan unionnya submask2. Bagaimana caranya supaya orderingnya fix? Kita cukup pastikan submask1 mengandung MSB dari mask, dan artinya submask1 selalu lebih besar dari submask2. Ini bisa berjalan dalam O(3^15), jadi aku langsung nggusur Zamil lagi dan ngoding K. Habis tes sample, aku submit, dan udah gak TLE. WA. dafuq. Baca codingan, ternyata lupa ngemod. goblok. Habis ngemod, submit, dan K - 2-ME Set AC! :')

Habis itu, aku keluar buat ngemil bentar. Lumayan ada minum sama snack enak. Terus aku masuk lagi. Pada tahap ini, untuk soal E aku percaya saja sama Zamil dan Rakina. Aku terus baca soal G. Gak ngerti, dan sekalinya ngerti pasti gak sempet. Baca soal H. gak ngerti juga. Yaudah deh ikut bantuin Zamil Rakina.

Aku gak ngerti mereka ngoding apaan, jadi aku cuma baca kemungkinan bugnya. Pas skimming codenya, anehnya aku gak baca ada kata mod sedikitpun. Padahal seingatku constraintnya sampe 10^9, yang artinya kasarannya jawabannya bisa 10^27. Aku tanya ke Zamil, dan responnya "astaga bener juga". Yey.

Lalu semua penghitungan kami kasih mod, terus submit. WA. asem. Baca-baca lagi, ada fungsi yang kayaknya balikin range, terus nanya Zamil, "ini emang boleh dimod ya?". Terus ternyata nggak :")) Habis ilangin mod di situ, submit lagi, dan AKHIRNYA E - Guessing Game AC!!! Aku seneng banget sampai ninju Zamil. Kalo gak AC sedih kan Zamil dari siang sampe sore cuma kerjain itu :'(

11 menit terakhir kami desperate ngedebug B, karena cuma itu harapan satu-satunya buat nambah AC. Tapi udah gak kuat, dan akhirnya kami berakhir dengan 6+3 AC. Alhamdulillah :') dan setelah ngitung aku ngoding 7 soal dan bantu debug 2 soal :O Harusnya lebih banyak memperbudak Rakina. Ngobrol sama Agus, dia bilang timnya AC 10 M(_ _)M

Keluar dari ruangan sambil membawa banyak balon, terus ngobrol sama yang lain bentar. Habis itu ketemu Pak Denny, lapor kalo nambah 3. Terus top 3 INC dipisah, disuruh makan bareng sponsor dan orang-orang penting lainnya. Awrakin makan bareng orang Tokopedia. Aku sendiri gak terlalu banyak ngomong, karena terlalu capek sama pusing. Cuma makan sama minumnya aja banyak :P

Setelah semua itu selesai, ternyata makan-makan yang seabrek - tahunan ICPC Jakarta - juga udah selesai :( Kami lalu ke auditorium, sambil ngambil pernak-pernik yang belum diambil kayak yang dari Tokopedia. Lagi-lagi aku nyempetin buat main SIF bentar. Terus pas acara penutupan, ada beberapa speech dan performance, ada speech dari Menkominfo (aku baru tau Menkominfo itu yang mana lel). Oh, selain itu ada lucky draw. Meh, event ginian gak mungkin aku menang sih. Selain stat luck-ku yang kecil parah, aku juga gak dapet nomornya :v Habis itu ada Contest Review dari Pak Suhendry. Terus pengumuman pemenang. Pengumumannya dimulai dari INC, jadinya kami maju karena peringkat 2. Yey hadiah!

Top 3 INC
Credits: Pak Denny

Setelahnya pengumuman ICPC. Unlike tahun sebelumnya, sekarang pakai resolver :O Lumayan lah seru ngeliat terbang-terbang. Pas run pertama, laptopnya entah kenapa mati atau ngehang gak merhatiin. Sedihnya, pas ngeproses WinRAR - Free Trial Forever. Udah saatnya kita bayar kayaknya.

Pas run kedua udah aman. Pas Awrakin diproses, awalnya B fail, terus terbang karena C. Okeh. Terus terbang lagi karena E :') At this point, kami paling atas di tim lokal :O Lalu untuk ketiga kalinya, kami terbang karena K, dan sekarang di posisi 4. Terus kegusur sekali, posisi 5. Was-was bisa 5 besar apa nggak, tergantung tim Running dari Universitas Keio. Dan ternyata, AWRAKIN RANK 5 :")))) Kami lalu maju untuk dapat hadiah Best National Team.

Best National :")
Credits: ICPC Regional Jakarta 2016
Hadiahnya gak kira-kira: 1 Drone, 1 Samsung Gear VR, sama Xiaomi yii (gak salah tulis kan ya?).  Habis itu pengumuman top 3 nya, dan hasil akhirnya:

  1. AcThPaUNpPuAmCmBkCfEsFmMdNoLr - National Taiwan University
  2. TeamTam - National University of Singapore
  3. LINUX - University of Engineering and Technology - VNU
Congrats!
Habis itu ada foto-foto lagi :D :
Sama Pak Menkominfo
Credits: Pak Denny

Cah UI
Credits: ICPC Regional Jakarta 2016
Hari sudah malam, sementara PR MD2 belum dikerjakan. Orang-orang UI lalu mencoba cabut. Tapi aku diajak Irvin buat foto bareng SC P1 2017. Jadi ya, kami foto dulu :')

SC P1 2017 - {Prabowo,Stacia}
Credits: Irvin
Setelah itu akhirnya beneran kembali ke Depok, kembali ke realita bahwa besok kuliah dan tugas belum dikerjakan.

In the end, terima kasih panitia yang sudah menyelenggarakan Regional ICPC yang bagus :") dan bisa tetap lancar walaupun hari sebelumnya ada kekacauan :"( Secara pribadi aku paling senang dengan Regional Jakarta, walaupun bisa saja ini karena aku memang belum ke banyak Regional lain :P

Terima kasih juga Rakina Zamil, dari INC, Gemastik, sama ICPC tahan setim sama orang kayak aku :') dari INC bikin banyak "dosa" (penalty), Gemastik nge-retard, dll. Yang jelas ICPC ini gak mungkin hasilnya sampe begini kalo gak ada kalian, tapi malas jabarin kenapanya huehue.

Seperti lomba biasanya, lesson learned, beberapanya:

  • BACA PETA DENGAN LEBIH TELITI
  • Biasakan ngertiin hampir semua soal untuk nentuin prioritas ngerjain -- I harusnya bisa lebih cepet disolve kalo gak terburu-buru ngerjain B
  • Harusnya Rakina bisa lebih banyak diperbudak
  • Biasakan mendengarkan, jangan seenak jidat ngejudge McNugget itu cuma dari McD
  • Nekat itu gak salah
  • Belajar sesuatu itu gak pernah rugi -- seandainya gak pernah belajar konsep Parallel Binary Search paling gak dapet F :")
 Trivia:

  • Supir busnya serem :(
  • Makna Nem_HCNU_Peno direveal sama Pak Suhendry. Sad.
  • Zamil ngeprint soal E tiap kali aku gusur. Total bisa 5-8 kali ngeprint.
  • Droneku sama Samsung Gear VR-nya Rakina dijadiin doorprize acara Pekan Ristek, walaupun masih gak terima kepada siapa Dronenya jatuh. Samsung Gear VR-ku nangkring di Ristek, karena di rumahku juga gak ada HP yang compatible.
  • Suvenir Tokopediaku hampir ketinggalan, untungnya dibawa Zamil :')
  • Sampai hari ini, sertifikat INC sama Gemastik punya Zamil sama Rakina masih di aku karena aku lupa ngasih. Padahal sebulan ada di tasku :v 
  • Jika dihitung di tingkat nasional, maka kami:
    • Peringkat 2 INC
    • Peringkat 3 Gemastik
    • Peringkat 1 (nasional) di Jakarta
    • :O
Sekian dulu kalik yah? Lanjutnya either ngebahas soal atau ngeblog Yangon. Yangon harus diblog sih, karena belum pernah ada perjalanan seabsurd itu dalam hidupku :)

Sabtu, 05 November 2016

Recap Sekian Bulan

Duh udah lama gak ngepost apa-apa :< Beberapa minggu yang lalu pengen ngeblog tentang soal CPC CompFest dan malah jadi wacana :' Anyway, post ini dibuat karena gak sengaja baca postnya Ammar di sini, dan kurasa aku agak terlalu capek dan sibuk main LLSIF, ketimbang bikib post mendetail, mungkin aku cuma bikin sedikit rekap event-event yang sudah berlalu~

  • [Early August] Rencana sering sepedaan dan renang jadi sedikit wacana, untung masih bisa berenang
  • [Mid August] H-1 Prelim CPC balik ke Depok, malamnya begadang ngurusin soal :< 
  • [Mid August] Prelim CPC! Ada beberapa masalah :< Untung bisa selesai :""
  • [Late August] Nee-san graduates, beberapa hari hedon di Depok berkat kehadiran ortu huehue. Ultah barbar bersama beberapa orang barbar
  • [Early September] Mendapat dorongan dari lubuk hati untuk membuat repository tentang CP di github. Sekarang hiatus. Sad
  • [Early September] For no reason nyoba main LLSIF. Sampe sekarang masih main lel
  • [Mid September] Nitip wibu stuffs ke Xing-Xing yang pergi ke AFAID. Selamat tinggal duit Pelatnas~
  • [Mid September] Gak tidur demi CPC :" Masalah muncul di mana-mana pas kontes. Absolutely one of my most depressing moment setelah gak bisa pergi ke OSN. Soal yang kubuat jadinya terlalu susah, tahun depan dimudahin deh :<
  • [Early October] Welcoming Party TOKI Alumni Biro UI! Diajak ngurusin tapi mostly gabut, maafkan :"" Free food xD
  • [Early October] (Ceritanya) ngajar di Pelatnas, walaupun aku cuma ngebacot gak jelas huehue
  • [Early October] INC 2016! Secara ajaib tim Awrakin bisa rank 2. Alhamdulillah, dengan banyaknya "dosa" yang kubuat masih bisa
  • [Late October] Finally yellow in CF! xD
  • [Late October] I think I performed poorly on my mid-term test :(
  • [Late October] Ristek - Kuikutsaja Rank 3 di Gemastik bidang pemrograman. Sejujurnya aku ngerasa performa kami harusnya bisa lebih baik lagi. Semoga buat ICPC Jakarta bisa lebih baik lagi
  • [Late October] Baru kali ini ngegacha yang agak hoki. Got 1 SR, 3 SSR, and 1 UR!
Ini sampe diketawain meja sebelah

Satu dari sekian barang. Thanks Xing-Xing!
Tenang, nggak dicolong

Image courtesy: Soko

Who knows taun depan gimana? :P
Image courtesy: Pak Denny




Ceritanya jadi pembina :P

Image courtesy: Pak Yugo

GG RNG

 As a side note, banyak sih yang aslinya pengen kutulis: Perjalanan IOI, ngeblog algo, ngisi github tadi, bikin post tentang pembuatan soalku di CPC (Belajar FPB was a rollercoaster ride :D), dll. Tapi entah kenapa sekarang rasanya mau nulis susah, kayak mendingan dipake istirahat atau hal lainnya :') Tambahan, sekarang highscore basket timezoneku 423 :') #roadto500 Oh, tambahan lagi. Jadi ceritanya ada deadline baca buat minggu depan, yang aku masih kurang 500 halaman. Terus senin ada deadline PR lain. Terus besok ICPC Jakarta, dan rasanya kayak gak ada persiapan. Udah, sekian.

:')


Sabtu, 27 Agustus 2016

A Little Note

  Jadi hari ini ceritanya resmi 19 tahun. Reaksiku:
  • Dafuq udah tua
  • Dafuq aku bisa bertahan hidup selama ini
Well, I guess not many people will understand why i write the second one. Ada beberapa hal yang harus dicatat mungkin untuk setahun terakhir ini:

  • Bisa kuliah :O
  • Bisa ikut lomba CP dan menang beberapa :O
  • Bisa jadi Scientific Committee di TOKI buat Pelatnas sama OSN :O
  • Bisa bikin soal CP :O
  • Bisa nyiapin kontes bersama yang lain :O
  • Tambah gendut :(
  • Tambah retard :(
  • Ndak kuning-kuning di CF :(
  • Koleksi rating change satu digit semakin banyak :(
  • Nyandu nonton anime :/
  • Nambah koleksi cerita retard buat anak cucu (kalo punya) ^^
Mungkin ada lagi yang harusnya dicatat, tapi yasudahlah. Aku juga aslinya bukan orang yang peduli masalah beginian sih :/

Yang lebih pengen kutulis, tentang kontes CP.

Beberapa waktu yang lalu, ada penyisihan CPC CompFest 8 kan ya? Mungkin sudah tahu, tapi aku jadi panitia di situ. Maafkan kalo masih banyak kekurangan pas kontes, semoga di final kontesnya bisa lebih baik lagi.

Dalam bikin kontes, salah satu yang sering kudenger: "Kontes yang bagus itu yang semua solve at least 1, semua solve ada yang solve, dan ga ada yang solve semua". Well, untuk kontes penyisihan kemaren, kami mencoba mempersiapkan dengan mempertimbangkan itu. Oiya, scoreboard akhirnya bisa dilihat di:

Mungkin bakal keliatan kalo yang SCPC ga ngikutin yang ditulis di atas (ada yang ga disolve), walaupun secara teknis, semua soal di penyisihan ini disolve setidaknya satu peserta (soal G SCPC juga muncul di JCPC, bedanya cuma di SCPC multi-tc).

Nah, kenapa aku bahas ini? Jadi, kemaren baru aja penyisihan Gemastik cabang pemrograman. Aku ikut sama Zamil dan Rakina, di tim Ristek - Kuikutsaja. Alhamdulillah, kemaren lagi ga retard, jadi hasilnya.. bisa dibilang memuaskan? Oh, dan soal-soalnya menurutku keren-keren :) dan aku cukup menikmati soal-soalnya.

Hal ini, membuatku berpikir lagi. Sebetulnya, target kontes itu apa? Kontes dengan hasil yang bagus seperti itu? Atau apa?

Aku yakin aku sudah sering mikir hal berikut, tapi mungkin kutulis di sini aja biar ntar di masa depan bisa bikin counter berapa kali mikir begini: "Yang penting yang ngerjain menikmati kontesnya. Entah karena kepuasan mendapatkan AC, atau karena mendapatkan sesuatu yang baru". Tentu saja, membuat kontes yang bagus berdasarkan kriteria di atas juga bisa dirasa cukup penting :P

Udah cukup kali ya ngebacot siang ini :P Semoga bisa nyiapin final CPC yang lebih baik dari penyisihannya >.< Dan bisa kagebunshin in case semua terlalu sibuk untuk live commentary >.<

Jumat, 12 Agustus 2016

Pelatnas 4 TOKI 2016

*bersihin debu*

Jadi mungkin sebagian besar dari kalian sudah tahu, kalau sekarang kontingen Indonesia untuk IOI sudah sampai di Kazan. Lomba benerennya masih 2 hari lagi sih mulainya. Padahal, sampai 2 hari yang lalu masih Pelatnas 4 loh. Sekalian bersihin debu di blog ini, aku mau nulis apa aja yang kulakuin selama P4, dari yang emang pas P4, atau yang technically di luar P4, kayak TOKI Open Contest Juli 2016. Apa kalian sadar kalau aku pakai kata ganti aku? Yah, habis kalo dipikir-pikir, "boku" lebih enak daripada "watashi". Dah, back to topic deh.

Persiapan P4 kalo gak salah udah dari sebulan~2 bulan sebelumnya. Masalah pertama justru nyari asisten. Kebanyakan anak TOKI di UI magang atau ada urusan lain pas masa-masa P4. Jadinya sampe nyari asisten dari luar. Untungnya, ada Prabowo sama Xing-Xing :") Selain itu, Irvin dihitung asisten ndak ya (?) btw, baru nyadar ini asistennya beda univ semua :O

Setelah asisten beres, masalah lanjutnya itu jadwal. Awalnya, Irvin udah nyiapin jadwal dengan asumsi Pelatnas 3~4 minggu. Terus kepotong jadi 2 minggu. Jeder. Potong banyak, gabungin banyak, jadi deh jadwal baru. Di jadwal baru, Pelatnas mulai ada latian dari tanggal 28. Jadinya, aku sama Prabowo beli tiket tanggal 27. Menjelang Pelatnas, tau-tau jadwalnya digeser sehari, jadi mulai ada latian dari tanggal 29. Which means kami kecepetan sehari. Jeder lagi. Untung aku udah bayar kos, kalo nggak mungkin kami menggelandang di sekitar UI.

Tanggal 27 aku pun cabut ke Jakarta. Pas di Jakarta, nungguin dulu Prabowo, biar bisa naik taksi bareng ke Depok (biar bisa patungan huehue). Sampe di kos, diminta ke UI dulu untuk ini-itu-buat-pelatnas. Nggak banyak sih yang dilakuin, cuma kontak Bu Aya, terus nambahin sublime sama apcalc di komputer yang nantinya dipake peserta. Sorenya, habis makan mi instan yang tentunya semua orang Indonesia tahu, kami balik ke kosanku. Nah, kan itu H-3 TOKI Open Contest, sementara masih banyak komponen soal yang belom siap :") aku sendiri belum bikin deskripsi soal sama sekali. Alhasil, malamnya aku bikin deskripsi. Entah kenapa, bikin solusi sama generator testcase rasanya lebih mudah daripada bikin deskripsi :"" Aku habisin 2~4 jam untuk bikin deskripsi Rammeow sama Ramduel :"" Oh iya, tengah malam ada sesi briefing bersama Irvin, yang Agus juga tau-tau nongol. Briefingnya biasa aja, yang ga biasa paling cuma habisin setengah jam coba nelpon HP-nya Irvin. Itu juga ga dapet hasil yang diharapkan. Belakangan diketahui itu karena Irvin retard.

Besoknya, setelah sukses bangun agak siangan, kami lalu siap-siap cabut ke Wisma Polimedia. Ya, nginepnya tahun ini di situ. Oh iya, walaupun gitu, aku lebih sering di kos, karena lebih nyaman juga, walaupun jadinya nggak dapet makan pagi sama malam x( Pas nyampe, ternyata pesertanya juga udah pada nyampe. Hasilnya, sore itu dihabiskan main CS. Malamnya, aku sama Prabowo nyicil urusan P4. Selain itu, aku juga mulai nonton Love Live! (jangan tanya kenapa).

Besoknya pun P4 dimulai. Setelah pembukaan, + aku ngebacot kayak briefing P4, peserta (kedepannya nyebutnya GoF ya :P) mulai latihan. Nggak ada yang signifikan sih buat hari pertama. Actually, masih harus ngetes-ngetes soal TOKI Open Contest sama simulasi P4, tapi karena aku ga bisa ngurutin prioritas, aku lanjut nonton anime. Oh iya, kayak biasanya, Pak Yugo bikin kopi di Pelatnas ini. Nah, berhubung aku tahun lalu ga sempet bikin kopi gegara P4 pas puasa, aku baru belajar bikinnya kemaren :P Nah, masalahnya, kopi yang dibikin kebanyakan gegara GoF pada ndak suka minum kopi :""" Akhirnya aku minum 3 gelas, sudah jauh lebih banyak dari dosis kopi yang kuminum selama satu tahun :"

Hari Sabtu, simulasi pertama P4. Sambil ngamatin simulasi, aku lagi-lagi nonton anime. Selain itu, juga nyoba update soal buat TOKI Open Contest berdasarkan review tester. Nah, terus hari ini, jumlah kopinya kayak hari sebelumnya, firasat nggak enak :( Habis simulasi selesai, istirahat sejenak, terus GoF dihajar Speed Practice. Karena bosen, aku sama Prabowo juga ikut :P ez win :P Di lain pihak, Ucrut, capek dihajar simulasi, bahkan udah ga kuat ngerjain soal Div 2 C. Lemah kamu crut.

GG WP
 Dan bagaimana nasib kopi yang banyak itu? Kuminum 5 gelas. Mati.

Sorenya, habis hujan-hujanan demi mencapai kos, aku nyoba internetan. Jahannamnya, inetnya CUPU PARAH. Jadi ngeri buat TOKI Open Contestnya, tapi bodo lah. Pas TOKI Open Contest, awalnya horor karena first AC nya aja cukup lama (10 menit), tapi ke belakangnya udah nggak terlalu masalah. Ada sih masalah, jadinya naikin memory limit Ramduel biar O(N^3) lolos pake int. Selain itu, aku agak kesel karena ada beberapa klarifikasi yang agak retard :/ tapi ya bodo lah. Oh iya, aku belum ngucapin sebelumnya, jadi congrats iafir for winning this TOC :D Most likely kami nggak bikin editorial, tapi ini quick solution per soal:

  • Rammon : Ad Hoc, cobain aja per tipe.
  • Rammeow : Misal left[x] menyatakan batas terkiri, sehingga subarray left[x]+1..x itu isinya unik. Pentingnya, left[x] ini non-decreasing. Solusiku untuk soal ini manfaatin binary search, rumus deret aritmetika, sama prefix sum.
  • Ramduel : print(input()). ada proofnya di olimpinfo
  • Ramdom : Bisa cek untuk masing-masing kasus, tapi ujung-ujungnya semua kasus bisa direduce ke suatu cara yang simple.
  • Ramdor : Untuk n >= 3, yang optimal itu nyobain per 3 orang. Oiya, strategi optimal orang jago pasti ngepick support, sampai support*2 >= banyak pemain. Untuk n < 3, harus hati-hati sedikit.
Malamnya, aku susah tidur, dan kebangun jam 3 pagi, terus nggak bisa tidur lagi :" Paginya, chat sama Irvin malah receh parah
jago = receh? karena Ammar juga receh
 Menjelang siang, pas mau tidur, dapet email dari Pak Rully perihal beli batik ke Margo. Ga jadi tidur dah :"" Aku lalu ke Polimedia, pas nyampe lagi pada main. Karena ngantuk parah, aku akhirnya malah tidur di kamarnya Sergio. Pas bangun, ternyata berangkatnya masih sore ;_;

Sorenya, aku, Prabowo, GoF, Pak Rully, sama Pak Fauzan berangkat ke Margo City. Nyampe di sana, ketemu Pak Yugo, terus milih-milih batik. Pas nganggur, jadinya ngomongin soal-soal peluang yang ceritanya kalo dipikir geje pol desu. BTW, berhubung Irvin belom dateng, jadinya ukurannya dia pake patokan ukuranku :P dan yang bikin kaget, ini Sergio sama Klungs kenapa bisa kurus parah ;_; Setelah beli batiknya, kami lalu makan di Marugame. Ini rada random sih milih tempat makannya :P Terus aku cerita kalo pas aku makan di situ aku ndak kenyang. Terus, berhubung Stacia makannya nggak banyak, aku dikasih separo udonnya :D Kurang lebih jadinya gini:

*makan udon*
*kenyang*
*minum teh*
*laper lagi*
Sial.

Habis itu pulang yey :v

Hari senin, diawali Speed Practice. Terus Xing-Xing udah mulai ngasisten :D Paginya, aku ngilang dulu karena mau ngurus ini-itu yang diminta kakakku. Alhasil, sprint Fasilkom -> FEB -> Barel -> Margonda -> Fasilkom. Untung 1 jam beres :D Balik-balik, nontonin Speed Practice, sama nonton anime + ngurusin pembahasan coderclass. Siangnya, aku bawain materi Randomized Algorithm, pake slide tahun-tahun sebelumnya, dengan sangat random. Kurasa aku ga jelas parah pas ngomong x( Habis itu, GoF lanjut latihan. Kayak biasa, Stacia sama Sergio kelar, sementara aku menghabiskan waktu ngetawain Ucrut.

Selasanya, ada materi dari Pak Stef tentang NT sama kriptografi. Pas baca-baca slidenya, ternyata mirip banget sama slide tahun lalu xD Hari itu juga Prabowo balik ke Medan :'( Sisi positifnya, jadi ada ngurus "gaji"-nya Prabowo ke Bu Aya, dan bisa ngeskip sebagian materi :P Walaupun ntar ada kena karma sih haha. Siangnya ada simulasi. Ada satu soal yang kuurus dan deskripsinya panjangnya kayak setan, untung ada yang ngerjain. Kalo nggak.. well.. :'( Sorenya, kayak biasa Depok hujan deras. Dan malamnya, berhubung hari selasa.. nge-rush beresin pembahasan coderclass sama Agus sampe larut malam :( kebiasaan deadliner ini ndak pernah beres. Sisi positifnya, pas selesai, bisa leha-leha selama seminggu lagi, sampe nge-rush lagi.

Besoknya, acara seharian cuma repeating soal pelatnas-pelatnas sebelumnya. Soal yang dibuka banyak pol desu, cukup yakin nggak sempet selesai semua. Karena pas P3 gak sempet jelasin, jadinya aku jelasin soal Elephants - IOI 2011. Ada 2 hal related to CP yang bisa dihighlight hari ini:

  1. Sebisa mungkin sebaiknya ada 2 orang yang nyiapin solusi.
  2. Kalo bisa, masukin testcase manual yang tricky. Karena manual, kecil juga nggak masalah.
Ini kutulis untuk reminder di masa depan juga.
Selain itu, aku juga lumayan terkejut pas ada yang solve soal yang kukira terlalu aneh untuk disolve. Btw, kalo ingatanku ga salah, hari ini pada main seri terbaru dari seri Henry Stickman, game yang aku tau gara-gara dulu adekku sering mainin :P yang baru ini kocak parah dah.
Seharusnya, aku udah mulai nyicil kerjaan untuk simulasi terakhir. Tapi, berhubung tanggung kalo ga nyelesein Love Live!, akhirnya aku nge-rush nonton 5 episode terakhir + Movienya.

Keputusan yang salah.
Karena setelah selesein semua bagian animenya, aku ngerasa hampa.
To the point besoknya pengen bawa bantal ke Fasilkom, dan tidur seharian.
:'(
Esoknya, niat bawa bantal diurungkan. Bukan karena gak etis. Tasku nggak muat kumasukin bantal.

Hari Kamis diawali simulasi. Sambil GoF simulasi, ngegalau + ngurusin kerjaan lain. Selesai simulasi, makan, lanjut sesi repeating. Kayak kejadian hari Sabtu, kayaknya udah susah fokus kalo udah dihajar simulasi. Semuanya solve 1 dari 3, terus udah gak fokus. Aku juga malah ngajak main ._. btw, kami main Get On Top, game absurd yang pertama kumainin pas P4 tahun lalu. Ez win ngelawan semua orang :P Ucup ngotot rematch karena kalah mulu. Cupz sih. Malamnya, rusuh beresin simulasi terakhir.

Hari Jum'at, aku bawa tas lain untuk bawa baju ganti, karena mau nginep di Polimedia selama tiga hari kedepan. Jum'at agendanya latihan doang. Secara logis, ga mungkin agendanya gitu doang. Pasti tengah-tengah main kan. Selain itu, si Ucup juga ada wawancara beasiswa, dan Klungs agak demam. Jadinya dibuatin tempat tidur darurat pake kursi, tambah bantal dari tas yang isinya bajuku.

Dewa Klungs kelelahan!
Pas Ucup wawancara, di komputernya ternyata ada essay beasiswanya kebuka. Iseng, aku, Stacia, Sergio, Xing Xing baca. Ada beberapa grammatical error yang ditemuin, tapi yaudahlah. Pasti udah disubmit juga kan. Cuma ya kenapa ga minta orang lain proofread dulu Cup :" Siangnya, pas ishoma, main Get On Top lagi, terus Sergio tau-tau udah jago x( Tentunya Ucup masih Cupz. Xing Xing juga sampe buka video orang main Get On Top di youtube :") Btw, pas main kami juga nyoba mainin dengan aneh-aneh.

still a better love story than twilight
Meanwhile, karena ngantuk, aku akhirnya pake tempat tidur darurat yang tadi dipake Klungs :P Biasanya aku bisa tidur 5 menit doang untuk fresh lagi. Si Ucup bikin code yang banyak pakai kata klungs, to the point that it was unreadable. Sorenya, balik ke Polimedia. Habis makan malam, ada pembicaraan geje yang terjadi antar cowok.


Setelah itu, biar besok ga kesiangan, GoF tidur, sementara aku sama Xing Xing tidurnya masih maleman lagi, ngobrol anime.

Besok paginya pun kami ke Fasilkom kayak biasa, telat dikit karena ga pake jalan pintas dan alhasil muter jauh x( Untungnya simulasinya ga pas jam 8. Oiya, simulasi yang ini nggak kayak biasanya, soalnya ini sparring sama tim Singapura. Ada 2 sesi, yang sabtu ini yang ngurus wong Indo, yang senin nanti wong Singapur. Untuk simulasinya, secara unexpected problemsetnya ternyata bagus :O Walaupun, aku ada buat blunder dan jadinya.. sedikit depresi. Pas simulasi, Klungs agak sakit, dan jadinya dibilang kalo misalnya udah gakuat, stop aja. Nah, menjelang akhir, skornya dia itu bagus, cuma belum nyampah di satu soal. Gregetan, jadinya aku malah live report klungs.

esmosi
Karena Speed Practice ditiadakan dan diganti BNPCHS besoknya, siangnya pun kami langsung balik ke Polimedia. Ucup beda sendiri, pergi ke tempat kakaknya. Di tengah jalan,

"Kecewa lah Yaz"
"Hah?"
"Kecewa"
"Hah!?"

Ternyata karena aku pake baju ICPC Singapura, di hari sparring Indo Vs Singapura. Sialnya, untuk sparring di hari senin aku bakal pake baju yang sama, berhubung baju yang kubawa ke wisma dikit parah.

Nah, pas balik jadinya bingung. Berhubung Klungs sakit, sebaiknya kan dia stay di wisma, karena IOI >> BNPCHS. Sementara itu, artinya harus ada yang jagain. Karena Xing Xing harus ke Binus, artinya aku yang stay. Ujung-ujungnya, ternyata ada ortunya Klungs, jadinya aku juga bisa ke Binus. Nah, biar Klungs ada porsi Speed Practicenya sendiri, alhasil aku juga nyariin kontes yang bisa dipake. Random pick juga sih ujung-ujungnya.

Hari Minggu pagi, udah pada siap-siap ke Binus. Klungs aslinya ngerasa udah enakan, cuma daripada parah lagi.. jadinya stay di Polimedia. Yang ke Binus jadinya aku, Stacia, Sergio, Pak Rully, Xing Xing. Ucup pergi sendiri ke Binus, untung nggak nyasar. Kalo diperhatikan, member ini cukup imbalanced:

  • Xing Xing -> Problemsetter
  • Sergio -> Peserta
  • Aku, Stacia, Pak Rully, Ucup -> Supporter (?) Tukang rusuh (?)
Kayaknya mulai hari ini juga aku kebiasaan ngomong "Nico Nico Nii" walaupun nggak terlalu suka Nico. Karena Xing Xing, jadi ada variannya, "Ucup Ucup Nii". Kayaknya pas registrasi kami rusuh parah deh xD Pas pembukaan juga, ide-ide liar ini keluar:

  • "Xing, tempat beli lightstick deket sini di mana ya? Ntar acung-acungin pas Sergio dipanggil" -Aku
  • "Ndak pake balon yang biasa di main bola itu kah?" -Stacia
  • "Ntar gini ga sih, pas Sergio AC kita teriak dari luar, WOOO SERGIO AC SOAL X" -Lupa
Oh iya, tadi kan dibilang ini BNPCHS buat Speed Practice. Entah banyak yang tahu apa nggak, tapi biasanya di BNPCHS emang ada yang ngedummy, dengan berbagai alasan. Nah, Sergio kan ikut sebagai peserta. Ucup sama Stacia ngedummy. Aku juga ngedummy sih. Salah satu alasan aku ngedummy, biar bisa memperkirakan level peserta untuk CPC CompFest nanti >:)
pindah Binus
Habis pembukaan yang sedeng-sedeng aja, peserta pergi ke ruang lomba. Aku, Ucup, Stacia ke ruang tempat para dummy berkumpul. Xing Xing ke tempat panitia. Pak Rully? Ilang. Entah ke mana. Tak ada yang tahu.

Pas di ruang dummy kan dikasih komputer masing-masing. Nah, jadinya bisa liat scoreboardnya practice session. Ngeliat banyak submission yang kenceng banget, aku malah jadi penasaran, ini orang-orang tau tujuan sebenernya practice session apa nggak :/ Tapi daripada mikirin itu, ada masalah yang lebih penting. Pertama, ndak bisa login. Habis itu, Felix Jingga yang ngurus. Habis ndak bisa login, yang bisa dipake cuma Visual C++. Ada Notepad++, tapi ga ada g++, kalopun ada ga bisa setting environment variable. Panik, Ucup download installer devc++, terus install di tempatnya sama Stacia. Pas di tempatku malah ga kebaca OMG. Terus, ngecek soal yang di website lomba, GG pol desu. Ada PDF, tapi isinya cuma "Soal BNPCHS 2016 Final Round tersedia dalam bentuk tercetak". Like, dafuq. Ini udah habis waktu practice session, dah mau mulai malah. Akhirnya, bisa install devc++, telat semenit atau 2 menit doang untungnya.

Pas mulai, Xing Xing bagiin bentuk tercetak soalnya. Aku lalu baca-baca sekilas. Ah, A ad hoc doang. Paling formatnya aja rese. Luckily, aku tau cara pake scanf sama printf yang bikin mudah soal ini. AC dalam menit yang sama kayak first solve soal itu di kontes aslinya xD Habis itu, aku lanjut baca soal. Malah baca E dulu. Oh, DP sama faktorisasi doang. DP-nya bisa di-speedup dikit pake kayak sliding window. Coding, terus AC \ :v /

Habis itu liat scoreboard resmi, syok ngeliat udah pada AC 3 :O Jadinya, lanjut ngerjain I yang intinya faktorisasi aja, sama F yang brute force ikutin soal doang. Setelahnya, aku baca soal G, yang Alhamdulillah ada penjelasan samplenya :" Coding kombinasi pake mod inverse, terus AC. Nah, habis itu ngeliat soal B. Oh, 0/1 BFS aja. Bisa pake deque. Ngoding, submit, WA.

Wat. Wat. Wat.

Yakin bener, aku coba assert-assert. Terus nemu kalo ada testcase yang ga ada transportal x( Habis itu, bikin asumsi-asumsi liar, dan akhirnya AC :O Setelahnya, aku baca soal H, dan nyesel ngerjain B dulu, karena soal kayak H itu udah lumayan sering kuliat :( Sisanya tinggal C, D, J. Rasanya udah pernah liat C, tapi D juga keliatan doable. Ngeliat D constraintnya lumayan kecil, aku bikin DP yang kompleksitasnya kayak 200^4, tapi mutusin YOLO aja. Terus AC. Habis gitu, ngerjain soal C, yang proof solusi greedynya ketemu sambil nge-construct solusi. Di menit 117, tinggal soal J \ :v /

Habis itu Xing Xing masuk, dan karena udah waktunya makan siang, kami putusin buat beli makan dulu di KFC terdekat. Kan belinya buat aku, Xing Xing, Ucup, Stacia, Pak Rully. Pas balik, aku baru inget kalo PAK RULLY NGGAK MAKAN AYAM. Terus panik. Tapi yaudah deh, semoga ada jalan. Sampe di Binus, ngajak Stacia sama Ucup makan dulu, habis itu sholat dzuhur. Sesudahnya, liat scoreboard, si Sergio udah leading parah. Aku sendiri males ngerjain soal J karena rada matik, dan firasat harus pake extended euclid, yang diajarin Pak Stef tempo hari tapi nggak kuperhatiin :( Begitu Sergio udah AC 9, yang kulakuin malah "Duh Ser udah Ser jangan AC semua lah". Begitu Sergio AC 10, damn. Yaudah kerjain J. Bikin brute force + math, di submission ketiga AC :O :O :O Total penaltyku lebih dikit dari Sergio yey \ :v / walaupun seandainya aku ikut kompetisi aslinya pasti performaku lebih rendah :P

Setelah itu, kompetisinya selesai, dan peserta udah bisa leha-leha. Meanwhile, aku stres karena Pak Rully ilang dan gak bisa dihubungi. Jadinya ya, sambil nunggu disuruh ngumpul buat pembahasan, penutupan dll, kami ngobrol-ngobrol dulu, sampe akhirnya Pak Rully nelpon, dan kami semua jalan ke tempat yang tadinya dipake pembukaan.

Habis makan siang peserta, agendanya pembahasan-yang-super-singkat-that-i-dont-even-know-if-contestants-will-understand-the-main-idea. Pas sesi pengenalan Binus, sesuai rencana, aku sama Ucup turun buat sholat ashar. Pas balik, ternyata masih sesi pengenalan. Wew. Setelah beberapa lama, akhirnya pengumuman pemenang. Rank-nya udah lumayan predictable sih sebenernya, kalo ngeliat sebelum freeze :/ Nah, terus Sergio dipanggil.

"... Dan champion dari BNPCHS adalah!!!!!"
*Pak Rully berdiri*
"Sergio Vieri!!!"

*dalam hati* "Wah, Sergio jadi tua dan besar"
Terus ketawa-ketawa sama Xing Xing xD

Di sini aku masih sendiri...

Sampai om datang untuk menemani
Congrats untuk para pemenang! Though, sebenernya aku expect lebih dari kalian, terutama medalis OSN dan veteran Pelatnas. Nope, bukannya aku nganggep kalian cupu emang cupu sih , tapi kalo ngeliat performa OSN serta Pelatnas, dan soal-soalnya, harusnya kalian bisa lebih dari ini.

Setelah penutupan, kami lalu cari makan malam. Kayak tahun sebelumnya, hari minggu adalah hari suci "konspirasi menghabiskan uang makan yang jumlahnya gede". Jadi, tujuan utamaku ke BNPCHS bukan ngedummy, tapi cari makan enak. wkwk.

Konspirasi duit makan
Setelahnya, balik ke Polimedia, nonton, ngobrol-ngobrol, tidur.

Paginya, aku beres-beres karena hari itu aku mau balik ke kos. Hari itu juga, si Irvin sampe Indo, walaupun ujung-ujungnya kena macet di jalan. Kalo sparring sebelumnya baik soal maupun OJ-nya dari orang Indo, sekarang soal sama OJ-nya pake punya Singapura. Pas kontes, karena penasaran, aku nyoba-nyoba soalnya juga. Sampe akhirnya males karena ada soal tipe kreatif yang deskripsinya panjang kayak setan x( Tengah kontes, si Irvin dateng. Terus, pas siang-siang, aku, Irvin, Xing Xing makan sate di kantin Fasilkom yang emang enak itu. Siangnya dilanjutin repeating. Sementara Irvin ngurusin Dengklek Contest, aku yang harusnya nyicil pembahasan coderclass, malah ngeretard. Sorenya, adanya penyesalan. Baru inget hari selasa bakal pamitan, yang berarti waktu yang bisa dipake bikin pembahasan berkurang x( Jadinya malam itu pembahasan aku kebut dikit. Nah, pas ngetes solusi, ada dampak gara-gara ngurus soal functional kayak IOI. Seharusnya:

printf("5\n");

Malah jadi:

return 5;

Masih ada kebegoan lainnya, tapi kuskip aja yah :(

Besok paginya, kami lalu cabut ke Kemdikbud di Senayan. Jadi inget pelepasan tahun lalu, mana aku perginya pake batik IOI tahun lalu :') Pas di sana, kayak biasa, ngaret. Untung bawa laptop. Jadinya nyicil coderclass lagi hueue. Habis itu, pas orang-penting-yang-aku-lupa-siapa masuk, beresin laptop, terus mulai acara formalnya. Terus foto-foto.

Go get Golds!
Sumber: Pak Yugo

Extended edition
Sumber: Pak Yugo
Habis foto-foto, agendanya udah lumayan bebas. Terus, malah nyambung ke pembicaraan "apa nama panggilannya Irvin pas masih kecil?". Muncul spekulasi seperti Jojo, Jono, Mojo, Mojo Jojo, dan lainnya. Terus Xing Xing nanya mamanya, dan keliatan puas sekali. Tapi karena dia pelit, nggak dikasih tau ke yang lain.

Setelahnya, ada pembicaraan antar pembina tentang Bebras. Kami juga dengerin. Nah, aku ga sengaja ngeliat pas Xing Xing bales sms mamanya. Jadinya tau nama panggilannya Irvin pas kecil. A very kawaii nickname indeed. Habis itu, balik ke wisma. Nah, kan pesen mobil. HP-nya Xing Xing sinyalnya weak. Jadinya pesen pake HP-ku. Terus begonya, mobil kami beda. Padahal aku mau langsung balik ke kos :""" Untung gap kedatangan kami di Polimedia ga beda-beda banget. Malamnya jadinya fokus ngerjain pembahasan coderclass sampai deket tengah malam. Gamau deadliner lagi deh :'(

Note: kalimat terakhir itu pasti bakal dilanggar.

Di beberapa paragraf sebelumnya, aku ada nyebut Dengklek Contest kan ya? Jadi ini kayak tradisi tahunan sejak 2011, dimana di P4 ada kontes yang isi soalnya mostly ngetroll. Nah, untuk tahun ini, beda formatnya sama tahun lalu. Actually tahun lalu sih yang formatnya beda sendiri. Jadi untuk tahun ini, ada 3 tim, yaitu:

  • Tim Deng, Sergio + Ucup
  • Tim Klek, Stacia + Klungs
  • Tim Guest a.k.a. Asisten, Aku + Xing Xing
Dengklek Contest ini kayak nandain penutupan P4. Which means dilakukan hari Rabu, 10 Agustus. Pagi harinya, aku bangun kayak biasa. Sholat kayak biasa. Mandi kayak biasa. Sampe pas keramas, aku ngerasa ada yang aneh.

*keramas*
*naruh shampoo*
"Perasaan biasanya naruh shampoonya ga di situ deh"
*mikir*
"Dafuq tadi itu sabun cair gobloook"

Udah pertanda ga enak sebelum kontes.

Terus aku pergi ke Fasilkom, dan ternyata bisa sampe lebih dulu, bahkan setelah 10 menit kupake sarapan. Habis briefing Dengklek Contest, kami ke workstation masing-masing. Karena ini ajang seru-seruan, jadinya kami (aku + Xing Xing) ngeretard. Bikin template yang kayak gini. Oiya, aku nulis "nico nico nii" nggak pake googling, jadi kalo salah maapkeun.

Di kontes kami ribut parah :") Dapet non-zero pertama dengan manfaatin apcalc yang kuinstall sebelum P4 mulai :P Habis itu ngerjain soal yang intinya nyari password suatu user. Kejadiannya:

*masukin nama user ke search bar*
*keluar error, usernya ga ada*
"dafuq, ini ngapain kita cari passwordnya kalo usernya aja nggak ada"

Setelah ngespam untuk soal itu akhirnya dapet 100 :") Terus kami balik ke soal pertama kami, dan nyoba oret-oret. Sementara itu, ada yang AC soal yang keliatan serius, dan Alhamdulillah aku dapet solusinya walaupun ngebug retard dulu :P Habis itu kejar-kejaran gila sama tim Deng. Tim Klek? GG WP. In the end, kami menang berkat sampahan di P1 xD Makanya sering-sering nyampah xD

#klungs #uminisasi #niconii
Siangnya, ada sesi sama Pak Sur. Terus naasnya si Ucup sakit. Jadinya dilarikan ke RS dulu, periksa sama minta obat. Sorenya, karena tinggal foto-foto doang, Ucup dikirim balik ke Polimedia duluan, sementara aku balik ke Fasilkom. Habis itu, foto-foto. Oh iya, Sergio dapet coffee maker karena poinnya paling tinggi di P4 ini.

Congrats Ser!
Sumber: Pak Yugo

GoF - {Ucup}
Sumber: Pak Yugo

Apa aku masih cukup muda untuk dianggap GoF? :D
Sumber: Pak Yugo
Sorenya lalu beres-beres kos, dan cabut ke Polimedia. Dikasih puzzle Hanayama sama Irvin, yang puzzlenya lebih di nyusun daripada ngebongkar :( Klungs, Xing Xing, sama Irvin terus main Coup, ditemani aku nyetel "Bohong Bohong Bohong". Sukses ngerusak konsentrasi.

Besok paginya lalu pergi ke Soeta. Terus ngeliat kopernya Irvin yang ajigile gedenya. Pas udah di Soeta, artinya udah mau perpisahan. Aku sebenernya tipe yang bingung kalo acara gitu ngomong apaan. Rasanya ada yang mau diomongin, bingung nyampeinnya gimana.

Jadinya yah, pesan untuk tiap GoF:

  • Sergio: Jangan retard-retard, tetep pertahankan kebiasaan untuk nyampahin tiap soal.
  • Stacia: Jangan terlalu terfokus di satu soal, inget untuk bagi waktu di soal lain.
  • Klungs: Kayak Stacia sih. Oiya, mungkin kamu harus maintain kondisi saat performa optimalmu? :P Walaupun tentunya bahaya kalo kamu sakit di sana. Jaga kesehatan desu.
  • Ucup: Jangan terfokus di satu soal, sama BACA SOAL LEBIH TELITI. Semoga aja nggak masalah karena ada translasi soal untuk tahun ini. Jangan sampe kepisah dari rombongan, kamu kayaknya kalo ilang bisa ditemukan tinggal tulang.
  • Semua: Maintain kondisi yang bagus pas lomba. Secara pribadi, aku sendiri ngerti rasanya under pressure pas kontes (remember i said it took me 1 hour to write sort for scales?) Kalo perlu, beberapa kali ke WC aja. Sama yang udah Irvin tekanin sama aku tulis di atas, jangan lupa nyampah :") last but not least, have fun! Kontes emang penting, tapi jangan lupa bersenang-senang juga :D Mungkin karena game kalian bisa saling unfriend kayak kejadian tahun lalu :P
Welp, rasanya masih ada yang pengen kubilang lagi, tapi sementara ini aja dulu deh :" Semoga pas kontes nanti aku sama Agus bisa bikin commentary di FB yang bagus :D dan semoga ga wacana lol.

Walaupun roleku di sini cuma sebagai asisten sama babu SC , aku pengen berterima kasih sama semua orang yang terlibat di P4 ini, karena tanpa kalian semua, acara ini gak bakal kayak gini :")

Sekian dan sampai nanti lagi! :D

Trivia, in a random order:

  • Jerawat di hidungku yang gede banget itu pecah 2 kali pas P4. Darahnya keluar banyak, to the point i said "Waduh! Pecahkan jerawat, mahasiswa ini dilarikan ke rumah sakit"
  • Dan ketika aku bersihin darahnya pake tissue, Xing Xing kira merah dari darah itu pola di tissuenya...
  • Dapet ilmu kalo soal aneh-aneh itu dapetnya dari ujian matdis.
  • Ada yang tahu arti klungs? Karena ada #klungs di twitter pinoy. Sampai sekarang gak ada yang tahu artinya apa.
  • "Kita harus lebih kuat dari kita yang dulu" -Ayaz, setelah beberapa kali ga bisa buka tutup botol minumnya sendiri.
  • Setelah kejadian 5 gelas, karena aku yang bikin kopi, selalu kupastiin siapa aja yang mau minum.
  • Narik susu ternyata menyenangkan.
  • Orang yang bisa ganti galon tanpa basah itu pasti dewa. Aku sama Xing Xing ganti galon, hanya untuk "mandi".
  • Once i said "Klungs, aku papamu". Ga ada yang berani extend joke itu pas ngomong sama mamanya Klungs.
  • Meng-counter recehnya Irvin, dibuat joke "klungs" dan "oren" secara bertubi-tubi sampai Irvin kesel.
  • Mungkin beberapa sadar, kaos P4 ini mirip P1 2016. Bedanya, ga ada orang kribo di belakangnya. So yea, it's like P1 punya, but cooler.
  • Rei-chan, Rudo Reina, adalah karakter original antara aku dan Xing Xing yang sumber inspirasinya kurang lebih mirip Irwanto antara aku dan Agus.
  • As a side note, aku tahu siapa itu user ReynaldoWijayaH dari TOC Juli :P
  • Kenapa ada #uminisasi ? Karena yah.. reasons.
  • Grup asisten namanya Tukang Makan Pelatnas 4 TOKI 2016 gara-gara aku sering nanyain soal makan :P Terus Prabowo juga ikut nanya makan :P
  • Related to klungs, pas aku ikut nganter ucup ke RS, ada yang nyari klung di FB, dan nemu orang dengan nama Klung Koon Klung :O
  • Ada sendal croc hitam yang ketinggalan di kamarku sama Xing Xing. Kasihan ga ikut ke Kazan >.<
  • Apalagi ya hmm...

Sabtu, 04 Juni 2016

Parallel Binary Search

Kembali lagi ke postingan tentang algo \ :v /
Jadi, kali ini saya mau ngebahas salah satu teknik yang jarang dipake dan mungkin tidak terlalu berguna, namun karena menarik dan lucu (?) jadinya pengen saya bahas :3

Sooo.. dari judul kan bilangnya Parallel Binary Search?  Itu apaan? Binser pake multi-threading? Sebenarnya, nggak ada term yang bener-bener umum dipake untuk strategi ini. Cuma karena kalo di CF biasanya nyebutnya begini, yaudah saya sebut begini juga. Atau enakan binser berjamaah?

Biasanya, teknik ini dipake untuk soal yang di-solve secara offline. Ada kan soal-soal query yang perlu di-solve secara offline kayak pake Mo's Algorithm. Gampangnya, ini Mo's yang O(log N), bukan O(sqrt N). Terus, ketika saya mengatakan binser berjamaah, saya tidak terlalu becanda. Memang, di teknik ini, kita melakukan semua binary search sekaligus. Biar mudah, lihat contoh soal ya. Connecting Graph

Kalo males baca, intinya gini. Ada N vertex dan M operasi, dimana operasinya itu:
  1. Bikin jalan antara u dan v
  2. Nanya kapan vertex u dan v pertama kali terhubung, baik langsung maupun tidak langsung. Jawab sesuai kondisi graf saat ini (bisa aja u dan v kehubung nantinya, tapi kalo sekarang belum, -1).
Ada solusi yang pake sparse table, bahkan kata Anthony bisa O(N log N) secara online. Tapi, biar sesuai dengan post ini, ayo dibahas dengan parallel binary search :3

Jika sudah tau disjoint set, maka solusi O(M log M) per query cukup trivial. Kita bisa binary search jawabannya, dan lakukan penggabungan dalam O(M) menggunakan disjoint set. Kemudian, cek keterhubungan bisa O(1). Cuma, pasti TLE. Bagaimana mengakalinya?

Sebenarnya, apa perlu kita ngelakuin semua itu untuk tiap pertanyaan masing-masing sekali? Apa nggak bisa kita ngelakuin semuanya bersamaan? Jawabannya: Bisa!

Ide utamanya, untuk tiap pertanyaan kita simpen low dan high dari binary searchnya. Kemudian, kita buat O(M) vector untuk menyimpan proses. Jadi, misalnya:
  • Query ke-1 memiliki low = 2, high = 5, mid = 3
  • Query ke-2 memiliki low = 3, high = 10, mid = 6
  • Query ke-3 memiliki low = 3, high = 4, mid = 3
Maka, isi vectornya:
  • vector[3] berisi {1,3}
  • vector[6] berisi {2}
Jadi, tiap isi vector[x] menyatakan query-query yang memiliki nilai mid senilai x. Nah, selanjutnya bagaimana?

Binary search akan berhenti ketika low == high. Itu akan diterapkan di sini. Kurang lebih, algonya:
  1. Cek apakah low == high untuk semua query
  2. Jika iya, berhenti. 
  3. Jika tidak, ke langkah 4
  4. Lakukan loop untuk "mengulang" semua proses update dari awal
  5. Ketika di proses ke-i, cek untuk tiap isi vector[i]
  6. Update low dan high untuk setiap isi vector[i], sekalian masukkan ke tempat barunya jika low < high
  7. Kembali ke langkah 1
Aneh? emang. 

Untuk mempermudah, kita bisa kembali ke soal tadi. Pertama, kita tahu untuk update dan mengecek keterhubungan, kita bisa menggunakan disjoint set. Selanjutnya, kita tinggal mengimplementasikan algo di atas. Contoh solusi:

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

vector<int> proc[N];
int lo[N], hi[N], pos[N];
int pset[N];
int n,m,ask;

int tipe[N], a[N], b[N];

// inisialisasi disjoint set
void reset() {
  for(int i = 1 ; i <= n ; i++)
    pset[i] = i;
}

// cari root disjoint set
int finds(int x) {
  return x == pset[x] ? x : pset[x] = finds(pset[x]);
}

// menggabungkan disjoint set
void join(int u,int v) {
  u = finds(u); v = finds(v);
  pset[u] = v;
}

// baca input
void read() {
  scanf("%d %d",&n,&m);
  for(int i = 1 ; i <= m ; i++)
    scanf("%d %d %d",tipe + i,a + i,b + i);
}

// jawab-jawabin query
void solve() {
  ask = 0;
  // inisialisasi low dan high
  for(int i = 1 ; i <= m ; i++)
    if(tipe[i] == 2) {
      lo[ask] = 1;
      hi[ask] = i + 1;
      pos[ask] = i;

      proc[(i + 2) / 2].push_back(ask);
      ask++;
    }

  bool change = 1;
  // O(log M)
  while(change) {
    change = 0;
    reset();

    // O(M)
    for(int i = 1 ; i <= m ; i++) {
      // O(1)
      if(tipe[i] == 1) join(a[i],b[i]);

      // proses semua query yang mid-nya sekarang di i
      while(!proc[i].empty()) {
        int posisi = proc[i].back();
        int idx = pos[posisi];
        proc[i].pop_back();

        int u = a[idx];
        int v = b[idx];

        // O(1)
        if(finds(u) == finds(v)) {
          hi[posisi] = i;
        }
        else {
          lo[posisi] = i+1;
        }

        // masih ada yang belum selesai
        if(lo[posisi] < hi[posisi]) {
          proc[(lo[posisi] + hi[posisi]) / 2].push_back(posisi);
          change = 1;
        }
      }
    }
  }

  // output semua jawaban
  for(int i = 0 ; i < ask ; i++) {
    int ret = -1;
    if(lo[i] <= pos[i]) ret = lo[i];
    printf("%d\n",ret);
  } 
}

int main() {
  int t; scanf("%d",&t);
  for(int tc = 1 ; tc <= t ; tc++) {
    read();
    solve();
  }
  return 0;
}

Kompleksitasnya bisa dilihat dari atas. Kita hitung per-update dan query:
  • Update: Ada O(log M) phase, dan tiap phase ada O(M) update yang masing-masing O(1). Total: O(M log M)
  • Query: Ada O(log M) phase, dan tiap phase ada O(M) query yang masing-masing O(1). Total: O(M log M)
  • Totalnya: O(M log M)
Cukup buat AC.

Nah, tapi kalo gitu doang kan kurang berasa. Makanya, kita lanjut ke soal yang bikin saya kenal strategi ini, SPOJ - METEORS

(Males jelasin soalnya, baca sendiri ya)

Jadi, untuk update, kan dibutuhkan range update. Sebenarnya, bisa pakai BIT yang range update point query. Nah, itu juga bisa dibuat pakai segment tree? Nah, kenapa saya sebut segment tree?

Salah satu strategi yang bisa dipakai adalah persistent segment tree. Kalau gak tahu, persistent segment tree itu segment tree yang nyimpen banyak versi selama dia di-update, hanya dengan tambahan O(log N) memory. Total memory yang dia butuhkan adalah O(N log N).

Nah, aplikasinya gimana? Kita bisa bikin dulu persistent segment tree-nya, terus untuk mencari tau pendapatan di suatu waktu bisa O(banyak_sector * log(M)), dengan nge-query di segment tree versi kesekian.

Cuma, katanya solusi ini MLE.
Nah, di sini kita bisa ngeliat "power" dari parallel binary search: Dia bisa ngegantiin persistent segment tree untuk kasus ini! Lebih tepatnya, dari segi memory. Persistent segment tree membutuhkan O(N log N) memory untuk N versi dan data. Sedangkan, dalam menjalankan parallel binary search, yang dibutuhkan hanya O(N) memory!

Jadi, kita bisa menyelesaikan soal METEORS dengan parallel binary search. Update-nya cukup menggunakan BIT, dan query-nya tinggal panggil query di BIT. Analisis kompleksitasnya?
  • Ingat, ada O(log K) phase, karena binary search dimulai dengan low = 1 dan high = k atau k+1 untuk mempermudah
  • Update: Tiap phase, ada O(K) operasi, masing-masing O(log M). Total untuk update: O(K log M log K) 
  • Query: Total, ada M sector yang dihitung nilainya (total dari N state). Untuk satu sector, mengecek nilainya O(log M) karena BIT. Total untuk query: O(M log M log K)
  • Sehingga, totalnya O((M + K) log M log K)
Cukup untuk mendapatkan AC. Saya menyarankan mengerjakan soal ini karena memang bagus. Namun, in case stres, contoh solusi bisa dilihat di sini

Soalnya memang gak banyak, soal yang bisa dipakai latihan:

Connecting Graph (dibahas di post ini)
SPOJ - METEORS (dibahas di post ini)
CF - Sign on Fence

Sekian dulu ya :v

Kamis, 26 Mei 2016

Untitled

Harapan semester ini:
Jadi juri OSN -> unable to go because of a certain fvcked up module.
Magang -> suppose I get internship, there's almost no one free to take care P4 onsite.

Currently I can't even enjoy my life.
What does it mean to be happy anyway?