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 -_-)

Stagnasi

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

Barusan baca kultwit dari @al_Uyeah tentang hijrahnya hati seseorang. Senang mendengarnya?

Sayang sekali hijrahnya justru menjauhi hidayah, bukan malah mendekatinya.

Hanya karena satu hal...

Yah, tidak perlu disebutkan lah ya. Baca sendiri saja.

Mungkin ini kenapa Nabi selalu menganjurkan kita berdoa

“Yaa muqollibal qulub tsabbit qolbi ‘ala diinik" (Wahai Zat yang membolak-balikkan hati teguhkanlah hatiku di atas agama-Mu) (HR Tirmidzi, Ahmad, Hakim)

Istiqamah itu berat.. mungkin lebih berat daripada memulainya itu sendiri.
Kalau memulai itu godaannya ya dan tidak,
maka istiqamah godaannya sekarang atau nanti,
nanti-nanti-nanti terus.... akhirnya lupa
kalau lupa-lupa-lupa terus... akhirnya malas
kalau malas berat mau mulai lagi,
dan karena sudah pernah melakukan tingkat kemalasannya bakal lebih tinggi dari sebelum memulai pertama kali.

Jadi, kalau sudah dimulai, jaga terus dengan kebiasaan. Eman kan kalau sudah dilakukan, terus hanya jadi kenangan manis
#notetomyself

Ironi

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

Baik, sekali lagi pemuda ini tidak tahu harus membunuh waktunya dengan cara apa. Kemarin saya mendengarkan sebuah cerita bagus tentang arti pengorbanan. Antara seorang anak -yang akan tumbuh dewasa- dan sebatang pohon.

Ada seorang anak tinggal di rumah tua milik ayahnya. Di depan rumah tersebut terdapatlah sebatang pohon apel yang sudah agak tua. Dia selalu bermain-main di bawah pohon itu. Seringkali anak itu pun berbicara dengan si pohon tentang cita-citanya menjadi seorang penyair. 

Setelah beberapa tahun anak tersebut telah tumbuh remaja. Keluarganya yang cukup sederhana membuatnya tidak memiliki tabungan yang banyak. Suatu hari, dia ingin memberikan hadiah kepada wanita yang dicintainya. 

"Aku ingin membelikan sesuatu untuknya tapi aku tidak memliki uang yang cukup untuk itu", keluhnya pada si pohon. 

"Oh, aku memiliki banyak buah yang segar. Kau bisa mengambil semuanya. Jual sebagian untuk membeli kado yang indah, dan berikan sisanya agar dia bisa memakannya", kata si pohon kepada pemuda. 

"Benarkah? Terimakasih pohon. Aku berutang budi padamu", sang pemuda lalu bergegas menuju pasar untuk menjual apel-apel itu. 

Pengorbanan pohon itu berbuah manis. Pemuda itu pu mendapatkan hati wanita pujaannya dan akan menikahinya. Sementara itu, dia belum memiliki rumah untuk tempat tinggal keluarganya kelak. Dia pun kembali mengadu pada si pohon. 

"Pohon, aku akan menikah. Kini aku harus memliki rumah sendiri. Tapi pekerjaanku sebagai penyair tidak banyak menghasilkan uang untuk membeli sebuah rumah." 

"Jangan khawatir, aku mungkin tidak bisa memberikan tempat tinggal. Tapi kau bisa menebangku daan membuat rumah dari kayu-kayuku", kata sang pohon kepada pemuda tanpa ragu-ragu. 

"Apakah tidak apa-apa jika aku menebangmu?" 

"Benar, tidak apa-apa. Batangku terlalu tua untuk hidup lebih lama. Akan lebih berguna bagimu jika batang ini engkau pergunakan sebagai bahan rumahmu nanti" 

Sang pemuda itupun bergegas mengambil kapak dan menebang pohon itu, lalu membangun rumah dari kayunya.

Inilah ironi hidup. Kadang kita melupakan orang yang benar-benar mencintai kita dengan tulus dan malah memperhatikan orang lain yang sebenarnya tidak begitu memperhatikan kita.

Cobalah sesekali kita tengok orang tua kita. Orang yang telah mempertaruhkan semua yang dimilikinya, bahkan nyawanya, atau bahkan mempertaruhkan semua yang belum dimilikinya sekalipun -semisal berkorban perasaan yang akan dibahas kemudian :)). Pernahkah kita memikirkan mereka, walau hanya sedetik dalam putaran kehidupan kita?

Sedetik, iya. Sejam, mungkin iya. Sehari penuh? Belum tentu.

Jadi apakah pantas bagi kita berbicara sok bijaksana tentang cinta padahal tidakkah kita tahu itu kecuali hanya sedikit dan dangkal sekali?

وَٱعۡبُدُواْ ٱللَّهَ وَلَا تُشۡرِكُواْ بِهِۦ شَيۡـًٔ۬ا‌ۖ وَبِٱلۡوَٲلِدَيۡنِ إِحۡسَـٰنً۬ا

Sembahlah Allah dan janganlah kamu mempersekutukan-Nya dengan sesuatu pun. Dan berbuat baiklah kepada kedua orang tua (An Nisa: 36)

Dinamika

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

Semoga apa yang ditulis benar-benar bermanfaat karena sekali lagi, setelah kesekian kalinya saya membuang waktu berharga saya untuk menulis di page sampah ini.

------------------------------------------------------------------------------------------------------------

Mungkin yang telah membaca beberapa post saya belakangan pasti tahu bahwa ada sesuatu yang aneh terjadi pada diri saya, tapi semoga tidak mengganggu aktivitas ramadhan kali ini.

Sedikit mengutip kata seorang kawan di blognya

We all grow up. As soon as we get older and no longer enjoyed things we’ve enjoyed as kids, we’ll find other kinds of enjoyment. Life’s difficult, it is, but at least not impossible to live

Hal sederhana ini yang sempat membuat keputusanku hampir salah, walaupun sebenarnya bukan alasan ini yang mendasari keputusan itu diambil. Memang hidup tak akan semulus kisah seorang anak kecil, atau malah seperti dongeng "happily ever after", harus ada dinamika. Seperti melodi, ada saatnya lagu itu diberi sentuhan forte yang keras, cepat, dan memburu, atau piano yang lembut dan mendayu. Pengalamanlah yang akan memberi kejutan untuk kita, setiap warna kehidupan dalam dinamika yang menerpa.

Jadi janganlah takut akan kehidupanmu, takutlah jika kau tidak mampu melangkah karena dirimu sendiri.
Sekian

*2*

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

Kebahagiaan tidak diperoleh semata dengan membahagiakan diri sendiri, tapi juga dengan membahagiakan orang yang tidak pernah membahagiakan kita

- random -

Melancholic Rhapsody

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

Bermula saat impian itu muncul,.. jauh sebelum hasil UN diumumkan

Sebelum apapun aku lewati, aku menemukannya

Ketika satu tahapan terlewati, aku menemukan satu lagi

Ketika satu tahapan terlewati lagi, aku menemukan satu lagi

Dan ketika tahapan terakhir aku lewati,..

aku tidak menemukan itu..

bukan itu yang kutemukan..

setan.. mungkin itu yang kutemukan

setidaknya menurut orang-orang yang telah mengenalnya dahulu

Setan yang menarik, kukatakan itu pada diriku

Saat yang cukup lama untuk tidak melihat setan itu lagi

Setelah cukup lama itu, suatu ketidaktahuan memaksaku melihatnya

bertemu dan bercengkrama untuk beberapa kali

Cukup banyak untuk membuatku berpikir ulang..

apakah ini yang namanya setan?

tidakkah ini malaikat yang sebenarnya?

Malaikat.. atau setan?

Hahaha konyol ya

seperti judul buku karangan penulis misterius Dan Brown

Tapi itu nyata..

angel and demon..

dua sisi yang berbeda tapi satu

dua sisi itu kini benar-benar kutemui

Menyiksa pikiran dan ragaku

Sedikitpun tidak berkutik

Aku berharap pada Rabbku

Ya Rabb yang mengatur masa lalu

jadikanlah masa laluku yang kelam ini

menjadi pengingat untuk terus berbenah

bukan sebagai lubang

yang terus menahanku disini

Ya Rabb yang mengatur masa kini

berikanlah kekuatan padaku untuk berdiri

untuk melanjutkan langkahku dijalanMu

jangan biarkan aku jatuh kembali

dalam ilusi ini

Ya Rabb yang mengatur masa depan

tetapkanlah aku dengan ketetapan yang mudah

dan berikan petunjuk untuk menemukannya

berilah juga kelapangan hati dan kekuatan

dalam menerima keputusanMu

Engkaulah sebaik-baik tempat mengadu dan memohon

Rindu

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

Waktu memang dapat melenakan kita. Banyak waktu luang kadang membuat kita melupakan kewajiban kita. Banyak juga waktu yang berkesan yang membuat kita lupa akan diri sendiri. Menyisakan banyak kenangan yang membuat kita merasa diri kita berarti. Bisa juga membuat diri kita lebih terhina. Atau bahkan menghancurkan dan merusak diri kita sepenuhnya.

Sedikit membaca postingan seorang teman (atau mbak) tentang kerinduan, membuatku sedikit merinding. Salah satu yang ditulis di sana benar-benar melambangkan diriku saat ini, tenggelam dalam kerinduan tak berujung.

Kerinduan yang menyiksa.. bukan karena harap.. atau ketakutan.. 

Hanya kerinduan.. tidak lebih

Sedikit menahanku untuk tidak melangkahkan kaki lebih jauh lagi

Sedikit aneh buatku. Tidak pernah kurasakan rindu yang berat.. tanpa harapan.

Mungkin harusnya lebih gampang karena tanpa harapan..

Nyatanya tidak demikian..

Jadi?

Curiousity

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

Sebenarnya kupikir ini kurang layak ditulis di kertas ini, karena memang tulisan disini kuniatkan untuk sharing ilmu. Tidak apa-apa. Semoga saja orang lain yang membaca ini, khususnya yang senasib denganku dapat iluminasi pencerahan lah..

So the story begins by myself, who is curious to the every unique thing, and also whatever (or whoever) called "thing". Mungkin berbahaya juga kalau selalu tertarik pada hal-hal aneh-aneh. Iya kalau baik, kalau buruk kan... malah jadi masalah baru.

Jadi to the point saja, curiousity always kills itu bisa saja memang benar. Karena sekarang jadi susah bangkit.

Sudah lama jatuh, lukanya memang sembuh, terus tertimpa beton.

Mungkin karena itu juga Allah ingin memberiku jalan keluar dari masalah ini,.. justru dengan masalah-masalah  baru. Dia ingin aku menjadi lebih tegas dan kuat dalam menerima tiap masalah. Bisa dengan tegas memutuskan, yang benar dan yang salah, yang patut diterima dan harus ditolak, yang harus diteruskan dan harus ditinggalkan.

Semoga pengalaman ini bisa jadi bekal abadiku.

Bismillah, AKAN KUTERUSKAN PERJUANGANKU!!