JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums Algorithm Matches SRM 534 Proof of the following solution for div2-500/div1-250 Revision History (1 edit)
Proof of the following solution for div2-500/div1-250
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.
Proof of the following solution for div2-500/div1-250
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 i-1 to j 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.