JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
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.
Subject Author Date
Proof of the following solution for div2-500/div1-250 Shuaib_Khan Feb 25, 2012 at 9:02 AM EST
Re: Proof of the following solution for div2-500/div1-250 vasja_p Feb 25, 2012 at 8:25 PM EST
Re: Proof of the following solution for div2-500/div1-250 vexorian Feb 25, 2012 at 8:33 PM EST
Re: Proof of the following solution for div2-500/div1-250 Shuaib_Khan Feb 25, 2012 at 8:51 PM EST
Re: Proof of the following solution for div2-500/div1-250 vasja_p Feb 25, 2012 at 9:38 PM EST
Re: Proof of the following solution for div2-500/div1-250 vexorian Feb 25, 2012 at 9:41 PM EST
Re: Proof of the following solution for div2-500/div1-250 Shuaib_Khan Feb 25, 2012 at 9:54 PM EST
Re: Proof of the following solution for div2-500/div1-250 vasja_p Feb 26, 2012 at 7:36 AM EST
Re: Proof of the following solution for div2-500/div1-250 Shuaib_Khan Mar 2, 2012 at 6:15 AM EST
Re: Proof of the following solution for div2-500/div1-250 vasja_p Feb 25, 2012 at 9:26 PM EST
RSS