Example:

.oo. - > .o.. -> ..o. -> ....

So, the total number of moves consists of moving each coin individually to the right-most cell. If the total number of moves is odd player 1 wins and if it is even player 2 wins. ( This is parity, even or odd)

With every move the parity changes. If N is total number of moves and a player makes a move N changes parity.

The only difference between this simplified game and the div1 250 problem is the move where you can jump 3 cells to the right. But note this. If total number of moves is N and we use move1 N becomes N-1. If we use move2 N becomes N-3.

Both N-1 and N-3 .

If N was even N-1 and N-3 are odd.

If N was odd N-1 and N-3 are even.

This means N changes parity with any move you make.

So actually there is no difference between these two games. The solution to the first game is to sum the distances from each coin to the right-most cell and consider it's parity. By equivalence it is the same solution for the div1 250 problem :).

I hope this informal proof (if it can be called so...) explains it for you. :)]]>

Edit: It is correct, according to bruteforce through all possible states at least.

Edit: If dp[i-1] is true, then we can tell the sum of distances between all checkers smaller than i-1 and cell (i-1) is odd. If we add a new cell, then for each cell we add 1 to the distance. If the number of cells before

If dp[i-1] is false, then we can tell the sum of distances to (i-1) was even, and the same logic applies.

Note that if a cell in cell (i-1) exists, its distance to (i-1) will be 0. That's the reason that when calculating dp[i] we don't need to care about how dp[i-1] didn't consider it.]]>

No matter what you do in a given position, you will always win or always lose it.

This is because victory can be defined by the parity of the sum of the positions of the checkers, or rather the sum of the distances between their positions and the right-most cell. Yet it does not matter whether you use a normal move or a jump, since the jump jumps three cells, the parity of the distance can only be toggled and never maintained. And this realization translates into a very easy solution. Just about every other thread about this problem already explains this.]]>

Solution 1) When its player 1 turn take MAX of the rest, and when its player 2 turn take MIN of the rest.

Solution 2) Take MAX for both players

Both solutions pass...

I think that this says that there will NEVER be a position for player 2 from which he has 2 choices (lose or win). That is, from every position of player 2 either all of his choices lead him to losing position OR all his choices lead him to winning position.

Am i right? :D]]>

classEllysCheckers {public: string getWinner(string b) { vector<bool> dp(b.size(),false);for(inti=1;i<b.size();i++) {intc=0;for(intk=0;k<i;k++) {if(b[k]=='o') c++; }if(c%2==0) { dp[i] = dp[i-1]; }else{ dp[i] = !dp[i-1]; } }returndp[b.size()-1]==true?"YES" : "NO"; } };

Whenever the count of checkers between board position 0 to i-1 is even, the solution to dp[i] is dp[i-1], otherwise !dp[i-1]. At first I thought it was because the total checkers were evenly distributed between the two players, so that in case of odd number of them, the winning player switches, and in case of even, it doesn't. But I don't think that is right.]]>