Wednesday, October 26, 2011

SRM522 Div1 Level1 250 Problem

Given a board consisting of n(n>=2) cells, each marked with either an 'A' or 'B', Alice and Bob alternatively place coins on some continuous empty cells, with the restriction that at least one cell must be left empty. When there is only one cell left, Alice wins if that cell is marked with 'A' and Bob wins otherwise.

First of all, if at least one end is marked with an 'A', then Alice wins. Without loss of generality, suppose the board is of the form "A??...?"('?' means empty cells marked with 'A' or 'B' arbitrarily). Alice can obtain "ACC...C"('C' means covered by a coin) in one step and win.

Then what if the board is of the form "B??...?B"?
If Alice covered either end with a coin, again without loss of generality, the board becomes "CC...CB" or "CC...C??..?B". Bob wins immediately for the former, by covering all other empty cells except the rightmost 'B' for the latter. So Alice would have to choose "B??...?CC...C??...?B" if she wanted to win.
Now let's consider a simpler situation, "B??...?CC...CB". (I)If it is now Bob's turn, he only needs to cover all the empty cells on the left and wins. (II)If it is now Alice's turn, she has up to four choices. If she choose to cover the rightmost 'B' or either end of the empty cells on the left, Bob can obviously win. Then again she has to choose to make the board of the form "B??...?CC...C??...?CC...CB". If Bob covers all empty cells of the second interval, then we reach the same configuration except that the number of empty cells decreases. So we can prove by induction that no matter whose turn is it, the winner would be Bob if the board is of the form "B??...?CC...CB".
So let's return to "B??...?CC...C??...?B". If the second interval is empty, the it corresponds to (I). Otherwise, Bob could cover all empty cells on the right except the rightmost 'B', and now it corresponds to (II). Either way, Bob wins.

So all we have to do is to check the two cells on both ends.

I code a bit mask DP during the contest. Finding patterns and proving them is still a hard task for me. Need more exercise.