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

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

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.

Here are the problemset and analysis for ACM-ICPC 2010 Jakarta.

ACM-ICPC 2010 Jakarta – Problem Set (405 KB)

These problems will be available on Live Archieve so you could practice there.

You can see the scoreboard of ACM-ICPC 2010 Jakarta here.

Here are the authors of each problem:

 Problem Author A Worst Locations Ilham Winata Kurnia B Counting BST Suhendry Effendy C Playing With Stones Teddy Mantoro D Arm Wrestling Tournament Eko Wibowo E Lightning Energy Report Felix Halim F Transitive Closure Ilham Winata Kurnia G Just Sum It Timotius Sakti H Serial Numbers Ryan Leonel Somali I Romantic Date Eko Wibowo J Fire Drill Gunawan

Thanks to all authors who have helped me prepare all the problemset, solutions and testdata. Thanks to Felix Halim who has helped me write alternate solutions for many problems and also thanks to Timotius Sakti who have written Java solutions for all problems.

Yohooooo! cepat ya write-up nya selesai, gw keren B-). Kali ini yang ngeganggu kehidupan gw di YM makin banyak: Felix Halim, Eko Wibowo, Evan Leonardi, Ashar Fuadi, Ryan Leonel, Petruk Risan dan Ilham. Untung kelar, jadi bisa menikmati hidup damai untuk beberapa saat.

Eko Wibowo juga udah ngeblog tentang INC 2010, silakan liat di sini.

Soal dan pembahasan solusi bisa dilihat di sini:

Sedikit cerita tentang babak final bisa dibaca di sini: cerita

Scoreboard bisa dilihat di sini: scoreboard

BNPCHS 2010 Final Round – Problemset (PDF – 468KB)

Pembahasan solusi bisa dilihat di sini:

Sedikit cerita tentang babak final bisa dibaca di sini: cerita