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...
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
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
In each move, you divide all piles, not only one