As mentioned in my previous post, here I will give several example of impartial game which turn out to be exactly equivalent to Nim Game.

Nimble
Given a line of squares labeled 0, 1, 2, …. Several coins are placed on some squares (it’s possible to have more than one coin on a single square). Two players take turns. One move consists of taking any one coin and moving it to any square to the left of it. It’s possible that the coin moved into a square already containing coins.

I’ll discuss a little bit about Nim Game. Felix said that he doesn’t understand about Nim Game so he asked me to write a blog. I don’t know whether he really doesn’t understand or he is just looking for a reason to make me write.

Nim is a two player combinatorial/mathematical game strategy. Given a number of piles which in each pile contains some numbers of stones. In each turn, player choose one pile and remove any number of stones (at least one) from that pile. In a normal play, player who cannot move is considered lose (ie., one who take the last stone is the winner). There is another variation where player who cannot move is considered as winning (misere play).

Few weeks ago I went to Kuala Lumpur to attend ACM-ICPC 2011 Kuala Lumpur hosted by IIUM (International Islamic University Malaysia). I was invited as a problem setter and judge. The invitation was addressed to my previous campus (BINUS), thus I represented BINUS/Jakarta/Indonesia in this ICPC.

Udah ada beberapa orang yang minta blog pembahasan soal ACM-ICPC INC 2011 yang barusan, tapi apa daya gw lagi ada kerjaan dan belum bisa buat. Paling cepat minggu depan, tapi kemungkinan besar masih dua-tiga minggu lagi setelah BNPC-HS 2011. Lagian gw juga harus nunggu Risan yang janji mau nulis pembahasan soal J (Messy Query) punya dia yang sepertinya memerlukan beberapa analisis yang cukup kompleks, dan Risan sendiri saat ini masih sibuk di Bandung untuk keperluan Pelatnas 1 TOKI dan minggu ini dia akan ke Kuala Lumpur untuk ACM-ICPC. Ya… ini emang bulan-bulan sibuk.

Lah terus ini post tentang apa? Di sini gw cuma mau post tentang cerita tentang pengalaman atau kejadian-kejadian unik yang gw alamin di INC kemarin aja. Mumpung masih segar dalam ingatan, kalau nunggu bulan depan udah keburu lupa. Nulis post ini cuma perlu waktu sekitar 1 jam (kalau pembahasan bisa satu hari). Tenang aja, pembahasan pasti dibuat, cuma ya minggu-minggu depan…

Babak penyisihan dari ACM-ICPC Indonesia National (Programming) Contest, atau yang biasa disebut INC, baru saja berlangsung pada hari Minggu, 23 Oktober 2011 yang lalu. INC 2011 adalah bagian dari rangkaian kegiatan ACM-ICPC 2011 (diakui oleh ACM sebagai salah satu kontes lokal ICPC), namun bukan sebagai kontes regional, sehingga tidak ada slot yang dialokasikan bagi tim pemenang untuk mengikuti ICPC World Final 2012 (untuk tim yang ingin mendapatkan kesempatan ini harus mengikuti ICPC Regional di kota/negara lain seperti Kuala Lumpur, Manila, dll).

Tahun sebelumnya Universitas Bina Nusantara dipercaya untuk menjadi host salah satu regional site ICPC (ICPC Jakarta), namun tahun ini direktur ICPC Asia menginginkan ICPC Jakarta dirotasi (“gantian”) dengan site-site lain, sehingga ICPC Jakarta tahun ini tidak ada (sambil berharap tahun depan kembali ada).

Babak final programming Compfest 2011 tingkat perguruan tinggi baru aja berlalu. Juara pertama diraih oleh ITB (Dongskar Pedongi – RevolutiO(N)), juara kedua oleh BINUS (Ketua Compfest), dan juara ketiga oleh UGM (ein).

Yang patut diperhatikan, juara keempat itu dari BINUS juga (Pelopor Compfest), isinya hanya 1 orang: Winardi Kurniawan, dia dikhianati dua anggota timnya (Panji Kharisma dan Eko Mirhard) :p. Tapi bersyukur juga Panji ga ikut, kalau Winardi sendiri AC 7, tapi kalau Winardi + Panji kayaknya jadi AC 5 [-(

Ok, di sini gw mau kasi pembahasan singkat tentang soal-soal yang keluar. IMO, soal-soalnya ga susah, tapi ga ada satupun tim yang solve semua soal (pada mentok di soal E).

Scoreboard bisa dilihat di sini (tapi sepertinya link ini ga permanen).

Here I want to explain something called segment array (I’m not sure whether the term is correct), a data structure that no better than segment tree but simpler to code. I learned this structure from my friend, Timotius Sakti, when he was still an undergraduate and preparing for ICPC.

I used this structure to solve problem H on Jollymoo 11 (a local “practice” contest at BINUS University). The problem was originated from Codeforces – Yandex Algorithm 2011 Round 1 Problem D, “Sum of Medians”, which can also be solved by segment tree.

Minggu, 29 Mei 2011 yang lalu barusan Jollymoo 11 berlalu. Tingkat kesulitan Jollymoo 11 adalah normal (bukan untuk divisi 2 seperti Jollymoo 10), jadi ada beberapa soal yang cukup menantang. Di sini gw mau bahas soal-soalnya, dan semoga bisa ngasi sedikit pencerahan buat yang ga bisa. Anyway, karena ini bukan kontes untuk divisi 2, maka beberapa penjelasan gw akan singkat banget, karena gw anggap trivial dan lu orang (harusnya) bisa.

Soal-soal Jollymoo 11 bisa dilihat di SINI.

Soal-soal kontes ini beberapa diambil dari arsip kontes-kontes lama (SRM, Codeforces, dll) yang diubah dan disiapkan, jadi gw ga ngambil credits apapun untuk soal-soal yang ada.

Seperti tahun-tahun sebelumnya Universitas Indonesia (UI) mengadakan event IT bernama Compfest yang di dalamnya berisi berbagai kegiatan dan perlombaan. Namun khusus tahun ini (semoga tahun-tahun berikutnya juga), Compfest juga mengadakan perlombaan di bidang programming (problem solving) untuk tingkat mahasiswa.

Babak penyisihan Compfest mahasiswa barusan berlalu, ada 5 soal, 4 mudah dan 1 “susah” (susah buat yang baru belajar). Kemarin gw dapat link scoreboardnya, tapi sekarang scoreboardnya udah berubah jadi untuk kategori SMA. Sepertinya link itu cuma temporer, jadi ga gw cantumin di sini (karena ntar bisa ilang juga). Hasilnya, sekitar 20an tim berhasil solve 4, tidak ada tim yang solve 5. Dari BINUS kalau ga salah ada 4 tim yang lolos ke final, dan ada satu tim veteran yang memalukan (termalas #1 + termalas #2 + manusia-normal) =.=

Dari kemarin gw ditanyain solusi soal D (soal yang ga ada yang bisa solve di kontes), jadi gw kepikiran untuk bikin write-up penyisihan Compfest mahasiswa yang barusan lewat. Soal D ini emang rada lain sendiri ngelihat soal-soal lain yang tingkat kesulitannya jauh banget sama soal D :P.

Soal penyisihan mahasiswa bisa dilihat di sini.

Jollymoo 10 yang dibuat khusus untuk pemula (divisi 2) baru saja berlalu dan gw mau bahas soal-soalnya di sini supaya bisa jadi bahan buat belajar. Yang bikin soal untuk Jollymoo 10 ini antara lain gw sendiri, Felix Perdana, Hutomo, Oscar Yuandinata dan Petrus Risan.

Soal-soalnya bisa dilihat di sini.