JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Matches SRM 534 Proof of the following solution for div2-500/div1-250
 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 dp(b.size(), false);   for(int i=1;i
 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 playersBoth 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
 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 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 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 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 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 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 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 vexorian) | Reply Thanks, i read the other topics but didn't quite understand until now what parity is. Thanks vexorian.
 Forums Algorithm Matches SRM 534 Proof of the following solution for div2-500/div1-250 Previous Thread  |  Next Thread