Selasa, 12 Agustus 2014

A Detailed Version of My First PJJ

*Saya tidak tahu apakah membuat judul yang menggabungkan Bahasa Inggris dengan singkatan di Bahasa Indonesia itu diperbolehkan atau tidak, tapi biarlah. BTW, PJJ itu Pelatihan Jarak Jauh

Hari ini sudah tepat seminggu PJJ OSN Informatika tahun ini berjalan. Entah ini cuma pikiran saya, atau karena saya yang tidak bisa membandingkan dengan PJJ tahun lalu karena saya dengan pintarnya terlambat masuk grup PJJ tahun lalu (saya baru masuk grup tersebut pada Pelatnas 1 karena ketololan saya sendiri), nampaknya pertanyaan di grup belum banyak dan agresif. Beberapa juga kurang aktif dalam mengerjakannya, tapi yah positive thinking saja lah, mungkin mereka aktif berlatih di suatu tempat :) Untuk menyalurkan keinginan menulis dan mengisi waktu karena nggak bisa tidur, saya mau nulis tentang PJJ saya tahun lalu, dengan sedikit mendetail. Mungkin post ini tidak terlalu menarik,lol. Post ini saya buat untuk mengingatkan saya di masa depan "How awful i code back then" :p

Tahun lalu, sehari sebelum libur puasa dimulai, muncul email yang menginformasikan PJJ dari ketua tahun lalu, yaitu Salvian a.k.a. Minato waktu itu. Kenapa Minato? Karena tahun lalu temanya Naruto :p Siangnya, saya disms oleh Supervisor (Orang yang membantu kita dalam PJJ) saya, yaitu Zetsu. Masalah identitas aslinya gak saya bahas di sini :p Oiya, sebelum PJJ ini, saya sudah mempelajari basic dari Pascal dan C++ , hanya saja sangat basic seperti input dan output serta operasi matematika. Bahkan library C++ yang saya tau hanya iostream, iomanip, dan cmath. Sebelum PJJ ini dimulai,omong-omong saya sudah sampai Bab 3, di mana saya stuck di soal median (soal yang banyak dijebol sort STL).

Oiya, buat peserta PJJ tahun ini yang mungkin nyasar ke post ini, PJJ tahun lalu sistemnya sedikit berbeda dengan tahun ini. Tahun lalu, kita tidak bisa melihat progress peserta lain lewat scoreboard, karena tidak lewat kontes, melainkan hanya mengerjakan training gate. Tahun lalu kami hanya bisa melihat progress lewat google docs yang diupdate Minato di waktu tertentu, sekitaran seminggu setelah PJJ berjalan 2 minggu kalau tidak salah. Pada awalnya, saya bertekad untuk menyelesaikan PJJ sampai Bab 8.

Setelah bertanya ini-itu dengan Zetsu, saya baru tau kalau cin/cout sangat lambat, terutama kalau datanya banyak (actually ada cara mempercepat cin). Alhasil, saya diberi tau kalau ada cara baca input yang lebih cepat, yaitu scanf. Setelah mengganti dengan scanf dan printf, saya akhirnya AC di soal itu! Pelajaran : ada berbagai cara dalam I/O.

Kemudian, saya melanjutkan perjalanan di Bab 3 tanpa kendala yang berarti, mungkin karena soalnya tentang ad-hoc dan math. Setelah itu saya sampai di Bab 4, Complete Search. Untuk bagian awal-pertengahan Bab ini, saya tidak terlalu mengalami kendala, kecuali ada yang saya hardcode serta entah bagaimana, soal yang kadang ditemui RTE jika diserang dengan DFS oleh orang lain bisa saya AC-kan dengan DFS :) Bab 4 mulai terasa berat ketika sudah memasuki 4C dan 4D. Saya ingat saya pernah stuck di beberapa soal yang bersangkutan, dan itu membuat saya frustasi. Alhasil, ketika soal-soal tersebut saya AC-kan, beberapa saya save di komputer dengan format nama_soal + kata_kasar, seperti maze k*****t dan pesta bebek a*u. Filenya masih saya save di komputer saya sampai detik ini :p Dan ironisnya, code yang bersangkutan harusnya tidak AC. Pelajaran : Jangan ngumpat dan kepedean kalo udah AC.

Memasuki Bab 5, saya rasa saya merasa tertekan. Saya nyaris tidak mengerti cara mengerjakan soal-soal di bab tersebut walaupun sudah diberi link referensi untuk mempelajari teknik-teknik di Bab itu. Alhasil, saya merasa frustasi sekali sampai nangis.Ya, nangis. Kalau saya lihat sekarang, saya setahun yang lalu tempaknya parah sekali ._. Karena kasihan lihat saya stres, Bapak saya nawarin untuk nanya ke pegawai  IT kantor perusahaan Bapak saya kerja. Alhasil, saya malah nambah bikin bingung orang-orang yang bersangkutan, walaupun setidaknya berdiskusi dengan mereka membuat saya merasa lebih baik. Pelajaran : jangan nanya CP ke pekerja yang dulu gak nyentuh CP. Kasihan, kerjaannya tambah banyak.

Karena tidak tahu tentang grup PJJ tahun lalu, saya tidak bisa terlalu memperkirakan progress peserta lain. Sebenarnya ini tidak terlalu penting, tapi karena saya kepo, saya pengen tau progress peserta lain :p Pada saat google docs yang berisi progress peserta diupdate oleh Salvian, sejujurnya saya merasa sedikit lega, karena progress saya bisa dilihat tidak terlalu buruk. Walaupun mungkin saja peserta lain sebenarnya mengamuk di OJ lain :p

Setelah mengAC-kan beberapa soal (dengan cara yang seharusnya gak AC), saya stuck di satu soal lagi, waktu itu tentang binary search. Yang ini benar-benar bikin frustasi, karena hanya salah satu TC, dan saya merasa sangat yakin kalau algo saya kali ini benar. Setelah nanya sama Zetsu, dia juga tidak terlalu melihat masalah di algo saya. Habis itu, karena range low dan high yang dipakai Zetsu berbeda, saya coba ikuti. Bedanya sebenarnya cuma low nya lebih kecil dan high nya lebih besar. Setelah saya ganti seperti itu, ternyata AC! Pelajaran : ngasih low sama high jangan tanggung-tanggung.

Setelah itu, sisa dari Bab 5 tidak terlalu sulit (Sort STL FTW!), tapi lucunya ada satu soal sort N log N yang saya AC-kan dengan insertion sort yang dioptimasi, karena saya tidak tahu kalau kita bisa mendefinisikan compare function pada sort STL. Setelah itu, masuk Bab 6, diawali dengan greedy. Greedy pada bab itu cukup straight-forward, hanya saja saya bermasalah pada soal yang memerlukan sort, dan datanya berbentuk pair. Pada saat itu saya tidak tahu kalau ada yang namanya pair di C++, serta insertion sort optimasi saya TLE. Alhasil, saya belajar sort N log N manual, yang saya pelajari merge sort (sampai detik ini saya belum pernah bikin quick sort). Setelah itu, akhirnya AC. Pelajaran : kadang, kepepet itu diperlukan untuk belajar.

Kemudian, saya memasuki Bab paradigma penyelesaian masalah yang mungkin masih terkesan mengerikan bagi sebagian besar orang (saya sendiri juga menganggapnya sulit), yaitu dynamic programming yang biasa kita sebut DP. Pada Bab itu, sebenarnya soal DP yang ada hanya persoalan DP yang klasik yang bisa gampang kita temui referensinya di internet. Walaupun banyak referensinya, sejujurnya waktu itu saya benar-benar tak berkutik dalam mengerjakan soal-soalnya, melihat contoh source codenya saja pusing :( Karena saya sudah merasa stres dari Bab sebelumnya, saya akhirnya memutuskan untuk menikmati libur saya dahulu (dan akhirnya kebablasan menikmatinya). Pada saat itu, karena masih merasa harus tetap berlatih, saya mencoba mengerjakan soal-soal di UVa. Dibilang berlatih juga, soal-soal yang saya kerjakan hanya soal-soal yang mudah, jadi gak bisa dianggap berlatih juga :p

Tak lama setelah itu, kami diinfokan untuk mengikuti kontes Pra-OSN 1. Saya tidak pernah ikut kontes sebelumnya, jadi yaa kalau hasilnya bagus Alhamdulillah, kalau tidak ya sudah. Begitu kontes dimulai, saya skimming, mencoba mencari soal yang doable. Akhirnya saya memulai kontes dengan mencoba mengerjakan sesuatu yang ada hubungannya dengan prefix sum. Saat saya submit, saya merasa senang karena tulisannya Accepted! But wait, kenapa ada kolom nilai resmi di sebelah kanan? Ketika saya buka, ada tulisan "token". Karena penasaran, saya coba men-token solusi saya yang tadi, dan ternyata nilainya hanya 45! Well, setidaknya saya tahunya pas kontes, bukan after contest :/ Pelajaran : Kalau gak tau dicoba, siapa tau membantu.

Setelah itu, saya mencoba soal interaksinya. Karena tidak terlalu mendapat ide, jadinya hanya bikin bruteforce yang hanya mendapat nilai 20 :/ Kemudian saya melihat satu soal yang menurut saya cukup menarik (versi lebih simple dari UVa - The Bridges of Kolsberg). Firasat saya itu bisa dikerjakan dengan DP, tapi entah bagaimana caranya :( Akhirnya saya ngutak-ngatik, nyoba-nyoba semua cara yang kepikiran, sampai akhirnya entah bagaimana, saya sampai ke DP dengan kompleksitas O(N^2). Karena di TC sample dan TC yang saya buat hasilnya sama, akhirnya saya submit. Deg-degan, saya pakai token di soal itu. Ternyata 100! Jujur saya senang banget pas itu, karena berhasil ngerjain soal DP :'D #berasaganteng #ohemangganteng Setelah itu, scoreboard resmi bisa dilihat. Saya cukup senang karena posisi saya berada di posisi perak, walaupun peraknya cukup di bawah :p

Jangan kepedean kayak orang ini

Karena Pra-OSN 1 tidak terlalu banyak yang ikut, dari Pra-OSN yang rencananya hanya 2 kontes akhirnya jadi 3 kontes. Pada Pra-OSN 2, performance saya bisa dibilang menurun. Seperti biasa, skimming dulu semua soal. Kemudian, saya mencoba mengerjakan soal ad-hoc yang berhubungan dengan binary. Lolos TC sample, saya coba membuat TC sendiri yang angkanya rada besar. Saya kaget karena outputnya sesuatu yang tidak mungkin :/ Akhirnya, nyoba utak-atik sana-sini baru akhirnya yakin benar, dan voila, 100. Pelajaran : rajin-rajin bikin TC. Kemudian, saya nyampah yang masih bermartabat di satu soal lainnya dengan menggunakan prefix sum, dapet 70. Lalu saya ketemu soal yang menurut saya bisa pake brute force, hanya saja karena terkendala dengan format inputnya saya cukup lama mencobanya. Sisa waktu sudah tipis, saya submit. Hasilnya 0 besar! Janggal rasanya karena harusnya separah-parahnya TLE, walaupun itu juga gak mungkin karena constraint kecil. Ternyata saya buat blunder parah yang biasa terjadi : Salah ngerti soal! Buru-buru saya edit beberapa bagian, mau submit tapi apadaya internet lambat :'( Akhirnya telat, kontes sudah berakhir :'( Btw, code itu AC waktu ada kayak repeating kontes-kontes Pra-OSN :'(  

 
Ingat, jangan kepedean


Pelajaran : Pahami soal sampai bego. Kontes ini posisi turun ke perunggu, tapi yasudahlah, salah saya juga :/ Habis itu saya potong rambut #random

Kontes ke-3 diadakan di hari keberangkatan saya buat Pelatda di LOPI. Akan tetapi, jika saya ikut bersama dinas propinsi buat perginya, waktu kontesnya bisa kepotong perjalanan ke Jakarta. Alhasil, saya bela-belain pergi duluan sama Bapak saya :p Kontes ke-3 ini menurut saya lebih manusiawi dibanding kontes lainnya, mungkin karena ada soal yang bisa dianggap bonus? :/ Saya memulai kontes dengan mengerjakan satu soal dengan brute force, dapet 40. Soal itu sebenarnya bisa dikerjakan dengan teknik Meet in Middle, yang baru saya ketahui pas Pelatnas :/ Setelah itu saya mencoba mengerjakan soal brute force (atau ad-hoc?) nya yang lain. Setelah ngebug sana-sini dan salah ngerti soal, akhirnya 100. Kemudian, saya ngerjain soal yang menurut saya jadi simple kalau sudah disort. Pertama submit, dapet 50an. Oh iya ada yang salah diinisialisasi ._. Edit dikit, 100. Kemudian saya bikin brute force di satu soal, expectednya TLE, tapi tiba-tiba nilainya 100! Sontak saya kaget, tapi itu tidak bertahan lama, karena akhirnya ditambahi TC dan rejudge, sehingga nilai turun jadi 30 :v Kontes selesai, dan posisi saya kembali perak bontot. Setidaknya rangkaian PJJ dan kontes ini bisa memotivasi saya untuk membawa pulang medali,mengingat sebelumnya saya sangat frustasi karena merasa tidak punya peluang mendapatkan medali. Setelah itu, Pelatda dimulai, kemudian OSN yang ceritanya bisa dilihat juga di post saya sebelum-sebelumnya :)

Sebelum menutup, saya mau nambahin beberapa fakta gak penting, yang mungkin saya update setiap kali saya ingat yang baru :p

My reaction when i see my old code :
  • Dafuq i was thinking back then
  • Dafuq, jelek banget, gak rapi (sekarang masih jelek juga sih..)
  • Dafuq, ini harusnya gak AC
Achievement janggal :
  • AC counting sort dengan sort STL(banyak yang gini juga sih)
  • Hardcode soal yang simple jika pakai rekursi
  • AC soal yang harusnya pake BFS menggunakan DFS
  • AC soal modular exponentiation dengan pow di Pascal yang dioptimasi
  • AC soal binary search tanpa binary search beneran
  • AC soal merge/quick sort dengan insertion sort
  • Vector,vector everywhere
Categories: ,

4 komentar:

  1. wah, berwarna XD , kita ga beda jauh ceritanya , cm berbeda ending, semangat!! , gogetIOImedal XD

    BalasHapus
    Balasan
    1. Oya? :) thanks ya :D btw itu lu bikin blog tentang CP juga?

      Hapus
  2. Yg mana? Yg rombongan itu ya? ~_~ lupakan.. itu cm iseng koq wkwk , btw, menurutmu gmn persaingan taun ini ? Lebih ketat atw longgar? :v

    BalasHapus
    Balasan
    1. Belum terlalu keliatan.Tapi Pra-OSN tadi bisa dibilang ajang pembantaian. :/

      Hapus