- Dynamic Programming, Game Theory, Mathematical, Picked

Find the winner of a game of removing at most 3 stones from a pile in each turn

Given an array arr[] of size N, denoting values assigned to N stones, two players, Player1 and Player2, play a game of alternating turns. In each turn, a player can take 1, 2, or 3 stones from the first remaining stones with the sum of values of all the removed stones added to the player’s score. Considering that both players play optimally, the task is to print the the winner of the game. If both the players end the game with the same score, print “Tie”.Examples:Input: arr[] = {1, 2, 3, 7}Output: Player2Explanation: Player1 will always lose in an optimal scenario.Input: arr[] = {1, 2, 3, -9}Output: Player1Explanation: Player1 must choose all the three piles at the first move to win and leave Player2 with negative score.If Player1 chooses only one stone his score will be 1 and the next move Player2 score becomes 5. The next move Player1 will take the stone with value = -9 and lose.If Player1 chooses two piles his score will be 3 and the next move Player2 score becomes 3. The next move Player1 will take the stone with value = -9 and also lose.Naive Approach: The simple approach is to pick the number of stones that will maximize the total sum of the stone’s values. As both players play optimally and Player1 starts the game, Player1 picks either 1 or 2 or 3 stones and the remaining stones passed to the next player. Therefore, the score of Player2 must be subtracted from score of Player1. The idea is to use recursion to solve the problem. Let the maximum score of Player1 be res which is obtained after the recursive calls.If the result, res > 0, Player1 winsIf the result, res < 0, Player2 winsIf the result, res == 0, then it is a tie.The recursive tree looks like this, where some subproblems are repeated many times. Follow the steps to solve the problem:Declare a recursive function, say maxScore(i), to calculate the maximum score of Player1 if the game starts at index iIf the value of i ≥ n, return 0.Initialize a variable, say score as INT_MIN, to store the maximum score of Player1Picks 1 stone: score = max(score, arr[i] – maxScore(i + 1))Picks 2 stones i.e (i + 1 < N): score = max(score, arr[i] + arr[i + 1] – maxScore(i + 2))Picks 3 stones i.e (i + 2 < N): score = max(score, arr[i] + arr[i + 1] + arr[i + 2] – maxScore(i + 3))Return the value of score.Store the value of maxScore(0) in a variable res.If the value of res>0, print “Player1”, if res= n)        return 0;          int ans = INT_MIN;          ans = max(ans,              arr[i] – maximumStonesUtil(arr, n, i + 1));          if (i + 1 < n)        ans = max(ans,                  arr[i] + arr[i + 1]                      - maximumStonesUtil(arr, n, i + 2));          if (i + 2 < n)        ans = max(ans,                  arr[i] + arr[i + 1] + arr[i + 2]                      - maximumStonesUtil(arr, n, i + 3));          return ans;}  string maximumStones(int* arr, int n){        int res = maximumStonesUtil(arr, n, 0);          if (res > 0)        return “Player1”;          else if (res < 0)        return "Player2";          else        return "Tie";}  int main(){        int arr[] = { 1, 2, 3, 7 };    int n = sizeof(arr) / sizeof(arr[0]);          cout = n)        return 0;      int& ans = dp[i];              if (ans != -1)        return ans;          ans = INT_MIN;          ans = max(        ans, arr[i] - maximumStonesUtil(arr, n, i + 1, dp));          if (i + 1 < n)        ans = max(ans, arr[i] + arr[i + 1]                           - maximumStonesUtil(arr, n,                                               i + 2, dp));          if (i + 2 < n)        ans = max(ans, arr[i] + arr[i + 1] + arr[i + 2]                           - maximumStonesUtil(arr, n,                                               i + 3, dp));          return ans;}  string maximumStones(int* arr, int n){        vector dp(n, -1);          int res = maximumStonesUtil(arr, n, 0, dp);          if (res > 0)        return “Player1”;          else if (res < 0)        return "Player2";          else        return "Tie";}  int main(){        int arr[] = { 1, 2, 3, 7 };    int n = sizeof(arr) / sizeof(arr[0]);          cout