ACM-ICPC Regional Asia Jakarta Site 2013

بسم الله الرحمن الرحيم

Baru beberapa hari yang lalu, aku merasakan udara panas khas kota pesisir. Udara panas yang bikin kangen Surabaya tapi gak kangen gerahnya. 

Yoi, ACM-ICPC Jakarta. My first ICPC and first contest in college. 

Agak alay, tapi memang gak kebayang bisa bertandang di kompetisi selevel ini. Waktu penyisihan INC pun rasanya almost impossible bisa lolos ke regional. But,... Allah punya cara lain buat bikin aku baca buku Competitive Programming 3 yang dikasih Wisnu, buku saktinya anak TOKI. Kayak gini nih bukunya

Buku level internasional yang ditulis alumni TOKI, sekarang lecturer di NUS; 

waktu kontes sempet ketemu orangnya, satunya gede satunya kecil :v

Oh ya, perkenalkan dulu tim saya,  Wisnu Wisnu si bos tim (orang luar ga menerima nama tunggal, makanya ID Cardnya gitu), Ibrohim Kholilul Islam aka Oz sang master koding, dan sampah terakhir yang harusnya dibuang dari kelompok, saya sendiri !!

Seminggu sebelum berangkat buat belajar itu mepet banget... dan cuma sempet baca bab awal sampai Backtracking, mentok diterusin di hotel pun cuma dapet sampai DP (Dynamic Programming). Ya sudahlah, yang penting aku bisa solve 1 soal (hampir 2 soal benernya, cuma 'kurang beruntung' di memo jadi gak AC), dan total tim Oz dapet 3 solved!! Yeah!!!

dan hasilnya pun masih 34 dari 58 tim :''

Ini dokumentasi tim ITB saat trial session Rabu kemarin,

Nah, saya mau sharing aja sekalian bagi-bagi ilmu buat soal kemaren, utamanya yang sudah solve. Cekidot

A.    Number Assignment

Solved by : Afrizal

Bisa dibilang ini soal termudah di kontes. Kontestan diminta membagi beberapa integer dalam beberapa kelompok yang mana nilai total selisih maksimum dan minimum dalam satu grup menjadi paling kecil. Idenya dengan greedy approximation, yaitu mengelompokkan integer secara terurut lalu jika ketemu gap yang lumayan besar dipecah. Bisa dengan sort array lalu dicari beberapa beda terbesar sebagai batas antar grup. Total kompleksitas O(N log N).

C.    The Busiest City

(Almost) solved by : Ibrohim, Wisnu

Soal graph yang hampir solved -dan memang seharusnya bisa solved karena banyak yang solved disini- ini bisa dibilang agak repot. Tujuannya yaitu menentukan kota tersibuk (yang paling banyak dilewati oleh permutasi path 2 vertex). Idenya -yang belum beruntung dapet AC- yaitu menentukan vertex yang bersebelahan dengan edge yang terbanyak dapat dibuat extensionnya. Entah kenapa terjadi bug yang aneh di kode kami dan akhirnya dapet WA 3 kali.

D.   Power Plant

Solved by : Wisnu

Ini soal graph yang tergolong mudah, dan juga soal pertama yang kami solve -walaupun solusi yang A ketemu duluan. Inti soalnya yaitu menentukan biaya minimum dari pembangunan jalur transmisi listrik dari generator (vertex yang sudah ditandai) ke semua bangunan. Idenya yaitu mengelompokkan generator menjadi satu vertex, lalu dicari harga minimum spanning tree (MST). Pengelompokan generator dengan bitset (status 1/0) lalu dengan Prim MST dicari edges termurah terus membuat extensionnya. Total kompleksitas O(|E|+|V|).

F.       Pasti Pas!

Solved by : Ibrohim

Satu-satunya soal string processing di kontes kali ini idenya mudah, tapi agak susah diimplementasikan. Soal ini bercerita tentang string yang bukan palindrom, tapi bisa dipecah menjadi beberapa substring, yang masing-masing substring jika dianggap satu komponen (atau dianggap satu simbol) string utamanya jadi palindrom. Contohnya, “PastiPas”. Jika “pas” kita misalkan “x” dan “ti” kita misalkan “y”, maka “pastipas” menjadi “xyx” yang merupakan palindrom. Kita diminta menentukan pengelompokan terbanyak yang mungkin agar string yang diberikan menjadi palindrom. Ide pertama yang terpikir yaitu secara naïf memecah substring yang dianggap sama, lalu diselesikan dengan rekursif. Solusi ini jelas mendapat verdict TLE. Lalu kami coba optimisasi dengan tidak memecah secara langsung, tapi mengecek per karakter, lalu diselesaikan secara rekursif. Dan akhirnya dapat AC setelah gagal 4 kali. Total kompleksitas O(|S|² log|S|).

G.     Horrible Quiz

(Almost) solved by : Afrizal

Soal ini pertama terlihat susah karena melibatkan teori peluang. Awalnya aku pikir ini bakal diselesaikan dengan kombinatorika. Setelah berpikir agak lama, aku menemukan stage dalam penyelesaiannya yang merupakan ciri soal DP! Jadi, soal ini meminta kita menentukan nilai terendah yang dapat dicapai dalam ujian, jika diberikan peluang kita menjawab benar dan salah dengan kemampuan sendiri untuk tiap soal (otomatis jika jumlahnya kurang dari 100% sisanya peluang kita minta bantuan dalam soal itu), jumlah maksimum soal salah yang mungkin diberikan oleh yang kita mintai bantuan (anggap saja kita pake joki pas ujian :v). Kita bisa selesaikan dengan DP 2D dengan jumlah soal salah maksimum sebagai constraint-nya, dan jumlah soal sebagai stagenya. Ambil nilai minimum dari nilai yang dicapai pada stage sebelumnya jika soal dari joki ternyata benar ((C-W+H)%*nilai sebelumnya) dan nilai yang dicapai pada stage sebelumnya jika soal dari joki ternyata salah ((C-W-H)%*nilai sebelumnya). Lalu dicari nilai maksimum pada stage terakhir untuk semua kemungkinan kesalahan yang diberikan joki pada kita. Waktu case testing sebenarnya sudah hampir benar, tapi entah kenapa masih ada bug dan waktu yang makin menipis memaksa kami untuk menyerah dalam 1 WA.

Untuk pembahasan lebih rinci silahkan merujuk ke blog pak Suhendry yang jauh lebih jago dari kami. Semoga bermanfaat. Terima kasih

untitled

بسم الله الرحمن الرحيم

Menjadi pion catur yang terus maju, itulah ibarat aku. Setiap pijakanku adalah belajar dan berlatih. Terus maju, menapaki kotak-kotak baru dan menambah ilmu.
Jalanku adalah panjang dan berliku, sementara langkahku hanya mampu satu demi satu. Tapi tekadku tidak pernah ragu.
Bahkan jika nanti aku terkalahkan takdir, akan ku pastikan pengorbanan itu membuka jalan untuk penerusku.
Aku bukanlah pemimpin terbesar, bukan manusia terhebat. Tapi pasti kan kutulis kebajikan-kebajikan di atas pasir.
Agar angin keikhlasan menerbangkannya jauh dari ingatan. Agar ia terhapus, menyebar bersama butir pasir ketulusan.
Karena aku bukanlah apa-apa melainkan seorang hamba.
Dengan nama Tuhanku, aku memulai perjuangan ini.

-2010-

Classic

بسم الله الرحمن الرحيم

Sudah lupa juga mulai suka hal-hal klasik sejak kapan.

Tapi in my opinion barang-barang klasik itu kadang lebih mengena daripada barang-barang kontemporer.

Bukan gak bagus.. ga feel aja

Saya jadi ingat quote

"Semua yang disampaikan dari hati pasti sampai juga ke hati, yang cuma dari mulut mentok cuma ke kuping, trus keluar kuping satunya"

Quote random tapi muasuk banget, PECAAAHHH *lak alay -_-

Jadi yang ingin aku sorot, yaah empati sudah mulai hilang dari karya-karya orang. Mentang-mentang semua serba komersiil trus buat ya seenaknya, pokoknya jadi bisa dijual oke no problem.

Plis bro, yang ingin dinikmati itu sebetulnya bukan permainan gitarmu yang memukau, atau suaramu yang memecah gunung, tapi feel yang kamu lontarkan ketika menyanyikan lagu itu.. itu yang gue cari meeen :))

Dan apresiasi yang sebenarnya juga bukan sekedar dari rating, dari selling copy, atau berapa kali download
Apresiasi sesungguhnya dari hati men. Kalo mau dapet yang dari hati, kasih dulu yang dari hati

Oke.. Sip

Angkot Day

بسم الله الرحمن الرحيم

Hari Jumat lalu, ada sebuah penelitian sosial yang menarik di Bandung. Namanya Angkot Day.

Ini adalah penelitian sosial yang berkaitan dengan keadaan transportasi di kota Bandung dan khususnya membahas masalah kemacetan dan hubungannya dengan angkutan umum, dalam hal ini angkot.

Bagi yang mau tahu silahkan tonton videonya dan baca selengkapnya di angkotday.info :)

Masalah utama dalam transportasi di Indonesia yaitu masih banyaknya penggunaan kendaraan pribadi di kota-kota besar seperti Jakarta, Surabaya, Bandung, Medan, dan kota lainnya. Dan masalah ini menjadi masalah serius khususnya di kota Bandung karena wilayahnya yang agak sempit dibandingkan kota-kota besar lain.

Sebenarnya akar permasalahan ini adalah, karena angkot dianggap tidak efisien, boros, dan tidak nyaman. Jauh dari angkutan umum yang ada di negara maju. Memang dengan pengelolaan yang baik, sarana transportasi umum tersebut dapat dikatakan menjadi moda transportasi andalan yang dapat mengurai kemacetan.

Nah, kita dapat lihat permasalahan ini dari dua persepsi berbeda,

Pertama, dari kacamata masyarakat

Menurut mereka, angkot dianggap tidak efisien karena harus naik angkot berbeda untuk menuju ke tempat tertentu karena trayek angkot yang terbatas. 

Selain itu ongkos naik angkot masih lebih mahal daripada naik kendaraan pribadi. Misal, angkot jarak 2 km seharga Rp 1500. Jika naik motor misalnya, anggap 1 liter bensin dapat habis untuk 15 km. Jadi biaya untuk konsumsi bensin sekitar 6000*2/50=Rp 240. Kurang dari seperlimanya, kan.

Ditambah lagi kebiasaan angkot yang suka ngetem dan berhenti sembarangan. Juga cara menyetir yang kadang ugal-ugalan, serta kondisi di dalam angkot sendiri seperti penumpang yang merokok sehingga mengganggu penumpang lain juga turut menyumbang makian pada angkot itu sendiri. 

Ini selain berdampak pada turunnya minat masyarakat pada angkot, juga memiliki pengaruh sosiologis yang besar pada sopir dan pengelola angkot. Kalau sudah dimaki orang akan malas dan sulit berbenah, kan.

Dan yang kedua, dari kacamata pengelola dan sopir angkot

Sebenernya, tuduhan yang dilancarkan oleh masyarakat pada angkot tidak sepenuhnya salah angkot. Memang, salah satu kesalahannya yaitu mengelola fasilitas publik secara privat/perseorangan. Karena itulah pengelola hanya mengedepankan mencari keuntungan daripada melakukan manajemen yang nyaman dan aman pada angkot.
Juga dalam pengelolaannya modal dan omzet yang dimiliki pengelola juga terbatas. Hal inilah yang menyebabkan fasilitas angkot tidak kunjung mengalami perbaikan, baik dalam hal sistem setoran, mobil angkutan, juga pengelolaannya.

Selain itu seperti yang telah disebutkan, faktor kepercayaan yang sudah menurun membuat pengelola enggan melakukan perbaikan. 

"Daripada sudah susah diperbaiki tapi tetep ga ada yang naik, mending ga usah"

Nah, karena ada perbedaan persepsi antar keduanya itulah ada hubungan yang pasif antara keduanya :

masyarakat menunggu angkot berbenah agar mau beralih ke angkot, sementara angkot sendiri menunggu masyarakat beralih agar ada modal untuk melakukan perbaikan.

Karena itulah harus ada yang menjembatani kedua kepentingan ini, dan telah diwujudkan dalam bentuk Angkot Day ini. Tujuan Angkot Day yaitu mencari tahu tingkat penggunaan angkot, sistem setoran, sekaligus mengkampanyekan angkot tertib, aman, dan nyaman (sekaligus gratis hehe :v) agar masyarakat dapat mengubah mindsetnya tentang angkot.

Lalu, apakah tujuan ini akan berhasil? Semoga

Integritas

بسم الله الرحمن الرحيم

Ini terjadi seminggu yang lalu. Pas lagi enak jalan ke tempat printing foto murah di daerah Tamansari (deket rektorat). Waktu itu libur dan saya apatis memang tidak ada kegiatan, jadi berkelilinglah saya di deket kampus hunting barang2 buat menuhin kosan.

Pas lewat belokan deket jembatan layang, saya lihat ada motor polisi. Biasa sih. Cuma yang tidak biasa adalah ketika saya lihat bungkus makanan yang dimakan si bapak terbang mendarat sempurna di atas trotoar. HEBAT!!! MARI TEPUK TANGAN!

Pertanyaannya : sebegitu parahnya kah, integritas di negara kita?

Jujur, saya masih bingung. Integritas di negri ini kenapa bisa jadi barang langka? Apa susahnya melangkah 3 sampai 5 meter demi perbaikan menyeluruh bangsa ini :)

Ayo budayakan pendidikan bebas korupsi !! (nyontek maksudnya -_-)