Selesai pembukaan langsung ke caltek pekanbaru. Saat sampai, ada briefing tentang sistemnya oleh Bu Inge dan Pak Adi, a.k.a Pak dan Bu Dengklek. Dilanjutkan penyampaian teknis oleh Kak Ayaz. sebenarnya, kita sudah punya slidenya dari sabtu tapi Kak Ayaz bacainnya lucu jadi aku dengerin lagi.
Setelah itu menuju ruangan. Kami dikasi loker pribadi dan untuk masuk ke ruangan harus pakai sendal khusus. Aku duduk diantara Hocky dan Yolanda. Practice session bertujuan untuk untuk menguji lingukangan kontes seperti kecepatan komputer, dan keyboard. Aku memasang target:
"pokoknya aku uji kasus besar"
"pokoknya aku harus uji unordered_map"
"pokoknya harus terbiasa dengan keyboardnya"
"pokoknya aku harus uji unordered_map"
"pokoknya harus terbiasa dengan keyboardnya"
*catatan: bagian ini mengandung istilah komputer. apabila kurang paham bisa langsung melompati sampai bagian foto
Ada 4 soal:
A. hello world (soal bonus)
B. batik riau (adhoc)
C. bermain sudut (STL :v)
D. memindahkan berkas (brute force)
Aku baca soal A, maunya sih gak ku ACkan :v. yaudah baca B. Jelas ini adhoc yaudah langsung dikerjain dan 100. baca C, aku mikirnya pake jarvis algorithm. kucoba gamenya dan bener, koding, eh 30. Baru sadar ini pada dasarnya ngurutin elemen.
Jadi, ada array {2,3,4,...,n} trus kita coba bandingin 2 elemen, sebut saja (b c). Misal (1,b,c) berlawanan arah maka (1,c,b) pasti searah jadi tinggak tuker aja posisi c,b. Kaya ngurutin elemen deh. Yaudah, sort(a,a+n,comp) dengan fungsi comparator:
bool comp(int a, int b) //misalnya tanya(a,b,c) fungsi yang nanyain a,b,c
return tanya(1,a,b)=="SEARAH";
kusubmit jelaslah ac :v (trollface)
Waktuku tinggal 2 jam dan soal tinggal 1. Output only, jijk. Aku coba koding pake cara aneh tapi subtask pertama pun gak tembus. Selama 2 jam aku coba optimisasi algo anehku tapi gagal terus. Aku iseng liat waktu dan wah lagi 4 menit. secepat kilat koding soal A dan AC.
selesai kontes, scoreku 300. Tama dapet 400, fullscore. Jadi, hari ini Tama jadi pusat perhatian. Soal D tadi ternyata brute force doang -_-. karena kesel kulampiaskan di open OSN dapet 100 :v. oh iya, targetku gaada yang tercapai gara gara ngerjain soal D itu -_-.
Selesai kontes ada briefing lagi buat besok. Katanya, jam 7.30 udah disini. Lalu kita balik deh ke hotel. Waktu sampai hotel panitia bilang besok kita bakal berangkat jam 7.30 (eh?).
Malemnya aku coba kerjain soal sparing jakarta vs jateng dengan bantuan Kak Steven Wijaya. Dilanjutkan nonton anime karena tiada hari tanpa anime. Setelah puas, akutidur lebih awal. Seperti biasa, temen sekamarku begadang. Sepertinya, matanya sudah terlatih menerima radiasi komputer dalam keadaan gelap gulita.
Hari pertama kontes
Pagi ini ada kesalahan fatal, celana sekolahku ketinggalan! kronologisnya ibuku bilang celana sekolahku robek dan diminta ganti. Aku lupa ambil celananya yang sudah dijahit -_-". Yaudah, aku pake jeans dan dibawah sudah dimarah panitia. Aku coba pinjem celana Tama, resletingnya rusak. Pinjem celananya Ramben, gak muat. Akhirnya, aku sukses minjem celana Rachman dari Riau yang muat!
Sampai di caltek sudah disambut oleh Pak Julio dan Pak Rully. Aku sempet meditasi sebelum kontes dan akhirnya kontes pun dimulai.
kontes dimulai
Baca A, kok deskripsinya mirip soal pertahanan yogya (OSN 2015) ya... ada Sd dan Sm. Aku bahkan sempet ngira ini copas pertahanan yogya. Ternyata enggak, sebelum liat constraintsnya aku mikir ini jelas DP. Lanjut baca B. Belom kepikiran apa-apa, lanjut C. Mikirnya DFS + backtrack, akan sukses kalau berhasil ngunjungin semua petak. ok, saatnya mengerjakan!
kontes dimulai
Aku menerapkan strategi baca semua soal dulu; siapa tau aja ada yang butuh "perhatian lebih" (uhuk, output only).
setelah puas membaca semua soal dan membuat ide awal kira kira tagsnya apaan, aku menyimpulkan:
A - Pertahanan pekanbaru (struktur data, greedy)
B - Tukar hadiah (DP)
C - Daratan dan es (hanya juri yang tau)
Ngerjain A dulu, ternyata constraint n<=300000. Tapi, Kepikiran ini ternyata mirip soal fidged spinner waktu simulasi yaudah orak-orek dulu lalu mulai ngoding, WA Ternyata ada operasi kebalik, dan AC! Wah, aku orang kedua yang mengackan soal ini setelah Salman! Aku jadi punya waktu 4 jam 30 menit untuk 2 soal.
 |
| komentator OSN |
Coba baca B lagi deh, aku buat program iseng pake map dan dapet 17 :v. Subtask 1 dan 3 bener, subtask 2 salah. Karena masih gak dapet feeling soalnya, aku lanjut C!
baca C, kayaknya sampe subtask 6 bisa deh (pasti ada 1 baris isi semua). Mulai ngoding tapi kok ada yang aneh ya. Kaya input juri gak sesuai gitu. Aku sudah menangin gamenya dan aku coba assert ke kiri dan cek posisi tetapi kok salah -_-. Disinilah semuanya mulai memanas.
Aku fokus benerin bug ini selama 3 jam! Kalau program juri salah kok gaada yang protes? Rasanya sediht membayangkan medali melayang dari leherku. Pasrah aku ke toilet. Balik dari toilet aku sadar KESALAHAN TERBODOH yaitu selain label kasus uji dia juga ngasi banyaknya daratan dan aku gak baca itu! jadi saat aku nyetak arah programku membaca banyaknya daratan sebagai posisi selanjutnya. Aduh gobloknya kok bisa gini ya, yaudah kuperbaiki tapi cuma dapet 25. waktu tinggal 90 menit, dan Bku masih 17. Aku B baca lagi
Entah kenapa soal tadi yang keliatannya tidak terpecahkan sama sekali langsung kepikiran cara yang jelas. jadi idenya memasangkan sebuah permen dengan bebek. Misal bebek terkiri yang belom dipasangkan ada di posisi i, dan kita sedang berusaha memasangkan permen ke J, maka di solusi yang optimal, permen ke J akan dipasangkan dengan bebek ke i, atau tidak dipakai sama sekali. ini memberikan solusi dp 3 state (pos, bebek_terakhir, sisa_k) dengan transisi O(1) jadi kompleksitas terburuk O(n^4) (karena k=n^2).
kukoding dan saat aku selesai ngoding timer menunjukkan 1.02.00. jadi aku tunggu lagi 2 menit biar freeze dulu :v.
Submit dan dapet 64 karena MLE. Sadar jawabannya gak gede-gede amat, semua variabel aku ganti shortint; dapet 80! Aku membuka jaketku, mengepalkan tanganku, im back in the game!
Aku mikir solusi untuk 100 itu minimal n^3 karena n=200. Optimisasi gak kepikiran secara instan jadi aku memilih untuk nambah poin di Cku yang 25 karena kupikir lebih aman.
Tiba-tiba Pak Rully dateng dan marahin aku soalnya dudukku miring. Untuk tadi gajadi pake jeans :"v.
Ok ngerjain C lagi. Ternyata algo awalku salah. Aku ngetesnya manual pake tangan jadi memakan waktu lama. Aku baru bener 10 menit sebelum kontes dan cuma dapat 36 padahal targetku sampe subtask 6. Coba-coba benerin tapi karena masukin casenya lama jadi gak keburu. Aku mengakhiri hari pertama ini dengan skor 216
aku tanya-tanya dan ternyata solusi B itu beneran n^4 menurut Igo dengan metode flying table. Aku skeptis bisa dibuat case biar jadi lelet. Yaudahlah nanti aku coba konsul jurinya.
Aku liat scoreboard dan nilaku disana masih 142, wah bisa kejutan nih. Tama nilai akhirnya 150 (yee gedean). Sampai di hotel ada Kak Rey, jadi aku menemuinya untuk menggali informasi penting. Ternyata, ada komentator OSN yaitu Kak Rey dan Kak Ashar; Kadang aku kadang di sebut :)
 |
| terharu :") |
Sampai di kamar aku tidur siang lalu olahraga. Nilaiku saat ini imbang jadi masih ada kemungkinan besok digusur apalagi kalau ada yang AC dan aku ga AC. Aku gak banyak latihan sih, lebih memilih menjaga stamina.
Karena nilaiku bisa dibilang masih 5 besar, jadi secara teoritis performaku besok sama masih emas. Harapanku cuma mudah-mudahan gaada soal geometri, kreatif, atau output only.
TAPI, kalau ada satu soal yang geometri, kreatif dengan format output only, itu bagus. Karena bisa aku skip dengan tenang.
Hari 2 kontes
Sebenernya aku bangun pagi, tapi dikasi baju aku sarapan dulu buat nanya pake baju apa. Ternyata masih seragam dan 6.30 mau berangkat. Saat aku nanya sudah 6.20 jadi selesai sarapan aku memakai jurus terlarang zaman SMP: mandilat (mandi kilat).
Untung busnya ngaret jadi jam 7. Sampai disana caltex lebih santai dari kemaren karena ada waktu lagi sejam sebelum kontes. Waktu jadinya kontes dimajuin 10 menit (jadi 8.20). Sampai di ruangan aku meditasi sampai 10 menit sebelum kontes. lalu minum, lalu meditasi sampai kontes dimulai. Aku duduk disebelahnya Rania dan aura imbanya terasa gitu
Kontes dimulai
Seperti biasa, baca semua soal dulu.
Baca A, dapet observasi kalau optimalnya kurang dari K, maka bisa pilih segment berurutan agar jadi K. trus pasti ada hubungannya sama urutan kalau di sort. baca B, dua buah array boolean array dp yaitu dp[x][y][len] kepikiran. Yaitu, apakah bisa membut prefix string S/T sepanjang len yang berakhir pada posisi (x,y). trus nyarinya bisa pake BFS dari semua titik yang mengandung karakter dari string awal. baca C, gaada ide tapi baunya dp gituloh.
setelah selesai, aku mengkategorikan soal soalnya:
A. Laskar Bebek (greedy, struktur data)
B. Labirin Dengklek (DFS,BFS, dan brute-force(?) )
C. Aritmetika Bebek (hanya juri yang tau)
Selesai baca semua soal muncul perasaan lega karena tampaknya tidak ada geometri ataupun output only :)
Sebenernya aku ngerasa B lebih mudah. Tapi, karena keseringan ngontes aneh rasanya kalau gak ngerjain A duluan :v. yaudah aku kerjain A.
Observasi pertama jelas bahwa waktu untuk mengurutkan suatu segmen adalah panjang segmen tersebut.
Setelah di observasi lebih lanjut, misal i posisinya di array awal dan j posisinya di array terurut. Maka, kita harus sort segment i-j. Jadi, aku cari semua segment tersebut. Selanjutnya, dapat observasi lagi
Misal ada segment i-j dan segmen k-l dan (i<=j). Apabila dia tumpah tindih ((i<=l) dan (j>=k)) maka optimal apabila kita mengurutkan segmen i-max(j, l) daripada i - j dan k - l secara terpisah karena akan ada potongan segment yang dihitung dua kali.
Maka, idenya aku gabungin segmen yang tumpang tindih agar menjadi satu segmen. Lalu, dapatkan vector akhir yang berisi panjang semua segment dari kiri ke kanan.
misal cnt -> banyaknya penukaran yang telah dilakukan
ans -> jawaban (waktu tercepat)
Kita cek setiap elemen pada vector. misal kita ngecek v[i]. apabila v[i] = 1 maka kita tidak perlu mengurutkan karena sudah berada di posisi yang benar. apabila v[i]>1 maka kita perlu mengurutkan segment ini maka tambahkan ans dengan v[i] dan cnt dengan 1
misal cnt<k. maka tinggal pilih segmen-segmen dengan panjang satu untuk menaikkan nilai k.
kalau cnt>k? berarti 2 segmen yang kita urutkan terpisah harus kita gabungkan. Misal, vectornya
2 3 1 3 5 1 1 4
Pada awalnya kita mengurutkan segmen dengan panjang 2,3,3,5,4 secara beruturut turut. Perhatikan bahwa segmen 2 dan 3 di awal awal vector dapat kita urutkan bareng-bareng dengan tambahan waktu 0 yang mengakitbatkan cnt dikurangi 1. Perhatikan juga 5 dan 4 diakhir vektor dapat diurutkan bareng bareng dengan tambahan waktu 2, karena segment panjang 1 tidak diurutkan.
Maka, kita simpan priority_queue yang berisi penambahan waktu minimal saat ini untuk mengurangi cnt. Untuk setiap subarray 1 kita push banyaknya elemen ke pq. Masukkan juga 0 sebanyak banyaknya i, i>1 dimana v[i] dan v[i-1].
Keliatannya simpel? tapi ini algonya banyak bagiannya jadi selama sejam pertama disaat yang lain sedang asik membanting keyboard aku masih asik nulis nulis dikertas. Saat kodinganku rampung, aku cuma dapet 35! Aku buat kesalahan FATAL.
Intinya, aku udah bener baca soalnya, lalu kubaca ulang dan malah menjadi salah baca soalnya. Aku kira segmen yang kita pilih sebelumnya harus TIDAK TERURUT. jadi aku menghabiskan waktu 1 jam untuk mencari solusinya tapi kok berasa unsolveable ya. Aku akhirnya coba jawab subtask K=1 tapi kok malah WA padahal algo sebelumnya ac. Yah, aku sadar kalau aku ternyata salah baca soal dan ide awalku udah bener. Yang bikin 35 ternyata ada BUG KONYOL saat menghitung banyaknya subbarray 1 yaitu lupa reset counter. fix dan dapet... 67.
MLE di tc n=100000. aku liat gaada rekursif sama sekali, mungkin memorynya ada gimana gitu. pindahin semua ke global, submit masih 67. Aku curiga sama map<queue<int>> ku yang dipake untuk nyimpen indeks indeks kemunculan a[i]. Aku pake queue biar keren gituloh iterasi dari depan.
Aku coba ganti jadi vector dan terpaksa iterasi dari belakang yang sangat tidak keren. submit, dan AC
Berkat latihan sih sebenernya jadi instingku bagus makanya langsung ketemu. Coba ini terjadi 6 bulan yang lalu mungkin aku sudah stresss.
Waktu lagi 3 jam. Nyoba kerjain B kepikiran idenya tapi casenya ribet gitu. Gimana kalau suffix dari string S itu prefix string T?. Yaudah skip dulu.
Kerjain C. Observasi youdontsay: Jawabannya pasti <=n.
Kesalahan FATAL lagi. Aku observasi kalau sebuah baris pilihannya cuman ganti keduanya atau ga ganti sama sekali. Jadi, hitung bagian yang membentuk baris arimetika terbanyak lalu kurangi n.
Setelah ngoding sejam dan debug 30 menit karena ribet bro mainin double, aku baru sadar kalau kita cuman bisa ganti elemennya menjadi nilai yang SAMA. Aduh goblognya 90 menit terbuang sia-sia. Aku cabut dari soal C.
Waktu lagi sekitar 90 menit dan Bku masih 0. Aku merasa khawatir lagi. kemaren sudah range emas masa aku harus kalah disini? Akhirnya aku pun mencoba mengerjakan B.
Aku pikirin kasus ribet tadi ternyata gak terlalu ribet. Ternyata rahasianya di array bool toleransi[i] dimana toleransi[i] menyatakan apakah i karakter terakhir string S sama dengan i karakter pertama string T.
Aku merancang algoritmanya di kertas dan ternyata ga seribet yang aku pikir. Untuk kasus dimana stringnya tumpang tindih, misal (i,j) adalah posisi valid dimana bisa mendapat seluruh string T, maka kita cari nilai m terkecil yang memenuhi dp[i][j][m] = true dan toleransi[s.size()-m]=true. Jika ada, kita menemukan jawaban sepanjang t.size() + m.
Untuk kasus dimana stringnya tidak tumpang tindih, kita maka cari semua titik (x,y) dimana dp[x][y][s.size()-1]=true dan cari mana yang terdekat ke titik yang bisa membuat T menggunakan manhattan distance. Misal jarak tersebut adalah d, kita menemukan jawaban yang dengan panjang d + s.size() + t.size()
Ternyata ngodingnya gampang banget! Aku pake banyak fungsi karena terinspirasi kodenya Steven Wijaya saat simulasi. Sekitar setengah jam kodeku sudah rampung. Ajaibnya? gaada bug! Aku cuma ngarep dapet subtask yang n,m<=50 karena ini kodenya bisa n^4 di bagian looping mencari titik (x,y) terdekat karena bisa ada n*m titik dan bisa ada n*m pemilihan titik yang mungkin. Waktu itu timer menunjukkan sekitar 59:00 (kali ini bukan disengaja ya)
Dapet 80!!! Wow diluar dugaan! Lebih kejut lagi saat aku buka submission dan cuman TLE di subtask terakhir TC terakhir! jadi mencoba mencari optimisasi retjeh agar bisa AC mepet.
Dapet observasi daripada looping semua kemungkinan titik mending buat array jarak[n][m] dimana jarak[x][y] adalah jarak terdekat petak(x,y) ke sebuah jawaban. Saat kita ketemu semua titik, jalankan BFS dari titik itu dan catat jaraknya. Apabila jarak sekarang lebih panjang, maka jalan ditelusuri lagi. Aku merasa ini lumayan mempercepat eksekusi.
kusubmit dan AC! walau aku ngerasa haram tapi mungkin bisa di buktikan secara matematis kalau memang seharusnya AC. waktu itu aku udh ga peduli yang penting AC.
Nilaiku saat ini 205. Aku merasa sudah comeback 2x saat freeze. disini lagu ini keputer dikepala sebentar:
Waktu sekitar 50 menit lagi dan tinggal sisa C. Aku memutuskan untuk incer subtask 4 aja. Dapet ide untuk cari elemen yang membentuk baris aritmatika terbesar lalu jawabannya n-itu. Aku memutuskan untuk membuka jaket dan mengepalkan tanganku lagi karena saatnya serius
Coba koding bentar dan WA! debug doublenya, ga ketemu. Buat transformasi matematis agar cuman pake variabel long long untuk memperkecil peluang bug, tetep WA! "santai, aku punya sekitar 40 menit untuk ngerjain ini" kataku.
Tapi, waktu terus berlalu dan aku belum juga mendapat solusinya. Aku mulai berpikir kalau algoku yang salah tetapi tidak menemukan counter case. Aku ngebayangin Salman, dkk pasti bisa lah jawab soal ini.
waktu lagi 10 menit dan open subtask kedua belum terjawab. Karena disana n=5 aku coba aja deh cout<<"5\n"; kalau misalnya WA tinggal cout<<"4\n" dst...
tapi ternyata jawabannya memang 5 yaudah aku dapet lagi 7 poin. Jadi, untuk day 2 ini poinku nambah 107 saat freeze.
Ruangan pun tepuk tangan saat waktu habis. Benar saja, Amnu dan Salman dapat subtask itu dan katanya solusiku salah (tapi ga dikasi counter case). Namun, nilai day 2 ku ini cukup besar. Aku belum menemukan orang lain yang lebih besar selain Amnu dan Salman jadi aku asumsikan aku terbesar ketiga :P.
seperti biasa, skorku saat freeze sangat jelek tetapi meningkat banyak saat freeze.
Total nilai asliku untuk day 1 dan day 2 adalah 438. Rasanya cukup banyak.
Aku mulai menjalankan troll. aku bilang nilaiku cmn nambah 7 dan soal B aku ga baca. Tidak berniat jahat tapi hanya agar orang orang terkejut saat aku dipanggil nanti :v.
Selesai kontes kita makan lalu ke audiotorium untuk mendengarkan sosialisasi. Kita dapet baju hijau dari tokopedia yang harus dipakai. di audiotorium semua kursi sudah dihilangkan jadi duduknya lesehan. Awalnya sosialisasinya menarik, seperti tentang TOKI, pembahasan soal, dan tentang kampus caltex. Tapi, saat sosialisasi tokopedia aku mulai ngantuk karena ada 3 :".
Kita dibagikan flashdisk yang kalau dicolokin laptop, bisa berubah jadi linux! Selain itu, flashdisknya juga bisa di colok ke HP. Tapi, aku gak berani, takutnya HPku jadi linux ._.
Tentunya aku juga dapat kesempatan langka foto-foto dengan beberapa juri.
Lalu mau ada foto seluruh peserta OSN komputer. Kami juga dapat memberikan tanda tangan didepan dan menulis hanya satu kata. Tentunya, aku pilih tempat yang paling tinggi agar tulisanku keliatan jelas dan aku juga nulisnya besar-besar. Mengenai apa yang kutulis, sudah tidak usah diragukan lagi
Observasi pertama jelas bahwa waktu untuk mengurutkan suatu segmen adalah panjang segmen tersebut.
Setelah di observasi lebih lanjut, misal i posisinya di array awal dan j posisinya di array terurut. Maka, kita harus sort segment i-j. Jadi, aku cari semua segment tersebut. Selanjutnya, dapat observasi lagi
Misal ada segment i-j dan segmen k-l dan (i<=j). Apabila dia tumpah tindih ((i<=l) dan (j>=k)) maka optimal apabila kita mengurutkan segmen i-max(j, l) daripada i - j dan k - l secara terpisah karena akan ada potongan segment yang dihitung dua kali.
Maka, idenya aku gabungin segmen yang tumpang tindih agar menjadi satu segmen. Lalu, dapatkan vector akhir yang berisi panjang semua segment dari kiri ke kanan.
misal cnt -> banyaknya penukaran yang telah dilakukan
ans -> jawaban (waktu tercepat)
Kita cek setiap elemen pada vector. misal kita ngecek v[i]. apabila v[i] = 1 maka kita tidak perlu mengurutkan karena sudah berada di posisi yang benar. apabila v[i]>1 maka kita perlu mengurutkan segment ini maka tambahkan ans dengan v[i] dan cnt dengan 1
misal cnt<k. maka tinggal pilih segmen-segmen dengan panjang satu untuk menaikkan nilai k.
kalau cnt>k? berarti 2 segmen yang kita urutkan terpisah harus kita gabungkan. Misal, vectornya
2 3 1 3 5 1 1 4
Pada awalnya kita mengurutkan segmen dengan panjang 2,3,3,5,4 secara beruturut turut. Perhatikan bahwa segmen 2 dan 3 di awal awal vector dapat kita urutkan bareng-bareng dengan tambahan waktu 0 yang mengakitbatkan cnt dikurangi 1. Perhatikan juga 5 dan 4 diakhir vektor dapat diurutkan bareng bareng dengan tambahan waktu 2, karena segment panjang 1 tidak diurutkan.
Maka, kita simpan priority_queue yang berisi penambahan waktu minimal saat ini untuk mengurangi cnt. Untuk setiap subarray 1 kita push banyaknya elemen ke pq. Masukkan juga 0 sebanyak banyaknya i, i>1 dimana v[i] dan v[i-1].
Keliatannya simpel? tapi ini algonya banyak bagiannya jadi selama sejam pertama disaat yang lain sedang asik membanting keyboard aku masih asik nulis nulis dikertas. Saat kodinganku rampung, aku cuma dapet 35! Aku buat kesalahan FATAL.
Intinya, aku udah bener baca soalnya, lalu kubaca ulang dan malah menjadi salah baca soalnya. Aku kira segmen yang kita pilih sebelumnya harus TIDAK TERURUT. jadi aku menghabiskan waktu 1 jam untuk mencari solusinya tapi kok berasa unsolveable ya. Aku akhirnya coba jawab subtask K=1 tapi kok malah WA padahal algo sebelumnya ac. Yah, aku sadar kalau aku ternyata salah baca soal dan ide awalku udah bener. Yang bikin 35 ternyata ada BUG KONYOL saat menghitung banyaknya subbarray 1 yaitu lupa reset counter. fix dan dapet... 67.
MLE di tc n=100000. aku liat gaada rekursif sama sekali, mungkin memorynya ada gimana gitu. pindahin semua ke global, submit masih 67. Aku curiga sama map<queue<int>> ku yang dipake untuk nyimpen indeks indeks kemunculan a[i]. Aku pake queue biar keren gituloh iterasi dari depan.
Aku coba ganti jadi vector dan terpaksa iterasi dari belakang yang sangat tidak keren. submit, dan AC
Berkat latihan sih sebenernya jadi instingku bagus makanya langsung ketemu. Coba ini terjadi 6 bulan yang lalu mungkin aku sudah stresss.
Waktu lagi 3 jam. Nyoba kerjain B kepikiran idenya tapi casenya ribet gitu. Gimana kalau suffix dari string S itu prefix string T?. Yaudah skip dulu.
Kerjain C. Observasi youdontsay: Jawabannya pasti <=n.
Kesalahan FATAL lagi. Aku observasi kalau sebuah baris pilihannya cuman ganti keduanya atau ga ganti sama sekali. Jadi, hitung bagian yang membentuk baris arimetika terbanyak lalu kurangi n.
Setelah ngoding sejam dan debug 30 menit karena ribet bro mainin double, aku baru sadar kalau kita cuman bisa ganti elemennya menjadi nilai yang SAMA. Aduh goblognya 90 menit terbuang sia-sia. Aku cabut dari soal C.
Waktu lagi sekitar 90 menit dan Bku masih 0. Aku merasa khawatir lagi. kemaren sudah range emas masa aku harus kalah disini? Akhirnya aku pun mencoba mengerjakan B.
Aku pikirin kasus ribet tadi ternyata gak terlalu ribet. Ternyata rahasianya di array bool toleransi[i] dimana toleransi[i] menyatakan apakah i karakter terakhir string S sama dengan i karakter pertama string T.
Aku merancang algoritmanya di kertas dan ternyata ga seribet yang aku pikir. Untuk kasus dimana stringnya tumpang tindih, misal (i,j) adalah posisi valid dimana bisa mendapat seluruh string T, maka kita cari nilai m terkecil yang memenuhi dp[i][j][m] = true dan toleransi[s.size()-m]=true. Jika ada, kita menemukan jawaban sepanjang t.size() + m.
Untuk kasus dimana stringnya tidak tumpang tindih, kita maka cari semua titik (x,y) dimana dp[x][y][s.size()-1]=true dan cari mana yang terdekat ke titik yang bisa membuat T menggunakan manhattan distance. Misal jarak tersebut adalah d, kita menemukan jawaban yang dengan panjang d + s.size() + t.size()
Ternyata ngodingnya gampang banget! Aku pake banyak fungsi karena terinspirasi kodenya Steven Wijaya saat simulasi. Sekitar setengah jam kodeku sudah rampung. Ajaibnya? gaada bug! Aku cuma ngarep dapet subtask yang n,m<=50 karena ini kodenya bisa n^4 di bagian looping mencari titik (x,y) terdekat karena bisa ada n*m titik dan bisa ada n*m pemilihan titik yang mungkin. Waktu itu timer menunjukkan sekitar 59:00 (kali ini bukan disengaja ya)
Dapet 80!!! Wow diluar dugaan! Lebih kejut lagi saat aku buka submission dan cuman TLE di subtask terakhir TC terakhir! jadi mencoba mencari optimisasi retjeh agar bisa AC mepet.
Dapet observasi daripada looping semua kemungkinan titik mending buat array jarak[n][m] dimana jarak[x][y] adalah jarak terdekat petak(x,y) ke sebuah jawaban. Saat kita ketemu semua titik, jalankan BFS dari titik itu dan catat jaraknya. Apabila jarak sekarang lebih panjang, maka jalan ditelusuri lagi. Aku merasa ini lumayan mempercepat eksekusi.
kusubmit dan AC! walau aku ngerasa haram tapi mungkin bisa di buktikan secara matematis kalau memang seharusnya AC. waktu itu aku udh ga peduli yang penting AC.
Nilaiku saat ini 205. Aku merasa sudah comeback 2x saat freeze. disini lagu ini keputer dikepala sebentar:
Waktu sekitar 50 menit lagi dan tinggal sisa C. Aku memutuskan untuk incer subtask 4 aja. Dapet ide untuk cari elemen yang membentuk baris aritmatika terbesar lalu jawabannya n-itu. Aku memutuskan untuk membuka jaket dan mengepalkan tanganku lagi karena saatnya serius
Coba koding bentar dan WA! debug doublenya, ga ketemu. Buat transformasi matematis agar cuman pake variabel long long untuk memperkecil peluang bug, tetep WA! "santai, aku punya sekitar 40 menit untuk ngerjain ini" kataku.
Tapi, waktu terus berlalu dan aku belum juga mendapat solusinya. Aku mulai berpikir kalau algoku yang salah tetapi tidak menemukan counter case. Aku ngebayangin Salman, dkk pasti bisa lah jawab soal ini.
waktu lagi 10 menit dan open subtask kedua belum terjawab. Karena disana n=5 aku coba aja deh cout<<"5\n"; kalau misalnya WA tinggal cout<<"4\n" dst...
tapi ternyata jawabannya memang 5 yaudah aku dapet lagi 7 poin. Jadi, untuk day 2 ini poinku nambah 107 saat freeze.
Ruangan pun tepuk tangan saat waktu habis. Benar saja, Amnu dan Salman dapat subtask itu dan katanya solusiku salah (tapi ga dikasi counter case). Namun, nilai day 2 ku ini cukup besar. Aku belum menemukan orang lain yang lebih besar selain Amnu dan Salman jadi aku asumsikan aku terbesar ketiga :P.
seperti biasa, skorku saat freeze sangat jelek tetapi meningkat banyak saat freeze.
 |
| day 1 naik 74, day 2 naik 107 bakal ada kejutan nih saat pengumuman xD |
Total nilai asliku untuk day 1 dan day 2 adalah 438. Rasanya cukup banyak.
Aku mulai menjalankan troll. aku bilang nilaiku cmn nambah 7 dan soal B aku ga baca. Tidak berniat jahat tapi hanya agar orang orang terkejut saat aku dipanggil nanti :v.
Selesai kontes kita makan lalu ke audiotorium untuk mendengarkan sosialisasi. Kita dapet baju hijau dari tokopedia yang harus dipakai. di audiotorium semua kursi sudah dihilangkan jadi duduknya lesehan. Awalnya sosialisasinya menarik, seperti tentang TOKI, pembahasan soal, dan tentang kampus caltex. Tapi, saat sosialisasi tokopedia aku mulai ngantuk karena ada 3 :".
Kita dibagikan flashdisk yang kalau dicolokin laptop, bisa berubah jadi linux! Selain itu, flashdisknya juga bisa di colok ke HP. Tapi, aku gak berani, takutnya HPku jadi linux ._.
Tentunya aku juga dapat kesempatan langka foto-foto dengan beberapa juri.
 |
| kak Ammar, sang one punch man |
 |
| kak Stacia, diterima di MIT tahun ini |
 |
| kak Turfa. |
Lalu mau ada foto seluruh peserta OSN komputer. Kami juga dapat memberikan tanda tangan didepan dan menulis hanya satu kata. Tentunya, aku pilih tempat yang paling tinggi agar tulisanku keliatan jelas dan aku juga nulisnya besar-besar. Mengenai apa yang kutulis, sudah tidak usah diragukan lagi
 |
| ramben nulis pesona mantan. curang ah dua kata. |
 |
| coba cari aku |
Bali maunya foto didepan lagi tapi sayangnya rame jadi kita foto di photobooth dibawah. Di fotoin Hocky
 |
| sang kordinator |
 |
| OSN ke... |
 |
| tradisi |
Kita memiliki banyak kesamaan loh!
-Sama sama alumni SMP 3
-Sama sama MIA 7
-Sama sama mau naik ke kelas 12
-Sama sama cowok
-Sama sama ikut OSN komputer
-Sama sama masuk sekolah Negeri
-Sama sama tinggal di Bali
-Peringkat medalinya sama sama kalau di mod 5 sisanya 3 (foreshadowing)
selesai sudah event utama OSN. Besok adalah rekreasi. jujur aja aku cukup tenang dengan nilaiku. mudah-mudahan cuman aku doang yang ngetroll saat freeze.
Oh iya ada komentator lagi oleh Kak Rey. Sayangnya karena aku baru AC setelah 2 jam jadi aku gabanyak disebut hari ini.
Aku baru nyadar ada optimisasi BFSnya untuk soal B tadi, yang dijamin O(nm). Aku sebenernya pas kontes kepikiran tapi gara-gara soal rompek (OSN 2016) ngerasa ribet padahal ini ga seribet itu. Aku bahkan udah nemu counter case yang kira kira akan membuat program awalku TLE. case:
200 200
aaa....aa
aaa....aa
...
...
aaa....aa
a
a
yah mudah mudahan gaada yang di rejudge ya :(
Malemnya, kita ada rencana mau nonton Spidermen. Batal karena tiket habis. Jangan di spoiler dulu ya!
 |
| Dikanggo nonton di tv hotel |
Bersambung
Comments
Post a Comment