Oke, ini bakal sedikit melenceng dari judul. Minggu lalu, selain ikut INC, aku juga ikut penyisihan keamanan jaringan sama pemrograman dari Gemastik. Biasanya, aku ikut lomba-lomba kayak gitu karena:
- Sifatnya objektif
- Fun
Tapi kayaknya Gemastik kemarin benar-benar kebalikannya. Kalo aku harus deskripsikan, pengalamanku kurang lebih "not fun", "annoying", sama "disgusting". Tapi daripada blogpost ini isinya jadi rant, mari kita sudahi membahas Gemastik sampai sini saja.
Oke, buat INC sama ICPC regional nanti, aku bakal ada di tim Supir Tayo sama Degol + Inigo (kayaknya Inigo masih gak tau kenapa aku pengen kasih nama Tayo). Terus walaupun kemaren ada ngomong ke orang-orang kalo aku kemungkinan besar gak ikut regional ke luar, turns out tahun ini ada tetep ke luar setelah beberapa pertimbangan. Tapi akunya juga udah rada bego sih hehe, jadi jangan berekspektasi tinggi :P
Anyway, setelah Gemastik pemrograman yang web-nya down 2 jam (bikin kacau luar biasa), aku jadi nanya FJ perihal INC besoknya, karena tahun lalu INC juga sempat kacau sekitar 1 jam. Responnya lumayan pede, jadinya aku harap gak down bakalan haha.
Oiya, terus malam sebelumnya kan ada IPSC, aku ikutan juga sama Prabowo + Agus. Walaupun jadinya tidur jam 3 pagi, gak sia-sia karena selama sejam ngedenger Agus jadi pelayan Mcd. Terus, ada pembicaraan, terkait pola selama aku ikut INC:
 |
| #2019PilihPrabayar |
Iya, aku emang berekspektasi peringkat 4 atau 5 :P
Untungnya, walaupun baru bisa tidur sekitar jam 4-an, masih bisa bangun buat pergi ke kampus demi INC. Pas nyampe, masih ada waktu sekitar 45 menit, jadi bisa minta tolong buka lab dulu sama siap-siap. Untungnya, gak kayak tiap latihan, Inigo sama Degol bisa datang tepat waktu kali ini :P Sebelum kontes mulai, kesepakatannya Degol baca 1/3 pertama, Inigo 1/3 tengah, aku sisanya, mulai dari soal I.
Omong-omong, soal dapat diakses pada tautan berikut.
Kontes mulai! Pas baca:
I: aih expected value. Tapi kayaknya bisa
J: sort terus greedy harusnya, cuma nggak yakin yang ukuran grupnya gede taruh di depan atau belakang, sama gak yakin begitu optimal apa nggak
K: notasi matematis. skip dulu
L: terlihat panjang, skip
M: terlihat pendek, macem TSP tapi ada properti anehnya. Kayaknya greedy tapi ngerepotin
WTF ini soalnya aneh semua.
Degol bilang dia mulai ngoding A. Terus aku masih ngoret-ngoret I dulu dikit. Udah dapat sekilas, aku baru mulai ngerjain J. Pas liat di scoreboard udah ada yang AC J, jadi yakin kalo solusinya harusnya greedy yang gampang. Karena gak tahu yang optimal yang mana, yaudah.. aku cobain aja dua-duanya :P Submit, J - A Study on Groups AC. Beberapa menit sebelumnya, ternyata Degol udah AC A - Tour de BINUS sama D - Substring Permutation.
Inigo bilang dia ngerjain F. Terus, aku sama Degol ngeliat scoreboard. Yang lumayan rame E sama H. Degol terus ngerjain E, sementara aku ngerjain H. Yang H pas dibaca kayaknya bisa DP Digit -- state-nya [indeks][angka non zero terakhir][udah kurang dari boundnya belom]. Habis ngoding yang ngebug-ngebug, H - Plate Parity AC.
Inigo sama Degol masih ngoding, terus aku sekilas baca soal B. Kayaknya malesin, aku jadinya ngerjain I. Pas baca soalnya lagi, ternyata tadi aku salah ngerti soal. Kukira awalnya yang dihapus itu indeks-indeks yang A[i]-nya habis dibagi P[j], bukannya i habis dibagi P[j] :"( Habis itu aku ngoret-ngoret lagi. Intinya mau nyari fungsi f(K), yaitu berapa kali suatu bilangan muncul pada sekuens X, apabila ada K bilangan di [1, N] yang habis membagi indeks tempat bilangan itu. Dengan sedikit kombinatorik, nilai f(K) bisa dihitung dalam O(N). Selanjutnya, pembilang dari expected value-nya kan pasti jumlahan f(banyak_pembagi_i) * A[i]. Nah, tapi O(N2). Bisa dipercepat dengan memanfaatkan fakta banyaknya pembagi berbeda itu dikit, sekitar 100 lah kasarannya. Jadinya semacam O(N * sesuatu). Seperti biasa, ngebug-ngebug dulu. Habis bener, submit, I - Expected Value of a Permutation AC.
Habis itu, aku ngecek Degol sama Inigo. Degol E ngebug, Inigo F belum selesai. Aku jadinya minta Degol jelasin soal E ke aku, biar nantinya aku takeover sama dia bisa bantu Inigo. Setelah dijelasin soal dan dikasih beberapa observasi penting, aku ngoding E. Ngebug juga yey. Ada masalah dengan state untuk ngitung buat sekuens good. Habis bener-benerin lagi, E - The Good, the Great, and the Superb AC. Pas ngerjain, gak sengaja denger Degol ada ngomong Hopcroft-Karp ke Inigo, kayaknya soal F ada matching-nya.
Habis itu aku nanya ada yang bisa dikerjain apa nggak, terus Degol jelasin soal C. Intinya dikasih tree yang per verteks-nya ada nilai, katakanlah A[i]. Terus ada Q query, untuk suatu path, itung banyak verteks yang memenuhi L <= A[i] <= R. Oke, ini harusnya bisa dikerjain secara offline pake BIT sama LCA. Intinya, pisah query jadi 3 bagian, yaitu di kedua ujung path, sama di LCA-nya. Lakukan DFS, pelihara BIT yang isinya data dari root hingga ke node sekarang. Kalo di LCA, artinya kurangi dengan 2 kalinya, tapi kalo di ujung path artinya tambah. Terus ada main coordinate compression juga. Capek sih, tapi yaudahlah, coding aja.
Habis ngoding yang tentunya ngebug lagi, aku cek sample-nya. Lho, ini kok angkanya gede. Lho, ternyata diminta jumlahan A[i]-nya, bukan cuma banyaknya yang memenuhi. Untung modifikasinya gak susah. Tapi ya ngebug lagi. Benerin, submit, WA. Oh, query BIT-nya masih pake int, harusnya long long (aku nggak suka pakai long long kecuali emang perlu). Submit lagi, C - Hierarchical Architecture AC. Pas AC, beberapa saat sebelumnya juga ternyata F - KMP AC. Kalo gak salah ini ngelempar kami yang sebelumnya posisinya sekitaran 5~10an jadi top 5. Padahal pas di awal-awal masih 15~20an terus hehe.
Habis itu, seperti biasa:
Ayaz: "Ada lagi gak yang bisa gw kerjain?"
Degol: "Ini Yaz ada soal G. Tenang ini kayak geometri tapi bukan geometri."
Intinya dikasih beberapa titik, mau bikin mereka titik pusat lingkaran, dengan syarat untuk 2 lingkaran, yang satu berada di dalam yang lainnya.
Degol: "Gw bisa N faktorialnya"
Ayaz: "Nice info gan"
Tapi aku sendiri lupa sih approach-nya Degol gimana hehe :") Habis mikir sejenak, aku kepikiran kalau:
Habis itu, aku ngecek Degol sama Inigo. Degol E ngebug, Inigo F belum selesai. Aku jadinya minta Degol jelasin soal E ke aku, biar nantinya aku takeover sama dia bisa bantu Inigo. Setelah dijelasin soal dan dikasih beberapa observasi penting, aku ngoding E. Ngebug juga yey. Ada masalah dengan state untuk ngitung buat sekuens good. Habis bener-benerin lagi, E - The Good, the Great, and the Superb AC. Pas ngerjain, gak sengaja denger Degol ada ngomong Hopcroft-Karp ke Inigo, kayaknya soal F ada matching-nya.
Habis itu aku nanya ada yang bisa dikerjain apa nggak, terus Degol jelasin soal C. Intinya dikasih tree yang per verteks-nya ada nilai, katakanlah A[i]. Terus ada Q query, untuk suatu path, itung banyak verteks yang memenuhi L <= A[i] <= R. Oke, ini harusnya bisa dikerjain secara offline pake BIT sama LCA. Intinya, pisah query jadi 3 bagian, yaitu di kedua ujung path, sama di LCA-nya. Lakukan DFS, pelihara BIT yang isinya data dari root hingga ke node sekarang. Kalo di LCA, artinya kurangi dengan 2 kalinya, tapi kalo di ujung path artinya tambah. Terus ada main coordinate compression juga. Capek sih, tapi yaudahlah, coding aja.
Habis ngoding yang tentunya ngebug lagi, aku cek sample-nya. Lho, ini kok angkanya gede. Lho, ternyata diminta jumlahan A[i]-nya, bukan cuma banyaknya yang memenuhi. Untung modifikasinya gak susah. Tapi ya ngebug lagi. Benerin, submit, WA. Oh, query BIT-nya masih pake int, harusnya long long (aku nggak suka pakai long long kecuali emang perlu). Submit lagi, C - Hierarchical Architecture AC. Pas AC, beberapa saat sebelumnya juga ternyata F - KMP AC. Kalo gak salah ini ngelempar kami yang sebelumnya posisinya sekitaran 5~10an jadi top 5. Padahal pas di awal-awal masih 15~20an terus hehe.
Habis itu, seperti biasa:
Ayaz: "Ada lagi gak yang bisa gw kerjain?"
Degol: "Ini Yaz ada soal G. Tenang ini kayak geometri tapi bukan geometri."
Intinya dikasih beberapa titik, mau bikin mereka titik pusat lingkaran, dengan syarat untuk 2 lingkaran, yang satu berada di dalam yang lainnya.
Degol: "Gw bisa N faktorialnya"
Ayaz: "Nice info gan"
Tapi aku sendiri lupa sih approach-nya Degol gimana hehe :") Habis mikir sejenak, aku kepikiran kalau:
- Kalau B tepat di dalam A, harusnya lingkaran A berimpit di B di beberapa bagiannya
- Asumsikan C lingkaran terkecil dalam suatu himpunan (radius 0), terus mau masukin D ke dalam himpunan sebagai lingkaran terkecil. Pasti C radiusnya nambah sebanyak jaraknya ke D. Karena observasi sebelumnya, kalau B lingkaran terkecil yang lebih besar dari C, pasti B radiusnya nambah sebanyak ini juga demi menampung C. Dst, intinya semua dalam himpunan radiusnya nambah sesuai jarak C ke D.
Kalau benar, artinya solusinya bisa pakai DP Bitmask dengan state [lingkaran terkecil][bitmask]. Kompleksitasnya O(N22N). Yaudah aku coba coding aja. Entah kenapa rasanya awkward ngoding DP dengan nilai floating-point, terus aku jadinya pake variabel boolean buat nandain suatu state udah diitung apa nggak. Submit, yey G - Discs AC. Kalau gak salah ini ngelempar kami ke peringkat 1 pas itu.
Habis itu, aku bilang ke Degol sama Inigo kalo kayaknya mereka bisa ngerjain soal M. Habis aku jelasin soalnya, mereka ngerjain soal itu. Sementara itu, aku mikir soal B. Kayaknya bisa pake BBST, tapi gak suka, males ngodingnya. Terus kepikiran semacam Sqrt decomposition. Intinya bagi list-nya jadi blok-blok berukuran K (bloknya pake vector). Simpen tiap angka ada di blok mana. Untuk dapetin pergeserannya kan bisa didapat dari selisih indeksnya, jadi sekarang mikir cara dapet indeksnya. Untuk dapetin indeks, bisa aja loop O(N / K + K), iterasi tiap blok yang indeksnya kurang dari indeks bloknya, terus iterasi dalam bloknya itu sendiri. Untuk update, yaudah geser secara naif aja. Nah, kalo udah K kali update, bikin ulang blok-bloknya. Jadinya kompleksitasnya bakalan semacam O(Q(K + N / K)). Biasanya bagusnya K = sqrt(N), cuma aku malas, jadinya aku pasang K = 400. Terus aku nyoba-nyoba beberapa hal, ternyata percobaanku cacat, jadi buang waktu sekitar 10 menitan. Habis yakin, submit. Beberapa saat kemudian, B - Linked List AC.
Inigo sama Degol masih ngomongin kasus-kasus soal M. Aku dengerin sekilas entah kenapa rasanya serem. Karena sisa K, L, M aku jadinya harus baca sendiri, secara itu tanggung jawabku semua harusnya :"D Aku jadinya baca L, karena itu aja yang aku masih bener-bener buta. Habis baca, intinya gampang, cuma bikin turnamen rigged.
Awalnya kepikiran DP bitmask, cuma gak yakin muat apa nggak. Habis itung-itungan, kayaknya muat. Aku ngebikin semua transisinya dulu di awal, nyoba optimasi aja. Habis itu, ngoding DP-nya gak terlalu susah. Sample bener, submit, WA. Baru habis itu nyadar, oiya harus nyimpen di suatu subtree yang menang siapa. Jadinya state-nya dari [bitmask] jadi [siapa yang menang][bitmask]. Ngoding lagi, ngebug lagi, debug lagi. Submit, WA lagi. Sial, ternyata di prekomputasinya ada yang lupa dibalikin karena tadi lagi ngecek buat nilai N kecil :" Habis dibenerin, L - Fair Tournament AC. Yang bikin kaget, ternyata kami gak first solve soal L. Padahal di atas-atas belom ada yang AC. Habis scroll ke bawah, ternyata ada tim yang udah AC :/ Aneh, jadi keinget ICPC Nakhon Pathom tahun lalu.
Degol sama Inigo udah submit M, tapi kayaknya ada kasus yang kelewat. Degol mencoba debug, sementara aku sama Inigo mencoba memahami K. Setelah diskusi, konklusinya di soal ini mencoba cari cycle terkecil di suatu graf. Dari batasan, O(NM) kan nggak bisa. Terus pake properti DFS spanning tree juga gak bisa, bisa aja loncat-loncat back edge. Tapi karena nekat, aku coba submit dulu O(NM) pake BFS, dengan semua komponen tree di-skip. Cuma ya TLE.
Karena N, M <= 20000, aku pikir kayaknya ini bakal perlu bitset-bitset-an. Terus hasil oret-oret kayaknya bisa pake BFS, simpen semua ancestor di BFS tree. Sayangnya, setelah ngoding dan WA-WA, baru ketemu kasus yang gagal. Jadinya pusing. Terus Degol juga M terus berhasil menemukan kasus baru, tapi masih WA-WA. Sampai beberapa menit terakhir, kami masih belum nemu titik terang untuk soal manapun. Sampai beberapa menit terakhir, kami rank 1 dengan AC 11, terus rank 2 AC 11 juga.
Di 5 menit terakhir, aku buka minesweeper sambil berharap yang rank 2 gak nambah. Berapa detik kemudian aku tutup, karena dapetnya naas melulu minesweeper-nya (klik pertama bentuk kotak). Was-was, pas 300 menit lewat masih rank 1. Ternyata habis beberapa menit kemudian, ada submisi soal K dari Kth-D Hyperprism yang AC xD jadinya kami kegusur ke rank 2 di menit terakhir.
Tbh, I am not even mad. I was really amused xD
Jadi karena kurang nekat, kami kegusur ke rank 2. Seenggaknya nggak seperti perkiraanku bakal rank 4 atau 5 :P Scoreboard akhir, sampai rank 10:
Masih banyak yang harus dibenahi sampai regional Jakarta nanti, tapi kurasa yang sekarang Supir Tayo gak buruk-buruk amat.
Yaudah deh, kurasa sampai ini saja dulu. Sampai bertemu di Binus bulan november nanti :D
Notes:
Habis itu, aku bilang ke Degol sama Inigo kalo kayaknya mereka bisa ngerjain soal M. Habis aku jelasin soalnya, mereka ngerjain soal itu. Sementara itu, aku mikir soal B. Kayaknya bisa pake BBST, tapi gak suka, males ngodingnya. Terus kepikiran semacam Sqrt decomposition. Intinya bagi list-nya jadi blok-blok berukuran K (bloknya pake vector). Simpen tiap angka ada di blok mana. Untuk dapetin pergeserannya kan bisa didapat dari selisih indeksnya, jadi sekarang mikir cara dapet indeksnya. Untuk dapetin indeks, bisa aja loop O(N / K + K), iterasi tiap blok yang indeksnya kurang dari indeks bloknya, terus iterasi dalam bloknya itu sendiri. Untuk update, yaudah geser secara naif aja. Nah, kalo udah K kali update, bikin ulang blok-bloknya. Jadinya kompleksitasnya bakalan semacam O(Q(K + N / K)). Biasanya bagusnya K = sqrt(N), cuma aku malas, jadinya aku pasang K = 400. Terus aku nyoba-nyoba beberapa hal, ternyata percobaanku cacat, jadi buang waktu sekitar 10 menitan. Habis yakin, submit. Beberapa saat kemudian, B - Linked List AC.
Inigo sama Degol masih ngomongin kasus-kasus soal M. Aku dengerin sekilas entah kenapa rasanya serem. Karena sisa K, L, M aku jadinya harus baca sendiri, secara itu tanggung jawabku semua harusnya :"D Aku jadinya baca L, karena itu aja yang aku masih bener-bener buta. Habis baca, intinya gampang, cuma bikin turnamen rigged.
Awalnya kepikiran DP bitmask, cuma gak yakin muat apa nggak. Habis itung-itungan, kayaknya muat. Aku ngebikin semua transisinya dulu di awal, nyoba optimasi aja. Habis itu, ngoding DP-nya gak terlalu susah. Sample bener, submit, WA. Baru habis itu nyadar, oiya harus nyimpen di suatu subtree yang menang siapa. Jadinya state-nya dari [bitmask] jadi [siapa yang menang][bitmask]. Ngoding lagi, ngebug lagi, debug lagi. Submit, WA lagi. Sial, ternyata di prekomputasinya ada yang lupa dibalikin karena tadi lagi ngecek buat nilai N kecil :" Habis dibenerin, L - Fair Tournament AC. Yang bikin kaget, ternyata kami gak first solve soal L. Padahal di atas-atas belom ada yang AC. Habis scroll ke bawah, ternyata ada tim yang udah AC :/ Aneh, jadi keinget ICPC Nakhon Pathom tahun lalu.
Degol sama Inigo udah submit M, tapi kayaknya ada kasus yang kelewat. Degol mencoba debug, sementara aku sama Inigo mencoba memahami K. Setelah diskusi, konklusinya di soal ini mencoba cari cycle terkecil di suatu graf. Dari batasan, O(NM) kan nggak bisa. Terus pake properti DFS spanning tree juga gak bisa, bisa aja loncat-loncat back edge. Tapi karena nekat, aku coba submit dulu O(NM) pake BFS, dengan semua komponen tree di-skip. Cuma ya TLE.
Karena N, M <= 20000, aku pikir kayaknya ini bakal perlu bitset-bitset-an. Terus hasil oret-oret kayaknya bisa pake BFS, simpen semua ancestor di BFS tree. Sayangnya, setelah ngoding dan WA-WA, baru ketemu kasus yang gagal. Jadinya pusing. Terus Degol juga M terus berhasil menemukan kasus baru, tapi masih WA-WA. Sampai beberapa menit terakhir, kami masih belum nemu titik terang untuk soal manapun. Sampai beberapa menit terakhir, kami rank 1 dengan AC 11, terus rank 2 AC 11 juga.
Di 5 menit terakhir, aku buka minesweeper sambil berharap yang rank 2 gak nambah. Berapa detik kemudian aku tutup, karena dapetnya naas melulu minesweeper-nya (klik pertama bentuk kotak). Was-was, pas 300 menit lewat masih rank 1. Ternyata habis beberapa menit kemudian, ada submisi soal K dari Kth-D Hyperprism yang AC xD jadinya kami kegusur ke rank 2 di menit terakhir.
Tbh, I am not even mad. I was really amused xD
Jadi karena kurang nekat, kami kegusur ke rank 2. Seenggaknya nggak seperti perkiraanku bakal rank 4 atau 5 :P Scoreboard akhir, sampai rank 10:
 |
| Supir yang bisa ngoding |
Masih banyak yang harus dibenahi sampai regional Jakarta nanti, tapi kurasa yang sekarang Supir Tayo gak buruk-buruk amat.
Yaudah deh, kurasa sampai ini saja dulu. Sampai bertemu di Binus bulan november nanti :D
Notes:
- Solusi yang aku coding bisa dilihat di tautan berikut
- Solusi M Degol udah 400 baris, masih WA :"")))
- Kayaknya salah satu kontes terbaik yang aku ikuti tahun ini :D Problemset menarik dan lumayan seimbang. Terus nggak down sama soalnya juga jelas
0 komentar:
Posting Komentar