Skip to main content

Pengalamanku Ikut BNPCHS 2017

Sekitar 3 minggu yang lalu, aku ngikutin BNPCHS. tulisan ini tertunda lama karena aku malas xD.
BNPCHS itu singkatan dari Bina Nusantara Programming Contest for High-School Students. Menyamai singkatan lomba terpanjang yang pernah aku kerjain yaitu AJHSME saat SMP. (The American Junior High School Mathematics Examination).

Penyisihan BNPCHS dilaksanakan pada tanggal 6 agustus dan final 20 agustus

selamat menikmati!

Penyisihan (6 Agustus 2017)

Nah aku ga banyak nyiapin untuk penyisihan. aku masih sante-sante aja tau-tau udh penyisihan. untuk penyisihan ini aku menargetkan cepat dan akurat.

saat ngerjain penyisihan aku cukup cepat, aku menjadi orang kedua yang menyelesaikan problemsetnya namun penaltiku monster jadi aku digeser terus sehingga menjadi ranking 4 di scoreboard akhir.

aku sudah lupa soalnya, tp saat ngerjain aku oneshot semua kecuali suatu soal rekursi. itu aku mau gaya pake map tp kena MLE terus. aku bingung dan sudah ku optimisasi sampe mati namun MLE padahal batas memorynya masih jauh. akhirnya terpaksa ga keren yaitu pake array. AC setelah 7x wa.

aku rasa sih soalnya ga perlu dibahas karena banyak yang bisa :v

Selesai penyisihan

aku evaluasi, ternyata aku bisa panik kalau ga AC dan bisa ngebom submission. dan aku juga nyadar lebih baik akurat tp lambat daripada cepat tapi rengas. aku akhirnya melatih akurasi. 

caranya adalah aku kerjain soal bnpchs tahun lalu, kalau aku bisa oneshot aku boleh makan oreo :v kalau ga yaudah. hasilnya cukup baik aku oneshot terus. aku juga olah raga kokkk jadi ga tambah gendut. beratku jadi 80 kg doang. "aku ga gendut, aku hanya terkompresi dengan baik". -Kak Ayaz

Minggu depannya ada penyisihan compfest dan aku jadikan ajang untuk menunjukkan akurasiku. jadi ini sistemnya ada freeze dan aku berniat untuk submit di jam terakhir. hasilnya cukup memuaskan. 3 dari 5 oneshot dan soal compfest itu IOI style jadi lebih berat untuk oneshot.

hari-hari sebelum final aku lewati dengan latihan soal BNPCHS, tidak lupa dengan selalu oneshot. pada suatu saat aku selalu oneshot sampe-sampe saat ga oneshot ada shock gitu.

Hari Keberangkatan Final

aku sudah survei tempat dan dapetnya di hotel amaris. aku berangkat pagi dari rumah. aku sadar tetanggaku mau ke turki jadi aku numpang aja ke bandara.

sesampainya di bandara ga banyak ngapain langsung boarding. saat tiba di bandara aku langsung cari taksi bluebird karena taxi online ga boleh masuk. ada tempat ngantrinya langsung berangkat deh.

Saat ditaksi kok aku ngerasa argonya cepet banget ya naiknya. aku nengok dikit udah deh nambah 3000 :v. trus aku baca di pintu taksinya ternyata argonya per-km. jadi aku jalanin eksperimen untuk ngitung tarif kasar per KM.

aku perhatiin kecepatan taksinya 100 km/jam. trus aku hentakkan kakiku tiap detik. ternyata tiap 5 detik argonya naik sekitar 390. aku buka kalkulator deh.
80 km/jam = (80x1000)/3600 = 22.22 m/s.
karena 5 detik, maka 5 x 22.22 = 111.1 m.
setiap 111.1 meter bayar 390.
bererti bayarnya 3,510 per meter
berarti per km dikali 1000 jadinya 3510 per km.
hmm trus aku perhatiin lg 11 km bakal nyampe. jd harusnya aku bayar lg 38610 kasarnya.

saat nyampe, aku perhatiin aku nambah sekitar 40 rb. berarti perhitungan kasarku sukses!!.

Sampai di hotel Amaris, check-in. langsung masuk ke kamar. impresi pertama wifinya kenceng. aku langsung tidur karena kecapekan. bangun sekitar jam 6 sudah lapar. aku buka go-food cek mana makanan terdekat. ada iklan domino pizza yaitu 2 pizza 100 rb(?). aku beli itu deh akhirnya

Ternyata pizzanya lebih banyak dari yang kuduga! aku ga habis!. lanjut belajar, masih ada sebuah soal maut bnpchs 2015 yang belum kelar yaitu permainan pandy. setelah diskusi akhirnya dapet ide dan AC. akhirnya hutangku selesai!. waktu sudah jam 11 WIB. jadi aku tidur.

Hari-H lomba

Bangun pagi, sarapan. karena hotelnya lagi sepi saat mau sarapan petugasnya inget aku kamar brp.

makanannya enak. saat mau ambil buah tiba-tiba ada masalah perut jadi balik ke kamar. selesai menuntaskan aku kebawah, check out, trus ambil buah sambil nunggu gojeknya dateng.

Lomba BNPCHS ini memperbolehkan pake baju bebas. ini sangat membantu dalam hal pengemasan pakaian karena artinya aku bisa hemat 1 set. nanti baju ini aku pake ke bandara.

ada peserta yang nanya rute angkot ke binus gimana, katanya biar hemat. trus disanin pake gojek aja. dia gamau katanya biar hemat. gojek bayarnya 10 rb :|

sampai di binus aku bingung masuknya gimana karena di drop di depan gedung parkir. akhirnya ketemu juga tempat liftnya. sebelum masuk aku buka line dulu. aku liat Vince lagi nyasar dan dia manual naik eskalator. akhirnya aku ngepap kalau aku lagi "OTW"

saat aku selesai ngirim ini, pintu lift kebuka menandakan tujuan

saat pintu lift terbuka kembali, aku langsung disambut dengan suasana ramai. tampaknya lantai 8 sudah dikemas khusus untuk acara bee-fest ini. aku registrasi trus liat ada Akbar, Ariell, dkk jadi aku duduk disana. pertama aku tanya Vince udh nyampe belum, mereka bilang belum dan aku baru saja mau ketawa taunya Vince muncul di belakang.

Grup sangar, gaada yang mau duduk deket-deket kita xD
Mulai deh acaranya. ada basa-basi gitu nanyain asal daerah peserta. Aku mulai gregetan karena dari Sumatra ke Jawa langsung lompat ke Kalimantan trus ke Sulawesi padahal aku udah siap angkat tangan yang tinggi. aku denger beberapa bisikan sayup-sayup "Bali kok ga disebut?". memang sih aku sendiri dari Bali tapi di anggep dong :(.

Mcnya akhirnya peka dan Bali disebut.

MANTAP BALI
MC: "Wah ada yang dari Bali!! bisa jualan pie susu dong!"

oh jadi gini stereotype orang Bali sekarang. kukira aku udh istimewa jualan pie susu saat OSN.

Selesai gitu langsung ke ruangan. di depan ruangan ada semacam snack gitu. biasanya kan dikasi air putih, nah ini teh pucuk. aku maunya bawa ke ruangan tp ga dikasi jadi aku batal ngambilnya, namun saat lagi di ruangan aku liat ada orang yang bawa minuman, aku tanya panitia boleh gak dan ternyata boleh jadi aku lari ke luar ambil teh pucuknya lagi. ternyata harus ditaro di locker yaudahlah.

Bnpchs ini lomba pertama yang aku ikuti yang memperbolehkan bawa cheetsheet atau contekan. Nah karena aku udah pro gatau mau tulis apa jadi gatau mau digimanain. tapi aku ngerasa harus bawa cheatsheet. selama latihan akhirnya aku sadar kalau aku buat segment tree lama dan di bnpchs speed dihitung jadi aku buat template segment tree. trus aku juga males ngertiin euclid extended jadi bawa itu juga. sisanya aku bawa buku CP3 siapa tau topik yang ada di bab "rare topics" keluar.


ngerjain soal final pun dimulai
jadi ada 11 soal, yaitu A-K.  karena awal-awal scoreboard masih kosong, aku menerapkan strategy yaitu kerjain soal A, saat aku selesai pasti scoreboard sudah rame jadi tinggal sikat-sikat aja yg mudah.

Baca A. hmm pola mudah, dikoding pertama mau nyoba keren pake rumus O(1), taunya ribet karena stress pasti pada mulai nemuin polanya. setelah beberapa saat terlihat di scoreboard depan ruangan bahwa ada yang AC A, diikuti beberapa saat kemudian orang-orang mengACkan A dengan derasnya. sedangkan saat menit 13 aku baru mulai ngoding setelah memutuskan untuk bruteforce total n^4...

ngoding dan WA!!. wah ternyata outputnya harus dipisahkan baris antara tc. perbaiki dan WA lagi!!. ini sangat membuat mentalku down karena kalau ga ac kena penalti waktu 20 menit dan itu sangat berasa bagi yang penaltinya lebih dikit.

akhirnya aku penasaran tc terakhir perlu nyetak newline ganda gak sih, buat klarifikasi karena aku gamau wa lagi. dapet jawaban "baca soal lebih teliti". tapi kali ini jawaban ini sangat membantu karena ternyata ada kalimat "antara 2 kasus uji dipisahkan sebuah baris" artinya tc terakhir gausah di enter. perbaiki dan AC!! soal A accepted


aku mengackannya sekitar menit ke 20. dan bahkan saat itu sudah ada yang ac 3 jadi aku sangat terbelakang!. oh dan ternyata aku salah lihat! yang banyak ac itu soal B bukan soal A, maklum scoreboardnya jauh di depan. baca B dan itu cuman looping biasa. koding dan ac oneshot soal B accepted



trus liat scoreboard ternyata SW sudah ac C, aku baca dan ternyata itu dp mainstream. nah permasalahannya dia mulainya hari 0 atau hari 1? hmm... soalnya mulai dari kedua hari tersebut memenuhi sample. trus aku perhatikan SW WA sekali jadi aku pun punya feeling mulai dari hari 1. koding, berharap cemas, dan AC oneshot! soal C accepted



trus aku perhatikan di scoreboard bagian bawah ada orang ackan I, aku sih mikirnya kalau dia aja bisa maka aku pasti bisa maka akhirnya aku kerjain. lagi-lagi soal "time waster".


tapi aku sudah belajar banyak teknik keren, jadi titiknya aku simpen di struct yang isinya array of pair untuk tiap titik. trus kalau mau bandingin 2 buah segitiga buat fungsi yang isinya ngesort arraynya trus bandingin sama atau tidak (ingat karena fungsi, maka ini pass by value, walau di fungsinya elemennya ke sort tidak akan berpengaruh kepada elemen aslinya). dan aku testing dan kok salah ya fungsi ngebandinginnya. aku coba dan ternyata dia selalu return false...

baru aku inget array itu bukan object jadi gabisa bandingin 2 array sama pake (a==b) dan harus looping. akhirnya aku ganti isi structnya jadi vector of pair deh... cukup dikit modifikasi kode dan akhirnya fungsiku sukses. submit dan jelaslah AC (oneshot) soal I accepted


Lalu aku liat ada sangat banyak orang mencACkan G. aku baca deh. saat pertama baca langsung tau kalau ini soal classic KMP dan aku pun bingung kok bisa banyak orang mendapatkan AC. setelah baca constraintnya yah ternyata panjang string <=25. jadi akhirnya aku buat algo bruteforce n^2 yaitu ngecek bisa gak buat palindrome sepanjang x, kalau bisa maka buat kalau enggak cek apakah bisa buat sepanjang x+1 (ini looping). ngecek bisa atau enggaknya juga pake looping. koding, dan aku pun niat cobain semua samplenya, lalu submit dan oneshot lagi soal G accepted



disini aku merasa sudah mengimbangi performa awalku yang kurang... semangatku pun balik full


Trus aku liat scoreboard bagian bawah ada yang ackan K. aku akhirnya mengerjakan itu. saat baca awal jadi teringet soal csacademy lama yaitu pasti optimal mindahin orang terakhir. aku bahkan terlalu malas untuk membuktikan tp karena udah ada yang ac jadi aku yakin gitu solusinya. koding dan ac! soal K accepted  (oneshot tentunya)


Lalu ac pada soal F mulai menumpuk. akhirnya aku kerjain dan ternyata cuman soal kombin. karena aku malas jadi aku buat algo sederhana yaitu hitung frequensi tiap huruf pake looping trus misal frequensi tiap huruf mulai dari a itu f1,f2,f3,...f26 maka jawabannya n!/f1!f2!...

int freq[200] //nyimpen frekuensi kemunculan tiap karakter, saking malesnya pun aku set limit gede
string s[]={"kwetiuw","mihun","friedrice"}
int a[] //a[0] banyaknya kwetiauw, dst...
for(i=0;i<3;i++)
{
for(j=0;j<s[i].size();j++)
{
freq[s[i][j]]+=a[i];
}
}
ans = fact[sum]; //total dari freq[0] sampai freq[200]
for(i=0;i<200;i++) ans=ans* 1/fact(freq[i]);
fact[n] = n!
nah ngitung 1/fact[x] aku pake inverse factorial.

dari sc diatas kelihatan banget aku orang malas :v

aku coba run sample dan hasilku beda jauh!. aku takut, jangan-jangan soal ini tidak semudah yang kukira. baca-baca penjelasannya dan kayaknya biasa aja deh. jadi kemungkinan terakhir adalah typo di nama makanan. dan benar saja! "kwetiuw" xD. diperbaiki dan lolos sampel

kusubmit dan dengan pede ekspektasiku oneshot lagi. NAMUN untuk setelah 5 soal oneshot akhirnya aku dapat WA juga!!!. aku pun langsung ngedown. bukan karena aku merasa bakal kalah namun karena streak oneshotku berakhir.

namun karena soal ini cukup straightforward kalau ada salah debugnya harusnya mudah. aku cek ada perkalian overflow gak. dan alangkah kecewanya aku saat baca baris terakhir ada kode
cout<<"sum"<<"\n" //ini untuk ngedebug saat typo tadi

aku facepalm keras banget walau tidak sekeras saat ngerjain soal daratan dan es di OSN 2017. aku komenkan linenya dan submit. dapet AC. soal F accepted

sejujurnya aku agak trauma kalau buat kesalahan-kesalahan seperti ini. aku inget pas PCS aku submit sc iseng dan WA lalu poinku berkurang 5 poin. ternyata 5 poin itu menjadi penentu dan nilaiku berbeda 1 poin dengan juara 2. aku berharap mudah-mudahan kali ini kesalahan itu tidak menjadi fatal.

Saat aku mengackan F. waktu sisa lagi 3 jam 20 menit lagi dan soalnya sisa 4. sempet baca sekilas semuanya (kecuali D) dan ini tinggal soal hard yang harus mikir.

sebelum ngerjain soal F tadi aku sempet baca soal H, dan aku liat scoreboard SW WA di soal tersebut. ini menurutku soal pure math jadi akhirnya aku niatkan cari rumusnya. aku formulasikan rumusnya dan ada sekitar 4 kasus berbeda.

submit dan WA!. trus baru nyadar ada kesalahan minor saat pers 1nya y=0, dan pers 2nya x=0. jadi aku fix "wah bakal ac sebelum SW nih" dan ternyata WA lagi!!

trus aku baru baca kalau ternyata nilai xnya bisa 2^63. yah...

SW udah ac E. aku baca dan itu kompleks banget ._.. ada naga, lorong, buah ajaib, dll. ditambah lagi samplenya yang 1 halaman!. akhirnya aku balik lagi ngerjain H :v

coba deh aku utak-atik mathnya dan ga nemu rumus yang kalau dikali ga overflow. oh iya dari submission pertama aku udah bagi dengan gcdnya kok...

setelah sejam utak-atik akhirnya aku pun menelantarkan soalnya karena melihat posisiku  di scoreboard sudah menurun karena orang-orang sudah mulai mengackan D dan E.

Aku baca E lagi dan  dapat observasi samar kalau soal ini bisa direduksi menjadi ngitung waktu tercepat sebuah naga sampai ke finish, dan waktu tercepat pak bondol. apabila pak bondol lebih cepat, maka itulah jawabannya. apabila tidak, maka jawabannya -1

Aku dapat observasi itu karena soal tipe gini pernah aku kerjain saat menyusup di sparing jateng-jakarta sebelum OSN 2017. bedanya disana nilai tiap edge 1 jadi bisa dihitung dengan BFS sedangkan yang ini harus pake dijsktra.

namun aku masih kurang yakin dengan observasi tersebut. jadi selama 10 menit aku coba menyakinkan diriku kalau itu benar. misal naga dapat mencegat pak bondol di tengah jalan, maka mereka pasti bisa "bareng-bareng" ke tempat finish dan akan mendapat waktu selesai yang sama. OK observasi terbukti!

dikoding dengan dikjstra. ditambah state boolean tambahan yang menyatakan apakah dia sudah makan buah atau belum.

kurang lebih aku buat struct yg nyimpen jarak,posisi,flag

trus karena kalau naga makan buah kecepatannya 2x lipat, artinya panjang lorongnya dibagi 2. karena aku sangat MALAS berurusan dengan double maka panjang lorongnya aku kali 2 semua.

ya jadi jalanin dikjstranya dari setiap naga secara pararel (push semua naga ke queue secara bersamaan). trus transisinya lumayan mudah.

nah saat mau nyari jarak pak bondol, aku copas dijstranya naga dan hapus baris
if(adabuah[pos]) flag=1;

cuman aku lagi males pake function soalnya aku sudah terlanjut buat semua arrayku di lokal. setelah dipikir-pikir kok aku males banget ya sangat bnpchs ini...

nah saatnya test sample. ini sampel tc 2nya panjangnya satu halaman dan kalau kodeku ngebug aku sudah membayangkan harus masukin tc ini berkali-kali tentunya akan menghabiskan waktu. jadi untuk pertama kalinya di lomba ini aku pake fungsi freopen. aku ingat ada versi online soal ini juga di tab problem jadi  aku pergi ke halaman problem dan buka link soal ini dan aku terkejut karena mendapat tulisan "silahkan membaca di lembar hardcopy" jadi masukin tcnya ke file secara manual deh. buat panitia, inilah gunanya tetep ada versi online soalnya walau ada printout (contoh OSN)

setelah masukin tcnya akhirnya aku jalanin. setelah perbaiki beberapa bug yang sangat minor akhirnya aku mendapat jawaban untuk tc 1 benar, dan tc 2 salah (aku dapat 74). aku pun mikir, sial bakal susah nih debugnya karena tc 2 itu lumayan besar. namun setelah aku analisis ternyata ada edge langsung yang ngehubungin 2 dan 8 dengan nilai 37. jadi dijstra kedua aku tambahin beberapa debug print dan aku pun bingung, loh kok saat dia di posisi 2 dia ngepush 74 ke 8?. aku cek lagi dan gaada edge 2-8 yang nilainya 74. mulai aku berpikir macam-macam, "bug parah nih kodeku"

setelah kurang lebih 15 menit testing-testing aku baru inget kalau jarak tiap lorong aku kali 2 aduh sialnya. "hack"ku backfire.

yaudah jadi jawaban akhir tinggal aku bagi 2.  sesaat sebelum submit, ungatan soal F ngeflash gitu dan aku pun cek source codenya lagi. benar saja! lupa ngapus freopen. "hampir saja!". nah jadi biar tambah yakin aku jalanin sekali lagi kodenya untuk ngecek ada debug print nyasar gak. ternyata ga ada. aku melihat scoreboard peringkatku sudah peringkat 8 atau 9 dan aku sedih.

akan kupertaruhkan segalanya pada submisi pertama ini! semua perasaan keluarga,teman, adik-kelas akan aku taruh di dalam submisi ini!

submit, refresh dengan deg-degan dan ACCEPTED! aku lihat scoreboard dari peringkat 8-9 aku langsung melompat ke peringkat 3 dibawahnya SW dan Kezia karena penaltiku kecil. dalam hati "i still got it!" soal E accepted

waktu tinggal 90 menit. setelah dipikir-pikir 7 soal pertama habis dalam 90 menit. lalu 2 jam untuk mengackan 1 soal (gak satu soal sih, karena nyoba H juga)

karena SW sudah ac D yaudah aku baca untuk pertama kalinya. ternyata ini soal ad-hoc time-waster gitulah. beruntungnya aku pernah ngerjain soal ini dengan versi yang lebih susah di sebuah lomba lokal tahun lalu (intinya di soal itu diminta terjemahan langsung).

jadi bagian ngubah-ngubah nilai N sangat mudah karena walaupun n=1 milyar dalam sekali langkah akan tereduksi menjadi sangat kecil. bagian susahnya adalah ngubah angkanya jadi huruf

jadi angkanya aku bagi 3. angka jutaan, ribuan dan satuan. (kasus khusus kalau n=1 milyar, dan n=0). trus aku buat 3 array hashing, satu untuk ratusan,puluhan, dan satuan.

lalu tinggal dikerjain aja dari 3 nilai tersebut. misal jawabannya ans. cara ngerjain jutaan,ribuan,satuan sangat mirip bedanya cuman kalau jutaan dan ribuan, jawabannya ditambah 4 (karena perlu nambahin "juta", atau "ribu) dan kalau ribuan kalau nilainya 1 itu kasus khusus return 6 (seribu = 6).

ini main fungsi gitulah jadi ga ribet. nah saat aku testing di sample kedua kok aku bingung 12 itu jadi 9. bukannya "DUA BELAS" = 8?. oh ternyata saat baca penjelasannya spasi termasuk.

yah modif dikit aja sih. tinggal tambahin variabel baru "spasi" jadi tiap kali kita nambahin ans kita juga nambahin spasi dengan nilai 1 atau dengan kata lain nilai akhir spasi = banyaknya kata pada bilangan. nanti jawabannya (ans + spasi - 1) (karena kata terakhir ga perlu di spasi)

ku test di sample kedua kok masih beda ya. aku cek penjelasan loh kok ini jelas-jelas beda jumlah katanya. akhirnya aku tenang dan baca klarifikasi ternyata memang samplenya diralat dan aku benar.

coba akhirnya aku tes di angka-angka random besar (bahkan yang terbesar aku test dengan angka yang menghasilkan panjang string 91). dan benar semua. aku pun cukup PEDE dengan ini. jadi aku submit. dan yak, bisa ditebak aku oneshot! soal D accepted

waktu itu sudah sisa lagi 57 menit jadi sudah freeze. asik-asik bisa buat kejutan. peringkatku saat freeze adalah peringkat 4 dengan ac 8 sedangkan peringkat 3nya adalah Salman dengan ac 9. namun aku liat penatlyku saat submit D adalah 846 sedangkan Salman adalah 892. yess nyalip.

Namun aku masih khawatir karena dia sudah AC D dari tadi seharusnya dia punya cukup banyak waktu untuk H, maka aku tidak boleh gegabah dan mengerjakan H lagi. setelah 20 menit utak-atik rumusnya agar ga overflow ga nemu-nemu juga. akhirnya aku liat tcnya sampe 1000 jadi aku merasa ada kemungkinan solusinya ga O(1).

setelah coba branstorming dan nyoba-nyoba ide-ide aneh seperti euclid Akhirnya dapat observasi ini bisa di ternary search. selesai lomba aku dapat jelasin namun gaada yang ngerti. mudah-mudahan sekarang menjadi jelas.

sudah jelas bahwa ini sama saja dengan mencari titik perpotongan 2 buah garis. apabila 2 buah garis tersebut digambar...

ini pake paint

misal garis p itu garis penentu. nah sekarang dari setiap titik di garis t kita coba cari jaraknya ke garis p (jarak titik ke garis). gambarnya akan terlihat seperti di bawah ini


garis tipis -> jaraknya

nah apabila kita buat grafik jaraknya dari titik x terkiri sampai terkanan, maka akan didapat grafik kurva! (dari kiri akan mengecil terus sampe berpotongan, terus membesar lagi).

perhatikan jawabannya muat dalam integer maka kita hanya mencoba kemungkinan dari -2^31 sampai 2^31 artinya ga bakal terjadi overflow! aku pun kegirangan saat menemukan cara ini.

namun waktu lagi 25 menit, dan aku gatau caranya nyari jarak dari titik ke garis secara general. namun aku ingat buku CP3 yang daritadi nganggur dan tersenyum. aku buka bab tentang garis dan ternyata ada! (distance point to lines). nah aku suka CP3 ini karena dia buat source code yang bisa langsung dipake. nah masalahnya di buku itu garisnya harus berbentuk 2 titik jadi aku harus konversi garis p jadi 2 buah titik. nah aku mikirnya biar konsisten aku coba cari biar titiknya bisa dinyatakan dengan bulat. namun tidak menemukan caranya (lupa sama si euclid, karena tadi udah nyoba). tak terasa waktu lagi 15 menit

 terpaksa aku main double akhirnya.

ini pertama kali copas kode tanpa mikir. dan saat bagian buat ternary search sempet ngebug karena aku buru-buru buatnya. saat sudah OK aku submit dan itu waktunya <1 menit. saat aku mau liat hasil sudah keburu log out jadi gatau soalnya bener atau gak.

nah aku mikir, kalau misalnya aku bilang AC 9 taunya yg H AC, aku bakal dibilang pembohong dan ga bakal dipercaya lagi. jadi mending aku bilang AC 10 trus taunya H ga AC.

selama kontes aku hanya baca J sekali, buat klarifikasi, dan ga nyentuh lagi.
==kontes selesai

"kenapa gak jelasin aja"
karena aku orang malas dan gamau jelasin panjang-panjang tiap ada yang nanya.

Trus nanya keluar dan Salman ga AC H berarti yang pasti diatasku itu Kezia dan SW. nah aku mulai takut jangan-jangan ada orang tak terduga yang mengackan H di jam terakhir. aku gasempet nanyain semua.

nah langsung aja ke ruang pengumuman. MCnya nanya-nanya dulu dan aku pingin banget ditanya. sayangnya malah Akbar yang ditanya namun karena dia malu-malu akhirnya aku pun bilang "saya kak!" akhirnya ditanya deh dan aku jawab dengan jujur. 

MC: "gimana kesanmu ngerjain soal"
Galang: "soalnya susah-susah"
(semua ketawa)
Galang: "saya sangat stress ngerjainnya"
(semua ketawa)
Galang: "saat yang lain pada ac 5 saya baru ac 2"
Galang: "namun berkat keteguhan hati akhirnya akhir-akhirnya aku pun bisa mengejar mereka"
Hekel: "Akhirnya lu ac berapa? 10 ya?!"

 ada fullbody VR namun beberapa saat kemudian ada seminar gitu jadi VRnya ditutup. ada seminar dari program study di binus dan aja juga tamu penting yaitu pak On Lee yang jadi COO di tiga perusaan ngasi materi.

aku duduk dibelakangnya Vince dan aku pingin nanya gedean gaji programmer atau dokter. Vince juga kelihatannya penasaran.  nah Pak On Leenya peka dan kadang nunjuk Vince karena dikira bakal bertanya.

Selesai ceramah akhrinya ada saat yang kutunggu yaitu pembahasan dari jollybee. saat pembahasan soal D aku sebagai mantan anak mtk tidak puas karena kurang lebih kaya gini pembahasannya:

"ada pola yaitu apabila n=0,1,2,3,4,6,1000 maka jawabannya 4, selain itu jawabannya 5. bukti: kita coba n=0-11 dan perhatikan memenuhi pola, maka polanya pasti memenuhi untuk n= 0 sampai 1000000000"

saat sesi tanya jawab aku maunya bertanya tentang itu namun menahan diri karena nanti bakal dikira bodoh. jadi saat aku menulis blog ini aku tertantang untuk membuktikan polanya dan di bawah ini aku akan coba membuktikannya dengan lebih meyakinkan. walau mungkin tidak 100% rigor namun setidaknya lebih menyakinkan lah ._.

misalkan f(n) -> banyaknya karakter pada representasi nilai

lemma 1: apabila n>7, maka n>f(n)
bukti:
banyaknya huruf maksimal dari sebuah angka adalah 8 (didapat dari "SEMBILAN")

n=5-20 dicoba aja dan tidak susah untuk melihatnya
untuk n=20-29. huruf = "DUA PULUH + x" bernilai maksimal (10 + 8) = 18. maka pasti n>f(n)
n=30-99, huruf = "x PULUH x" bernilai maksimal (8 + 8 + 5 + 2) = 23. maka n>f(n)
untuk sisanya kita bisa buat upperbound kasar. kita misalkan untuk y digit banyaknya digit itu kira-kira 8y (semuanya angka 9). karena karena y=floor(l0log(n)) + 1 maka 8y<<n .
terbukti...

lemma 2: apabila n>7 maka f(n) >= 7 (kecuali n=1000)
bukti:
bagi beberapa kasus
n=8-11 dicoba manual aja
n=12-19 perhatikan bahwa ada " Belas" itu sudah 6 kata. maka berapapun depannya pasti ada 1 kata lagi
sisanya= perhatikan bahwa banyaknya kata pada N pasti minimal 2. untuk setiap bilangan, pasti mengandung salah satu kata dibawah ini (perhatikan spasi di awal kata)
{" puluh", "seratus", " ratus", " ribu", " juta", " milyar"}
perhatikan bahwa kita juga pasti mengisi sebuah nama angka. karena angka yang memiliki string terkecil ada "2" (DUA) maka dalam kasus terbaik sekurang-kurangnya bakal ada 7 karakter apabila ditambahkan imbuhan tersebut.
TERBUKTI.

lemma 3. apabila n>7 (kecuali n=1000). maka suatu saat ketika kita terus mengganti  n dengan f(n) pasti akan dapat 7.

bukti:
berdaskan lemma 1
kita buat nilai n saat di transformasi ke i menjadi baris berikut (ni>n(i+1) berdasarkan lemma 1)
n0, n1, n2, ..., ni 
apabila ni>7, maka berdasar lemma 2 kita masih bisa menambahkan elemen baru yaitu n(i+1) dan tetap akan mendapat barisan dengan n(i+1) >=7. perhatikan bahwa berdasarkan lemma 2 ni tidak akan pernah kurang dari 7.
TERBUKTI

lalu transformasi 7. 7 -> 5 -> 4 -> 5

jadi apabila n>7 (kecuali n=1000) maka jawaban terakhirnya adalah 5.

n=1000 istimewa karena tidak memenuhi lemma 2.

lalu saat pembahasan J, saat disana aku ngerti ide umum tapi masih ga ngerti detail-detail kecil. namun setelah dipikir beberapa saat akhirnya ngerti. idenya lumayan mudah namun aku ngebayangin ngodingnya bakal perlu tricks-tricks agar efisien.

Akhirnya saat yang ditunggu-tunggu tiba! pengumuman!. pertama pas pengumuman perunggu aku masih santai. nah saat perak ini mulai deg-degan. yang aku tau cuman kalau peringkatku > Salman

Rania dipanggil, lalu Igo. ini artinya aku akan mendapat emas!. cihuy!

dan benar saja saat emas aku dan SW dipanggil. jadi yang juara ditampilin gitu mukanya saat ngerjain soal dan aku "sadar kamera". tiap kali ada yang foto aku langsung bergaya (kayaknya aku kena penalty beberapa menit gara-gara ini).

saat aku naik mcnya ngomong gitu ke aku dari jauh "katanya soalnya susah!" trus aku bales "memang susah tapi bukan berarti ga bia jawab". Temenku Akbar ada yang jadiin meme




dia tuh malu-malu ngirim ke grup OSN takut ada SW jadi akhirnya aku yang mencet :P. lumayan nih aku suka.

sudah ditebak siapa juara umumnya. satu-satunya yang ac 10 tidak lain adalah... Kezia m(_ _)m.

Setelah itu aku lumayan lama diem disana nunggu duitnya. Vince juga masih disana. akhirnya aku dapet fotoin SW bersama Kak Arnold lalu karena ada pengumuman duitnya bisa diambil diluar akhrinya keluar deh. diluar diajak ngomong sama kakak-kakak binus cukup lama. akhirnya ada yang nanyain compfest langsung Vince yang kukira sudah nyampe penginapan tiba-tiba lompat ke sampingku.

Pesawatku jam 9. saat itu jam 6. aku sama Vince akhirnya nyari makan bareng. Memang karena Bandara dan Binus lumayan dekat dan aku memperkirakan hanya perlu 30 menit untuk sampai jadi kalau aku berangkat jam 7 harusnya aman.

kita nyarinya jalan kaki keluar dari binus. Baru keluar kita melihat restoran hongkong maunya makan disana tetapi aku ngeliat pintu masuknya terlalu mewah jadi punya firasat buruk akhirnya kita terus jalan.s etelah keluar dari gang binus aku liat ada Dcost yaudah akhirnya makan disana.

Sistemnya disini ga pake pelayan. kita ambil kartu makanan trus bayar di kasir. karena aku pingin udang jadi aku nyari-nyari mana nih kartu udangnya sementara Vince udah selesai mesen
Vince mesen ayam + tempe+nasi sedangkan aku udang + nasi goreng. total belanjanya 150 rb ._.



ketika minuman datang aku ternyata minumanku dan Vince sama yaitu es milo. Vince bilang memang itu aja yang menarik. akhirnya kita ngobrol masalah OSN (aku sudah lupa ngomongin apa) trus makanan dateng deh. wih Vince 3 piring makannya, jangan tertipu dengan badannya yang kurus.

makanan pun datang!

makan bang


Waktu menunjukkan sekitar 7 kurang 15 saat kita selesai makan. aku bilang sama Vince balik dah duluan aku mau pesen grab. dia pun pergi. akhirnya setelah grab terpesan aku keluar namun di datengi pelayan katanya snackku ketinggalan. yah ternyata itu snacknya vince ditaro dibawah meja lupa dibawa. namun karena snacknya enak aku deh yang ambil :).

Lalu drivernya nelpon dia bingung mana nih dcost gaada. aku bilang deket binus dan drivernya bilang aku salah masukin alamat. Aku padahal udah ngandelin lokasi dan ternyata lokasinya melenceng lumayan jauh dan drivernya bilang perlu waktu 15 menit untuk sampai ke tempatku.

setelah sekitar 10 menit, Vince lewat didepanku. aku takut jangan-jangan dia balik ngambil snacknya, taunya dia salah arah xD. wah pasti sudah jauh jalannya.

Saat drivernya datang sudah jam 7 lewat dikit. langsung deh berangkat ke bandara.

sesampainya di bandara langsung aja aku ke tempat check-in namun aku menyadari bandaranya sepi banget. saat masuk pintu keberangkatan diluar cuman aku doang yang ada. trus ruang check-in bagasi kosong melompong!
Suana bandara Soekarno-Hatta malam senin...
Nah aku sampainya jam 8 dan pesawatku jam 9. tapi aku santai saja karena ga bawa bagasi dan bandara sepi. sesudah check-in dan masuk ruang tunggu, diumumin kalau pesawat di delay satu setengah jam!. waduh!!. akhirnya aku membuka laptop dan jawab-jawab pertanyaan yang ditanyain kepadaku (seperti pr anak kelas 11).

tak terasa sudah saatnya boarding tapi aku kasihan sama bapakku yang sudah nungguin dari jam 8 di Bali jadi bapakku nunggu lama banget.

Di pesawat karena lion gaada Tipi jadi aku tidur dan saat bangun sudah mau mendarat pesawatnya.

Langsung disambut bapakku dan pulang. di mobil aku liat kursinya sudah diturunin jadi aku bersyukur ternyata bapakku nunggunya sambil tidur di mobil dan bukan nungguin di kedatangan jadi perasaan bersalahku berkurang.

Aslinya pesawat dijadwalkan sampai jam 11 jadi sampai rumah jam 12 masih termasuk waktu normal untuk tidur. namun karena delay tadi jadi nyampe bandara jam setengah 2 dan sampai rumah jam 3!. mana lg 4 jam bakal upacara bendera lagi!. Kalau saat SMP sih aku bakal bilang "capek" dan gak sekolah namun karena aku sudah kelas 3 sudah bertanggung jawab akhirnya aku maksimalkan waktu tidurku yang sisa 3 jam.

Bangun pagi karena aku pake alarm canggih yang tidak mau mati kecuali kita berhasil jawab soal mat jadi aku bangun pagi dengan segar. btw nama appnya "i can't wake up" silahkan dicoba! (bukan promosi tp appnya memang bagus bagi yang sulit bangun).

Sedikit funfact tentang blog ini:
karena aku takut bakal lupa detail saat ngerjain soal final, maka aku buat tulisan ini dimulai dari saat ngerjain trus kebawah sampai selesai, baru balik ke atas lagi.

Nah sekarang aku ingin ngomongin hasil BNPCHS lagi:


saat kontes aku tuh santai banget ngerjain. dari awal kontes aku ga pernah menduduki posisi 5 besar. bahkan aku tidak memiliki first solve!.

"trus kenapa dong bisa emas"

ya karena kecepatan ac bukan cuman satu-satunya faktor. ada faktor lain yaitu penalti waktu. setiap solusi non-ac waktu akan ditambahkan 20 menit. 20 menit itu adalah waktu yang cukup lama jadi logikaku kalau waktuku tidak jauh-jauh amat dan lebih akurat maka aku pasti bisa unggul. dan benar saja!. disaat yang lain pada ac 8 dan aku menduduki peringkat 8, saat aku oneshot problem E langsung meloncat ke peringkat 3!. menurutku sih kalau awal-awal acnya banyakan namun penalty gede itu  bakal lengser. ingat saat penyisihan disaat sudah ada 3 orang yang AC semua, sejam kemudian tiba-tiba ada yang muncul entah dari mana dan merebut peringkat 1 (Fausta)

lihat saja peringkat 4, (maaf ini bukan bermaksud menyinggung). ac di semua problemnya dia  lebih cepat dari aku kecuali I dan K, bahkan ada perbedaan yang cukup jauh seperti di D,E,F. dan dia juga sudah AC 9 sebelum freeze. namun karena penaltinya gede maka saat freeze walaupun aku baru mengackan problem ke 9 aku bisa menyalipnya.

Aku bisa bilang kalau keunggulanku adalah aku sangat tenang saat ngerjain soal berbekal dari pengalaman dan meditasi. apabila aku tidak AC aku hanya akan syok selama beberapa detik lalu kembali mengontrol. inilah senjata pamungkasku untuk BNPCHS ini.

Jadi aku ingin memberikan tips untuk kontes ACM style seperti ini (kayanya cuman BNPCHS deh...) kalau ingin menang, jangan fokus pada ngetik cepat dan mendapatkan solusi secara tepat dulu. fokuskan pada peningkatan akurasi karena sudah dibuktikan lebih menguntungkan. btw aku masih ngetik pake 2 jari lhooo :P.

Akhir kata, aku ingin mengucapkan terima kasih kepada seluruh panitia BNPCHS karena acaranya keren, materinya seminarnya bagus dan soal lombanya pun menantang. tapi  saya rasa persebaran tingkat kesulitan perlu di perbaiki agar ac peringkat 2-10 tidak sama. makasih juga beasiswanya :).

beberapa hari setelah BNPCHS aku cek dan semua foto sudah di upload. saat ngerjain soal aku ingat untuk bergaya agar menarik. dan inilah hasilnya

ayo temukan perbedaan :v

tetapi akubaru menyadari pentingnya foto candid. beruntung saat aku mengscroll albumnya kebawah ternyata aku menemukan foto-foto candid. ternyata panitianya tidak mau nyerah dan diam-diam foto aku tanpa disadari :D
Setelah 2 tahun ngeCF, akhirnya aku memasang DP juga :")

baiklah tulisan ini aku tutup. dalam waktu dekat ini aku akan mengikuti lomba lagi yaitu Compfest 9 di Universitas Indonesia. jadi bagi yang ikut sampai ketemu ya :)

Comments

Post a Comment

Popular posts from this blog

Menjadi Maba yang Penuh Ketidaktahuan

UI baru saja selesai UTS tadi, dan UTSnya sangat greget. Postingan sebelumnya sebenernya hanya untuk bilang kalau sekarang aku punya domain, ini postingan yang sebenernya. Jadi kali ini aku bakal buat nyeritain gimana aja sih selama 3 bulan pertamaku kuliah di UI.  Catatan: bukan berarti bakal ada update tiap 3 bulan ya, wkwkwk. Kurang lebih postingan ini jadi karena sangat banyak kegiatan-kegiatan "orientasi" yang aku alami dan sudah terlalu banyak bahan. Aku yakin nanti kegiatan perkuliahannya bakal membosankan dan mungkin saja bakal update 1x pertahun. Kamus: Maba = Mahasiswa Baru. Pacil = Fasilkom. Kutek = Kukusan Teknik (daerah di belakang UI) Kukel = Kukusan Kelurahan (daerah di belakang UI) Detos = Depok Town Square (Nama suatu pusat pembelajaan di Depok) kuis = ulangan PA = Pembimbing akademis (Paling mirip dengan "wali kelas" di SMA) KAMABA Singkatan dari Kegiatan Awal Mahasiswa Baru. KAMABA  dibagi me

Mengikuti ICPC 2019 Bagian 1: Jakarta Regional

Halo, sudah lama tidak berjumpa! Semester ini aku terlalu banyak kegiatan jadi lupa ada blog ini. Jadi, liburan semester ini bakal ada banyak blog-blog yang bakal keluar ^_^. Kali ini, aku bakal nyeritain pengalamanku mengikuti ICPC lagi tahun ini. ICPC,  The International Collegiate Programming Contest  adalah lomba programming yang setiap tahun diadakan. Tentunya aku ikut lagi dong. Apalagi, sudah dibekali ilmu dari matkul TKTPL saat semester 2. Peminat CP di UI lumayan banyak, jadi diadakan seleksi untuk masuk tim intinya. Aku lolos :D. Pembentukan Tim Aku gak perlu mikirin mau ngetim siapa, karena komposisinya sudah ditentukan oleh Pak Denny. Aku dapat tim bareng Kak Norman dan Budi. Aku lumayan seneng dengan timku. Tahun lalu, aku ngetim Kak Norman juga jadi sudah tahu kemampuan masing-masing. Budi, aku sudah sering ketemu saat ngajar di pelatnas 2 dan pelatnas 3 dan skillnya jago, Aku mikirnya dia bakal ngecarry kita, hehe. Oh, kita kebagian regional Kuala Lumpur. Jad

Jurnal Fasilkom Semester 6: Konteks

Halo lagi, Ketemu lagi di blog semesteran ini. Kali ini aku mau ceritain gimana sih aku menjalani semester 6 di Fasilkom UI. Kondisinya masih pandemi, jadi kegiatan perkuliahan masih full online. Pada semester ini, kalian akan ketemu dengan satu-satunya matkul di Fasilkom yang kuambil di tiga semester . Sebelum-sebelumnya kegiatanku selalu sibuk yah :| Semester 3 ngambil 22 sks + 3 organisasi + asdos Semester 4 ngambil 22 sks + PIC compfest + asdos Semester 5 ngambil 17 sks + part-time Bareksa + asdos Waduh semester 6 sibuk apa aja nih? -_-, semester 6 ini aku: gak ngambil sks banyak (dibawah 20) gak part-time/full-time gak ikut kepanitiaan lagi, apalagi jadi ketuanya gak ikut kegiatan external "Wah Galang mau santai?" tujuannya begitu :( Pingin sekali-sekali ngerasain gabut jadi aku menghindari hal-hal yang potensi sibuk, aku bahkan resign dari part-timeku karena ingin fokus akademis.  Sayangnya sepertinya aku magnet kesibukan, berasa gak tenang aja kalau ada waktu gabut. Ba