0
$\begingroup$

I have 2 problems that derive from a simple problem. I'll explain the simple one with the solution I found and after that the modified problem.

Suppose there is a game with 2 players, A and B and a list of positive integers. Player A starts by taking out a number from the list, player B does the same and so on after the there are no longer numbers in the list. Both players sum up the picked numbers. Each player scores the difference between his sum and the opponent's one. The question is what is the maximum score player A can obtain if both players play in an optimal manner.

Now, for this I figured out that the optimal strategy for each player is to take the biggest number at each step.

The following 2 modification:

At the beginning of the game player A should remove K numbers from the list. If he does this in an optimal manner and after that the games is the initial one, what is the maxim score he can obtain?

and

At each step the players can pick the left-most or the right-most number from the list. Again they play in an optimal manner. Which is the maximum score player A can obtain?

For the second modification I can think of a brute-force approach, i.e. computing the tree of all possibilities, but this does not work for big input data. I believe that there is some kind of DP algorithm.

For the first modification I can't think of an idea.

Can someone help with some ideas for the 2 modifications, what algorithm to design in order to get the response?

[LATTER EDIT]

For the second variation I found the DP solution at https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/

$\endgroup$
  • 1
    $\begingroup$ What help do you expect exactly ? An efficient solution to answer both modifications at the time ? Only the first one ? A DP solution for the second one ? Please precise your question. $\endgroup$ – Vince Apr 3 at 9:52
  • $\begingroup$ @Vince Basically I need algorithm ideas for those 2 variations of the initial problem. The implementation itself is easy, but an optimal algorithm I don't know. I've made it precise. $\endgroup$ – vasile_t Apr 3 at 9:59
  • $\begingroup$ Can player A remove less than K numbers in Variant 1? $\endgroup$ – xskxzr Apr 3 at 10:45
  • $\begingroup$ @xskxzr No, he is supposed to move exactly K numbers. $\endgroup$ – vasile_t Apr 3 at 10:53
  • $\begingroup$ @j_random_hacker You mean that Player A gets the biggest number, eliminates the biggest from remaining list, player B picks the new maximum, and repeat this until the list becomes empty or K numbers where eliminated, and continue the game from initial problem? $\endgroup$ – vasile_t Apr 3 at 11:21
0
$\begingroup$

Here is the post for the 2nd modification, which is

At each step the players can pick the left-most or the right-most number from the list. Again they play in an optimal manner. Which is the maximum score player A can obtain?

The solution is based on DP. For the sub-problem (i-j) i.e. v[]i, v[i+1], ..., v[j] there are two choices:

  1. The user chooses the i-th element with value v[i]: The opponent either chooses (i+1)-th element or j-th element. The opponent intends to choose the element which leaves the user with minimum value. i.e. The user can collect the value v[i] + min(F(i+2, j), F(i+1, j-1))

enter image description here

  1. The user chooses the j-th element with value v[j]: The opponent either chooses i-th element or (j-1)-th element. The opponent intends to choose the element which leaves the user with minimum value. i.e. The user can collect the value v[j] + min(F(i+1, j-1), F(i, j-2))

enter image description here

Following is recursive solution that is based on above two choices. We take the maximum of two choices.

F(i, j) represents the maximum value the user can collect from i-th coin to j-th coin.

F(i, j) = Max(v[i] + min(F(i+2, j), F(i+1, j-1)), v[j] + min(F(i+1, j-1), F(i, j-2)))

Base Cases

F(i, j) = v[i] If j == i

F(i, j) = max(v[i], v[j]) If j == i+1

Here is a pice of code in Python that solves it

def optimalStrategyOfGame(arr, n): 

    # Create a table to store solutions of subproblems  
    table = [[0 for i in range(n)] for i in range(n)] 

    # Fill table using above recursive formula. Note that the table is  
    # filled in diagonal fashion from diagonal elements to table[0][n-1] which is the result.  
    for gap in range(n): 
        for j in range(gap, n): 
            i = j - gap 

            # Here x is value of F(i+2, j), y is F(i+1, j-1) and z is  
            # F(i, j-2) in above recursive formula  
            x = 0
            if((i + 2) <= j): 
                x = table[i + 2][j] 
            y = 0
            if((i + 1) <= (j - 1)): 
                y = table[i + 1][j - 1] 
            z = 0
            if(i <= (j - 2)): 
                z = table[i][j - 2] 
            table[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z)) 
    return table[0][n - 1] 

[SOURCE] https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.