JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (oldest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Re: Proof of the following solution for div2-500/div1-250 (response to post by vasja_p) | Reply
Thanks vexorian and vasja_p. Both explanations compliment each other and helped me get my thoughts right about the problem.
Re: Proof of the following solution for div2-500/div1-250 (response to post by Shuaib_Khan) | Reply
I now understand it completely. Let me explain. Imagine a simplified version of this game as analogy. In this new game a player can move only using the first move from the original game, that is, he can only move a coin one place to the right. For this game it is easy to see what is the total number of moves to get from the initial board to a board with no coins.

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. :)
Re: Proof of the following solution for div2-500/div1-250 (response to post by vexorian) | Reply
Aha! Well it is correct per the systests in practice room. And yea something tells me this reduces to the same "super easy" solution. But I don't see the equivalence yet.
Re: Proof of the following solution for div2-500/div1-250 (response to post by Shuaib_Khan) | Reply
Mine was a response to vasja_p's post mostly. I haven't answered your post because I am not even sure it is correct yet. If it is correct, it is probably indirectly for the same property as the super easy solution. But I am not sure yet.

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 i (note that there was a typo here) is odd, then we will add an odd number to the sum of distances (We will toggle its parity). If the number of cells is even, then we will add an even number (parity stays the same).

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.
Re: Proof of the following solution for div2-500/div1-250 (response to post by Shuaib_Khan) | Reply
My reply was just an addition to your question :) since i had a similar problem in understanding my own code , and didn't want to post a new topic :)
Re: Proof of the following solution for div2-500/div1-250 (response to post by vexorian) | Reply
Thanks, i read the other topics but didn't quite understand until now what parity is. Thanks vexorian.
Re: Proof of the following solution for div2-500/div1-250 (response to post by vexorian) | Reply
A little confused here. Were the above two replies a direct response to my question?
Re: Proof of the following solution for div2-500/div1-250 (response to post by vasja_p) | Reply
Yes, you are right.

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.
Re: Proof of the following solution for div2-500/div1-250 (response to post by Shuaib_Khan) | Reply
I also got confused after my solution passed system tests. It seemed so ok when i coded it but now i don't really understand why it works.
Then i coded another solution and it too passed, although it is different. Basically first is min-max stratgy and second is max-max strategy :))).

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
Proof of the following solution for div2-500/div1-250 | Reply
I came up with the following DP recurrence, and it passes systest. But now that I am thinking about why it works, I am not completely able to come up with a proof. Can someone shed some light.
class EllysCheckers {
public:
	string getWinner(string b) {
 
	vector<bool> dp(b.size(), false);
 
	for(int i=1;i<b.size();i++)
	{
 
				int c=0;
				for(int k=0;k<i;k++)
				{
					if(b[k]=='o')
						c++;
				}
				if(c%2==0)
				{
					dp[i] = dp[i-1];
				}
				else
				{
					dp[i] = !dp[i-1];
				}
 
	}
	return dp[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.
RSS