samiemad's blog

By samiemad, history, 8 years ago, In English

Today I was participating in 2012-2013, Samara SAU ACM ICPC Quarterfinal Qualification Contest , We solved 12/13 problems ^_^. The problems were very interesting. :D

The one I couldn't solve was "H — Game with the Stones", even though I had a bit more than 2 hours to think about it, I only got WA on test 16...

I will explain where I got so far and please tell me what I am doing wrong.

at first I came up with this pattern for a single pile: L, W, L, W, W, W, L, W, W, W, L, W, W, W, L...

for every x%4 =  = 1 we can split it to (x - 2, 2) which is a losing position for the opponent.

for every x%4 =  = 3 there is no way to get a winning position no matter how we split it.

for every even x we can split it to (x - 1, 1) or (x - 3, 3) to get the opponent to a losing position x - 1 or x - 3..

so win if X%4! = 3 and lose otherwise...

I then noticed that we only care about the 'longest' pile.. and I found what would be the length of the pile (the number of turns until it gets all 1s)

I found this pattern for the length of a pile: 0, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 7, 7, 8 ...

length(x) = x / 2 + (x%4! = 2)

finally I look for the largest winning pile and make sure that all the other piles can be finished before it, meaning that length((ai + 1) / 2) is less than length(W). (W is the largest winning pile and ai are all the other piles)

this is my code

anyone have an idea what I am doing wrong here? and/or how to solve this problem?

I always have rough time with game theory problems.. so I am trying to get a better understanding on how to think analyze and come up with the solution...

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

a position is losing position if and only if biggest pile is of form 2^k-1 for some k=1,2,3... try to prove it yourself.

hint for the proof:

it's sufficient to show that:

1- final positions are losing positions

2- from any losing position you can only go to winning positions

3- from any winning position you can go to at least one losing position

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

The answer doesn't just depend on the largest pile. For instance, consider two piles of size two.

This problem can be solved using the Sprague-Grundy theorem. Here's some readings: TopCoder Wikipedia