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 (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Matches SRM 534 Div2-500 proof
 Div2-500 proof | Reply The correct/simplest algorithm was to add up the distance of all the pieces from the right with winning positions as odd and losing as even.I thought up this proof for that.Define: an "odd" position as one where the sum of the distances is odd and an "even" position as one where the sum of the distances is even.1. The last move of any game (the * game) is to have a single piece on the board with distance of 1. In order to win, you must eventually end up in this position. This is an odd position.2. If you are in an odd position, you can move your opponent into an even position: You can always move one piece to the right by one spot, decreasing the sum by 1, resulting in an even sum.3. If you are in an even position, you cannot move your opponent into an even position: case 1) move one piece to the right, decreasing the sum by 1, resulting in an odd position. case 2) move one piece 3 to the right, decreasing the sum by 3, resulting in an odd position.4. For optimal play, all winning initial positions are odd: since the * game is odd (1), you need to get to an odd position to win. If you're in an odd position, you can remain in an odd position (by 2 & 3). If you're in an even position, you cannot get into an odd position (by 2 & 3).
 Re: Div2-500 proof (response to post by mcclosdl) | Reply What is the explaination if two checkers are at odd positions and sum is even. The first player can use one of these odd positions to win? I don't really understood the editorial completely in the first place. Can you help me?
 Forums Algorithm Matches SRM 534 Div2-500 proof Previous Thread  |  Next Thread