There are only 2 types of heaps in this problem: 1. Optional heaps -> have > 1 coins 2. Non-optional heaps -> have = 1 coins
Start from the rightmost heap. This is base case - whoever gets this heap surely wins. Look at the heaps before it. If it is a non-optional heap (1 element only), then the assured outcome is the inverse of the assured outcome of the next heap. If it is an optional heap, then the assured outcome for whoever is first is a win - irrespective of the assured outcome of the next heap. This is because the player whose turn it is to move can either pick up all the elements of the heap thus converting it into the assured outcome of the next heap (if that is a loss for the other player) or can leave 1 element in the heap, thus getting a win by optimal play. When there are multiple optional heaps in sequence, the optimal play is to always force your opponent to keep picking the last element from each heap so that you retain control over the fate of the game. Hence, a sequence of optional heaps is the same as a single optional heap. Unroll the loop till the first heap and output the assured outcome as the answer. For example 1 2 2 2 1: 1 - Win 2 1 - Win for Player 1 at this stage 2 2 1 - Win for Player 1 at this stage 2 2 2 1 - Win for Player 1 at this stage 1 2 2 2 1 - Loss for Player 1 at this stage... Outcome: Loss This is equivalent to 1 2 1 For eg. For the heap: 1 2 3 1 2 2 - win for player 1 1 2 - Loss for player 1 3 1 2 - Win for player 1 2 3 1 2 - Win for player 1 1 2 3 1 2 - Loss for player 1 This is equivalent to 1 2 1 2 For all the games discussed above: Game 1: 2 3 -> is the same as game 2 2 which is equivalent to 2 -> Player 1 wins Game 2: 1 2 -> is a loss for player 1 for obvious reasons Game 3: 2 1 -> is a win because of the optional heap Game 4: 1,2,3,1,4 -> Loss for player 1. Equal to 1 2 2 1 2 -> 1 2 1 2 -> Loss Game 5: 1,1,2,3 -> Win for player 1. Equal to 1 1 2 2 -> 1 1 2 -> Win Game 6: 2,1,3,4,5 -> Equal to 2 1 2 2 2 -> 2 1 2 -> Win for player 1 Nice question. --- Enjoy! DK http://twitter.com/divyekapoor http://www.divye.in -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/M1kxsMMUgjIJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
