ICPC Regional Singapore 2018

Nggak, aku nggak ke Singapore.

Tadi aku ikutan mirror ICPC Singapore 2018. Nah, kemarin aku gak yakin bisa ikutan apa nggak, soalnya ada yang harus kupelajari terkait TA. Terus Degol sama Inigo ada kuliah. Tapi ya, daftar-daftar aja dulu di Kattis. Oh, bisa bikin nama tim. Aku bikin nama tim cuma biar gak keliatan ikutan aja. Awalnya mau bikin "Your Lonely Tayo Driver" (pun intended) atau "Ching chong Does Not Dream of Bunny Boy Classmate" (entahlah lagi keinget Sakurajima Mail). Tapi, kalo misalnya ada kemungkinan nanti aku ikutan kontes dengan low effort, buat apa aku put effort untuk bikin nama tim. Aku liat layar, oh placeholder kalo gak ada nama timnya itu "(no name)". Aku copas, jadiin nama tim deh.

Post ini bakal bahas soal-soal yang kukerjain pas mirror, sama yang udah ku-upsolve tadi pas maghrib. Soal dibahas sesuai urutan aku ngerjain. Scoreboard mirror bisa dilihat di sini, dan solusi-solusiku bisa dilihat di sini.

Oiya, aku rada late start karena harus presentasi dan tadi dosennya agak molor datangnya :< Iya, aku selama 2 jam pertama ngerjain di kelas, setelah aku presentasi. Terus antara ngerjain A sama D aku gak ngerjain karena lagi belajar terkait TA (gak fokus sih) sama brunch.

B - Hoppers (menit ke-26)

Karena loncatnya 2, artinya semua bakal kekunjungi iff grafnya  bukan bipartite. Itung ada berapa connected component, sama cek di antara connected component itu ada yang nggak bipartite apa nggak. Bisa pake DFS/BFS biasa. Kalo ada yang bukan bipartite, jawabannya banyak_component-1. Kalo nggak ada, banyak_component. O(N + M).

L - Non-Prime Factors (menit ke-28)

Modifikasi sieve, sama loop harmonic aja. Precompute semua jawabannya dalam O(MX log MX) (MX = 2 juta), terus jawab tiap pertanyaan dalam O(1). Jadinya O(Q + MX log MX).

J - Free Food (menit ke-30)

Aslinya karena kecil bisa main loop brute force aja, cuma aku tadi pake prefix sum soalnya ngodingnya gampang juga. O(N + 365) = O(N).

C - SG Coin (menit ke-48)

Hmm, ada cerita blockchain segala. Tapi intinya sih, daripada nyari transaction string, gampangan nyari token, secara dia cuma ditambahin di akhir. Aku selalu set transaction string = "a", terus brute force mau hasil hash-nya berapa, yang merupakan kelipatan 10⁷. Kalo token yang dibutuhin nilainya gak di luar batas, yaudah langsung ambil aja. O(1). Btw, aku salah set nilai maksimum tokennya jadi 10⁷ di solusiku :)) tapi ya tetep nemu solusi sih.

F - Wi Know (menit ke-79)

Misal prev[d] menyatakan indeks terbesar sehingga elemen ke-d dan elemen ke-prev[d] sama. Misal 4 indeks yang mau kita ambil berturut-turut a, b, c, d. Misal kita fix-kan nilai c. Maka, a pasti paling enak pake elemen pertama yang nilainya sama dengan c. Terus, ini bakal ekivalen dengan nyari indeks d, sehingga prev[d] > a, yang nantinya dijadiin b.

Aku pake segment tree yang rada aneh rasanya. Segment tree-nya untuk nyari dari suatu range [1, x], nilai prev yang mana nilai elemennya (A[prev[]]) itu = i, untuk 1 <= i <= x. Ada mainan update berdasarkan prev, terus nyari x minimum, sehingga nilai query(1, x) itu > a. Maaf aku agak gak jelas jelasinnya, rada njelimet emang solusiku :<

Awalnya aku ngoding O(N log² N) (binary search + query segtree), tapi TLE. Jadinya aku modifikasi jadi O(N log N), ilangin binary searchnya. Baru deh AC.

Btw, submission pertamaku buat soal ini gak sengaja masuk ke Kattis lomba aslinya :')) Untuk keadilan bersama, aku submit juga ke mirror-nya supaya dapet penalty :'))

A - Largest Triangle (menit ke-138)

Kayaknya cukup langka aku mau ngerjain geometri, dan itupun cuma karena gatel kenapa ini soal pada AC :<

Aku awalnya ngerjain urut dari titik terkiri bawah. Sort berdasarkan polar angle, terus cobain untuk tiap titik lain, pasangin ke titik sekarang sebagai alas segitiga. Tinggi segitiga harusnya bisa di-ternary search, seandainya kita ngerjainnya urut. Setelah selesai, hapus titik terkiri bawah. Cuma ya.. O(N² log N), dan TLE :<

Habis itu aku ngide, coba daripada ternary search, dibikin macam two-pointer. Gak ngeprove kebenarannya. Disubmit, WA. Habis itu ngide lagi, jawaban harusnya ada di convex hull. Terus two-pointer lagi. Duh, WA. Pas aku bikin tes sembarang, entah kenapa ada keluar digit di belakang komanya 1, padahal harusnya 0 atau 5 (karena titiknya bilangan bulat semua). Lho, lupa dikali 5. Habis dibenerin, submit, AC. Wut. Jadinya O(N²).

Btw, pas aku mulai ngerjain ini aku masih di kelas. Terus aku gerakin tanganku buat ngebayangin alas sama tinggi segitiga. Tapi pas ngelakuin aku jadi kepikiran, itu gerakannya kayak Ultraman.

Pada titik ini, aku belajar terkait TA sama memutuskuan buat brunch, karena udah lapar banget. Habis makan aslinya udah niatin gak lanjutin. Hanya saja, iseng kepikiran sesuatu yang bego di D terus mau nyobain.

D - Bitwise (menit ke-221)

Soal macem ginian pasti hampir selalu iterasi dari bit terbesar ke terkecil, lalu cek bisa gak solusi terbaiknya masukin bit itu. Untuk ngecek apakah X bisa dibentuk di K subarray, aku pake kayak DP tapi lebih kayak greedy. Untuk kemudahan, misal or(l, r) menyatakan bitwise OR dari elemen ke-l sampai ke-r, dan dp(i) adalah pair<int, int> yang mana:

• dp(i) = {0, or(1, i)} apabila X bukan submask dari or(1, i)
• Selain itu, pasti ada l sehingga X submask dari or(l, i). Cari l maksimum, terus dp(i) = {1 + dp(l-1).first, dp(l-1).second)}

Mudahnya, dp(i) menyatakan {banyak subarray max, sisa or}. Selanjutnya, brute force i, sehingga dari i+1..n akan digabung dengan sisa or. Kita bisa itung banyak subarray partisi yang mana X adalah submasknya dengan mudah dalam O(N). X valid kalo banyak subarray partisi >= K.

Nah, masalahnya untuk nyobain bit-nya ada O(log 10⁹) bit. Terus, pas kontes aku nggak kepikiran cara sliding window or selain pake prefix sum per bit. Jadinya, solusi ini kompleksitasnya O(N log² 10⁹). Aku coba kasus sembarang di laptopku, 4 detikan. Liat TL Kattis, hmm 3 detik. Aku coba submit aja. To my surprise (and annoyance), dapet AC dalam 2.2 detik. Setelah kelai sama TL F sama A, tau-tau di sini malah lebih ringan :s Habis chat sama Ammar pasca kontes, katanya emang N diturunin jadi 500.000 di kontesnya. Oh, pantes kepangkas separo.

Anw, tadi kepikiran cara mangkas O(log 10⁹) dari prefix sum. Intinya ganti ke sparse table sih, soalnya kita bisa precompute untuk tiap length, berapa 2 pangkat terbesar yang <= length. Jadinya sekarang ngecek or(l, r) bisa dalam O(1). Silahkan cek D2.cpp kalo masih penasaran.

I - Prolonged Password (menit ke-251)

Phew, untung yang bikin soal baik, panjang string transformasinya di rentang [2, 50]. Untuk soal ini, aku bagi 2 kasus, yang K <= 100 sama K > 100.

Pertama, misal dp(k, char) itu menyatakan panjang string kalo kita transformasi char sebanyak k kali. Ini bisa dalam O(k * |T|) doang. Untuk kemudahan, batasi dp(k, char) dengan nilai yang > 10¹⁵. Misal kita pengen nyari karakter ke-x dari string hasil transformasi char sebanyak k kali. Kita bisa iterasi sebanyak O(|T|), ngecekin karakter ke-x itu munculnya sebenarnya hasil transformasi karakter mana dari T_char dengan memanfaatkan dp tadi. Jadinya, karakter ke-x juga bisa dicari dalam O(k * |T|).

Nah, kenapa tadi aku bagi kasus? Intinya sih:

• Kalo K <= 100 (bukan tight bound), kita harus cek dia itu awalnya transfomasi dari karakter mana di S. Nah, masalahnya |S| <= 10⁶. Kalo kita loop aja, bisa O(|S|) per query, TLE dong. Jadinya.. bikin prefix sum, terus binary search karakternya pake prefix sum. Lanjutnya pake solusi di atas.
• Kalo K > 100, pasti sebenernya itu hasil transformasi dari karakter pertama terus-menerus sampai K = 100 (kasarannya, 2¹⁰⁰ > 10¹⁵), jadi untuk K > 100 pasti karakter ke-x ada dari transformasi karakter pertama secara terus-meneurs. Aku pake semacam sparse table untuk nyari setelah berubah K-100 kali, karakter pertamanya itu jadi apa. Lanjutnya bisa pake solusi di atas.

Keseluruhannya, per query butuh O(100 * |T|), jadi totalnya O(M * 100 * |T|).

Btw, pas ngerjain ini awalnya aku kira K itu dikasih per query juga (jadi beda-beda), terus stres karena prefix sumnya bakal jebol :')

K - Conveyor Belt (menit ke-276)

Aku gak ngerjain soal ini sampe di akhir karena males baca ceritanya (yea, i'm a simple man). Habis baca singkat, intinya ini bisa dimodelin jadi network flow. Untuk kemudahan, ubah semuanya jadi 0-index (nggak ngubah solusi). Misal (i, j) artinya vertex ke-i, pada waktu j dalam modulo K. Bikin graf berikut:

• source ke (i, i) untuk tiap 0 <= i < K, dengan kapasitas 1 (produsen)
• (n-1, i) ke sink untuk tiap 0 <= i < K, dengan kapasitas INF (tujuan)
• (a, i) ke (b, (i+1) mod K) untuk tiap a, b edge di input dan 0 <= i < K dengan kapasitas 1 (edge per satuan waktu modulo K)

Tinggal cari max flow dari graf tersebut. Karena banyak jawaban maksimum K ya.. O(K * BFS) = O(K² M).

Anw, pas chat sama Ammar ternyata ada masalah wording di soal ini.

"These robots can be programmed, but their behavior on each product is deterministic, depending only on the producer which produces the respective product. ".

Ini bisa dipahami kalau untuk tiap produk, di setiap persimpangan gerakannya deterministik, jadi sebenarnya nggak bisa ada cycle (graf yang tadi mungkin ada cycle, cuma waktunya beda). Karena aku bacanya kecepetan, aku nggak nyadar ada kalimat itu. Dan kayaknya emang intended dari pembuat soal nggak kayak gitu. Jadi kasihan sama yang nggak ngerjain gara-gara mikir begitu :<

G - Rectangular City (post-contest)

Kalo gak salah pas kontes aku skip gara-gara salah ngerti soal. Pas nyoba upsolve, salah ngerti lagi :/ Btw, karena samplenya begitu, sekedar mengingatkan bahwa walaupun N event itu bentuknya persegi panjang, K titik yang diambil gak harus ngebentuk persegi panjang (sample nunjukin persegi semua).

Misal intersection dari N event itu kita nyatakan sebagai (r1, r2, c1, c2) dengan r1 <= r2 dan c1 <= c2. Kita akan pandang permasalahan r dan c ini terpisah, karena solusi permasalahan ini bisa dipakai di keduanya.

Sekarang kita fokus untuk r. Ada berapa banyak cara bikin N event, sehingga intersectionnya punya batas row (r1, r2)?

• Ada r1^N - (r1-1)^N cara nentuin batas atas N event supaya batas atas intersectionnya r1. r1^N artinya banyak cara yang intersectionnya <= r1, sedangkan (r1-1)^N yang < r1. Kalo dikurangi jadinya pas di r1 intersectionnya
• Dengan cara serupa, ada (R-r2+1)^N - (R-r2)^N cara nentuin batas bawah N event supaya batas bawah intersectionnya r2.
• Untuk banyak cara (r1, r2), kaliin aja dua nilai itu

Nah, kalo sudah, kita bisa hitung rows[X], yang mana rows[X] menyatakan banyak cara sehingga tinggi intersectionnya X. Tinggal brute force (r1, r2) yang mungkin, terus tambahin banyak caranya ke panjangnya. Dengan cara serupa, hitung cols[Y], dengan patokan (c1, c2).

Selanjutnya, bisa kita lihat kalau rows[X] * cols[Y] menyatakan banyak cara bikin N event yang intersectionnya punya ukuran tepat X * Y. Jawaban yang kita cari itu banyak cara bikin N event yang intersectionnya punya ukuran >= K. Dengan precompute i^N untuk tiap i yang mungkin di awal, kompleksitas solusi ini O(max(R, C) log N + R² + C² + RC).

H - Sliding Blocks (post-contest)

Ini soal lain yang males kubaca :/ Pas kontes aku udah baca dan came up sama suatu solusi, tapi males ngoding. Pas chat sama Ammar ternyata solusinya bener :P

Intinya karena bentuk grafnya tree, kita bisa cari urutan masukin baloknya pake toposort. Bikin edge berdasarkan treenya, terus berdasarkan arah slidenya. Kalo ke atas, artinya kita harus masukin ini duluan sebelum balok terdekat di bawahnya. Kalo ke kiri, artinya harus lebih dulu berdasarkan kanan terdekatnya. Dst, dst.

Solusiku O(B log B) dan lumayan jorok, copas-copas di mana-mana. Oh well, yang penting nggak TLE :P


And that's all!

Aku nggak ngerjain E, dan setelah chat dengan Ammar, untung aku nggak ngerjain. Salah ngerti soal >.> Kayaknya hampir semua tim salah ngerti soal. Kayaknya pengertian soal yang Ammar jelasin (convert -> asterisk check -> convert -> asterisk check dst) lebih doable, cuma aku nggak terlalu minat buat nyobain.

Overall, kayaknya... regional yang ini nggak terlalu susah? Mayoritas soalnya medium. Cukup yakin kalo ngerjain bertiga bareng Degol sama Inigo juga bisa AC 10-11 gitu. Agak sayang ada masalah sama soal D sama K (Donkey Kong?). Tapi ya, kontesnya cukup menarik. Menurutku Soal H sama I lumayan menarik. Terima kasih untuk panitia yang bikin mirror hehe. Semoga kalo ada ICPC Singapore lagi (mungkin beberapa tahun lagi? ada gap 3 tahun dari ICPC Singapore terakhir) bisa lebih keren lagi ^^