Last Updated: 11 Dec, 2020

Optimal Strategy for a Game

Easy

Asked in companies

Solve now

Problem statement

You and your friend Ninjax are playing a game of coins. Ninjax place the 'N' number of coins in a straight line.

The rule of the game is as follows:

1. Each coin has a value associated with it.

2. It’s a two-player game played against an opponent with alternating turns. 

3. At each turn, the player picks either the first or the last coin from the line and permanently removes it.

4. The value associated with the coin picked by the player adds up to the total amount the player wins.

Ninjax is a good friend of yours and asks you to start first.

Your task is to find the maximum amount you can definitely win at the end of this game.

Note:

'N' is always even number.

Ninjax is as smart as you, so he will play so as to maximize the amount he wins.

Example 1:

Let the values associated with four coins be: [9, 5, 21, 7] 

Let’s say that initially, you pick 9 and Ninjax picks 7.
Then, you pick 21 and Ninjax picks 5. 
So, you win a total amount of (9+21), i.e. 30.

In case you would have picked up 7 initially and Ninjax would have picked 21 (as he plays optimally). 
Then, you would pick 9 and Ninjax would choose 5. So, you win a total amount of (7+9), i.e. 16, which is not the maximum you can obtain.

Thus, the maximum amount you can win is 30.

Example 2:

Let the values associated with four coins be: [20, 50, 5, 10] 

Let’s say that initially, you pick 10 and Ninjax picks 20.
Then, you pick 50 and Ninjax picks 5. 
So, you win a total amount of (10+50), i.e. 60.

In case you would have picked up 20 initially and Ninjax would have picked 50 (as he plays optimally). 
Then, you would pick 10 and Ninjax would choose 5. So, you win a total amount of (20+10), i.e. 30, which is not the maximum you can obtain.

Thus, the maximum amount you can win is 60.

Input format:

The very first line of input contains an integer T denoting the number of test cases. 

The first line of every test case contains an integer ‘N’ denoting the number of coins present in the line initially. 

The second line of every test case contains ‘N’ space-separated integers denoting the values associated with the coins placed by Ninjax.

Output format:

For each test case, print the required answer in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= 'T' <= 10 
2 <= 'N' <= 10 ^ 3 
0 <= 'VALUE' <= 10 ^ 5

Where 'T' is the number of test cases, 'N' is the number of coins and 'VALUE' is the amount on each coin.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Suppose it's your turn and you are left with coins in the index range ['I', ‘J’] (other coins have already been picked up in previous turns). You have the option to pick either ith or jth coin. Of these two options, you would select the one which maximizes your winning amount.
- If you pick the ith coin. The other player will have the option to pick ('I'+1)th or ‘J’th coin.
  → If the other player picks the ('I'+1)th coin. You can pick either end of the range ['I'+2, ‘J’].
  →If the other player picks ‘J’th coin. You can pick either end of the range ['I'+1, ‘J’-1].
  → As the other player wants to maximize his amount (thereby minimizing the amount you can win). Hence, of the two ranges which you are left with (mentioned above), you can only use that range that gives us the minimum amount.
- If you pick the jth coin. The other player will have the option to pick ith or ('J'-1)th coin.
  → If the other player picks the ith coin. You can pick either end of the range ['I'+1, ‘J’-1].
  → If the other player picks ('J'-1)th coin. You can pick either end of the range ['I', ‘J’-2].
  → Similarly here, of the two ranges which you are left with (mentioned above), you can only use that range which gives us the minimum amount.
We’ll use a helper function that would return the maximum amount you can win for a given sub-array of coins.

Algorithm for the above solution is as follows:

→ Int helper(vector<int> ‘COINS’, int ‘I’, int ‘J'):

Base Case 1: if ‘I’>'J', this is not possible so return 0.
Base Case 2: if ‘I’='J', means only one element in the sub-array, hence return coins[i].
Select the ith coin, and recursively call the helper function for the two possible cases and select the one which gives the minimum.
- 'X' = ‘COINS’['I'] + min( helper('COINS', 'I'+1, 'J'-1), helper('COINS', 'I'+2, 'J'))
Select the jth coin, and recursively call the helper function for the two possible cases and select the one which gives the minimum.
- ‘Y’ = ‘COINS’['I'] + min( helper('COINS', 'I'+1, 'J'-1), helper('COINS', 'I', 'J'-2))
For the above two possible amounts, select the maximum one.
‘AMOUNT’ = Max('X', ‘Y’)
Return this selected amount.

→ Int optimalStrategyOfGame(vector<int> ‘COINS’, int ‘N'):

Call helper('COINS', 0, ‘N’ - 1)
Return the result generated by the helper function.

Solve now

02 Approach

In the previous approach, we were making 4 recursive calls every time we called the helper function but a better approach to solve, would be as follows:

We’ll use a helper function that will return the maximum amount you can win for a given subarray of coins.
Suppose it's your turn and you are left with coins in the index range ['I', 'J'] (other coins have already been picked up in the previous turns). You have the option to pick ith or jth coin. Let SUM store the sum of coins in the subarray ['I', 'J'].
→ If you pick the ith coin. The other player will have the option to pick ('I'+1)th or jth coin. The other player will choose the coin such that it minimizes the amount you can earn. So you can collect the value Vi + ('SUM' – 'Vi') – helper('I' + 1, 'J', ‘SUM’ – ‘Vi’). The expression can be simplified to ‘SUM’ – helper('I'+1, 'J', ‘SUM’ – 'Vi')
→ If you pick the jth coin. The other player will have the option to pick ith or ('J'-1)th coin. The other player will choose the coin such that it minimizes the amount you can earn. So you can collect the value ‘Vj’ + ('SUM' –'Vj') – helper('I', 'J'-1, ‘SUM’ – ‘Vj’). The expression can be simplified to 'SUM' – helper('V'+1, 'J', 'SUM' – 'Vj').
→ As we want to maximize our amount, we will return the maximum out of the two.

The algorithm for the helper function would be -

→ Int helper(vector<int> ‘COINS’, int 'I', int 'J', int ‘SUM’):

Base Case: if 'I'='J'+1, return the maximum of the two coins.
Return Maximum of (SUM - helper('I'+1,'J', 'SUM' - ‘COINS’['I']), SUM - helper('I', 'J'-1, 'SUM' - ‘COINS’['J']))

Solve now

03 Approach

Approach 1 solves the same sub-problems multiple times i.e. helper function gets called for the same sub-array (index range) multiple times.

For example: Consider calling helper function for a range [0, 10], the recursive calls made will be for ranges: [2, 10], [1, 9], [1, 9], [0, 8].
→ We can see that the same subproblem (here [1, 9]) will be solved multiple times.
→ As we move down the recursion tree, this will happen with other subproblems as well.
→ This can be avoided by storing the results which we have already calculated in a lookUp table and return this result whenever required, instead of calculating it again.
→ Hence, the idea is to use the concept of memoization using a lookUp table.
Steps:
→ Create a 2D lookup table, of size ‘N’ * ‘N’, to store the solutions to the subproblems where ‘LOOKUP’['I']['J'] denotes the maximum amount you can win for the subarray coins['I', 'J']. Given that you start first.
→ Initialize the table by -1.
→ Now, every time we call the helper we first check whether the sub-problem has been solved before or not.
If ‘LOOKUP’[i]['J'] = -1, sub-problem needs to be solved. Hence, recursively call the helper function and store the result in the table.
Otherwise, the sub-problem has already been solved. Just return the stored result.
The algorithm for the helper function will be as follows:
Int helper(vector<int> 'COINS', int 'I', int 'J'):
→ Base Case 1: if 'I'>'J', this is not possible so return 0.
→ Base Case 2: if 'I'='J', means only one element in the sub-array, hence return 'COINS'['I'].
→ If ‘LOOKUP’['I']['J'] != -1, return ‘LOOKUP'['I']['J'].
Otherwise, we move to the next step.
→ Select the ith coin, and recursively call the helper function for the two possible cases and select the one which gives the minimum. Thus, call X = 'COINS'['I'] + min( helper('COINS', 'I'+1, 'J'-1), helper('COINS', 'I'+2, 'J')).
→ Select the jth coin, and recursively call the helper function for the two possible cases and select the one which gives the minimum, thus, call Y = 'COINS'['I'] + min( helper('COINS', 'I'+1, 'J'-1), helper('COINS', 'I', 'J'-2)).
→ For the above two possible amounts, select the maximum one, thus, update ‘AMOUNT’ = Max('X', 'Y').
→ Store the ‘AMOUNT’ in ‘LOOKUP’['I']['J'].
→ Return this selected amount.

Solve now

04 Approach

Approach 2 solves the same sub-problems multiple times i.e. helper function gets called for the same sub-array (index range) multiple times.
For example: Consider calling helper function for a range [0, 10], we can see in the image given below that the same subproblem (here [1, 9]) will be solved multiple times.

As we move down the recursion tree, this will happen with other subproblems as well.

This can be avoided by storing the results which we have already calculated and return this result whenever required instead of calculating it again.
Hence, the idea is to use memoization by using a ‘LOOKUP’ table.
Create a 2D lookUp table, of size ‘N’ * ‘N’, to store the solutions to the subproblems where ‘LOOKUP’['I']['J'] denotes the maximum amount you can win for the subarray ‘COINS’['I', 'J']. Given you start first.
Initialize the table by -1.
Now, on every call to the helper function, we first check whether the sub-problem has been solved before or not.
If ‘LOOKUP’['I']['J'] = -1, sub-problem needs to be solved. Hence, recursively call the helper function and store the result in the table.
Otherwise, the sub-problem has already been solved. Just return the stored result.

The algorithm for the helper function is as follows:

Int helper(vector<int> ‘COINS’, int ‘I’, int 'J', int SUM):

Base Case: if 'I'='J'+1, return the maximum of the two coins.
If ‘LOOKUP’['I']['J'] != -1, return ‘LOOKUP’['I']['J'].
Otherwise, move to the next step.
‘AMOUNT’ = Maximum of (SUM - helper('I'+1, 'J', SUM - ‘COINS’['I']), SUM - helper('I', 'J'-1, SUM -‘COINS’['J']))
Store the ‘AMOUNT’ in ‘LOOKUP’['I']['J'].
Return the 'AMOUNT'.

Solve now

05 Approach

The idea behind the approach will be:
Suppose it's your turn and you are left with coins in the index range ['I', ‘J’] (other coins have already been picked up in previous turns). You have the option to pick ith or jth coin. Of these two options, you would select the one which maximizes your winning amount.

If you pick the ith coin. The other player will have the option to pick ('I'+1)th or 'J'th coin.
→ If the other player picks the ('I'+1)th coin. You can pick either end of the range ['I'+2, 'J'].
→ If the other player picks 'J'th coin. You can pick either end of the range ['I'+1, 'J'-1].

→Now, as the other player wants to maximize his amount (thereby minimizing the amount you can win) hence, of the two ranges which you are left with (mentioned above), you can only use that range which gives us the minimum amount.
If you pick the jth coin. The other player will have the option to pick ith or ('J'-1)th coin.
→ If the other player picks the ith coin. You can pick either end of the range ['I'+1, 'J'-1].
→If the other player picks (j-1)th coin. You can pick either end of the range ['I', 'J'-2].

→ Similarly here, of the two ranges which you are left with (mentioned above), you can only use that range which gives us the minimum amount.

Idea

The idea is to create a 2D table of size N*N.
Each entry in the table stores the solution to a subproblem i.e. ‘TABLE’['I']['J'] represents the maximum amount you can win for the subarray ‘COINS’['I', 'J'] given that you start first.
The algorithm for filling the table is as follows:
- Loop 1: For ‘LEN’ = 1 to ‘N’:
- Loop 2: For ‘I’ = 0 to ('N' - ‘LEN’):
  →Let 'J' = 'I' + ‘LEN’ - 1
  →If ('I'+1) < N && ('J'-1) >= 0 then, A = ‘DP’['I'+1]['J'-1], otherwise A = 0.
  →If (i+2) < N then, B = ‘DP’['I'+2]['J'], otherwise B = 0.
  → If ('J'-2) >= 0 then, C = ‘DP’['I']['J'-2], otherwise C = 0.
  → Update ‘DP’['I']['J'] = max(‘COINS’['I'] + min(A, B), coins['J'] + min(A, C)).
- End Loop 2.
- End Loop 1.
‘DP’[0]['N'-1] stores the final answer.

Let us understand the above algorithm in detail with an example:
For the test case where ‘N’ = 4, Coins List = [5, 40, 4, 1]

We will create a Table of dimension N * N i.e. 4 * 4, with all elements initialised to 0.
Each entry in the table stores the solution to a subproblem i.e. ‘TABLE’['I']['J'] represents the maximum amount you can win for the subarray coins['I', 'J'] given that you start first.
The ‘LEN’ variable in the algorithm represents the length of the subarray being considered in the current iteration.
For the first iteration ‘LEN’ = 1, so consider all the subarrays with length 1. All the cells with ‘I’ = ‘J’ are filled in this iteration. Filling the table according to the conditions mentioned in the algorithm above, we get:

For the second iteration ‘LEN’ = 2, so consider all the subarrays with length 2.All the cells with ('I'+1='J') are filled in this iteration. Filling the table according to the conditions mentioned in the algorithm above, we get:

For the third iteration ‘LEN’ = 3, so consider all the subarrays with length 3. All the cells with ('I'+2='J') are filled in this iteration. Filling the table according to the conditions mentioned in the algorithm above, we get:

For the fourth iteration ‘LEN’ = 4 (= 'N'), so consider all the subarrays with length 4. All the cells with ('I' + 3 = 'J') are filled in this iteration. Filling the table according to the conditions mentioned in the algorithm above, we get:

The cell marked as red (Table[0]['N' - 1]) stores the final answer.

Solve now