PROBLEM LINK:
Author: ravikiran0606
Editorialist: ravikiran0606
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
COMBINATORIAL GAMES,DP
PROBLEM:
Initially there are K coins in the pile. There is an array of N integers a1, a2,…aN. The game is played in turns.In each turn, the player can take away ai coins (1<=i<=N) from the pile. The player who cannot make any turn loses the game. It is assumed that both the players play optimally. We need to find the winner of the game.
EXPLANATION:
In this question, we can find who will win the game using the rules of the combinatorial games. We can consider the game as the set of positions where the first player will win or lose. Let’s represent this information in an array dp[maxi]. Let dp[i] = 1 denote that with i coins in the pile, first player will win and dp[i] = 0 denote that with i coins in the pile, first player will lose in that position.
Positions have the following properties:
1)All terminal positions are losing.
2)If a player is able to move to a losing position then he is in a winning position.
3)If a player is able to move only to the winning positions then he is in a losing position.
The base case is that dp[0] = 0, since with 0 coins, first player cannot make a move and he will lose. We need to fill the array by using the above properties. Losing positions are those indices i such that dp[i] = 0 and winning positions are those indices i such that dp[i] = 1. In this question, from the position i, the player can move to positions i-a[p] ( for all 1<=p<=N such that i-a[p]>=0 ). From position i, if a player can move to at least one position j such that dp[j] = 0, then dp[i] = 1. (rule 2) Otherwise dp[i] = 0 (rule 2). In that way, if we fill the array dp upto kth position. If dp[k] = 1, then the answer is “Yes” else “No”.
AUTHOR’S SOLUTION:
Author’s solution can be found here