Gambling (Algorithm 1)

Points : 17

Alice and Bob play a unique gambling game at a casino. A row of casino chips (tokens) is placed at the Casino table.The players play alternate turns. In a turn a player can take a chip from any end of the row (two choices).

Assume that you are given an initial configuration of the chips along with their denominations and Alice starts the game. Alice wants to acquire maximum possible amount irrespective of the strategy Bob plays with.

Design an Algorithm to calculate the maximum amount that Alice can definitely acquire.

Can you extend the game for two rows when each turn would have four choices? Mention the time and space complexities along with both algorithms.

Solution

Case 1

Gambling problem was based upon the famous problem Coins in a Row in which two players plays a game against each other under the constraints that they can pick the coin from the end’s only. The solution to this problem is based on Dynamic Programming since greedy approach would not work here.

Now let us define the Recursive Relations for this approach. Let P(i,j) denotes the value of profit that I can take when I am left with casino chips from i to j.

P(i,j) = Max{[min(p(i+1,j-1),p(i+2,j))+ val(ith chip)],[min(p(i,j-2),p(i+1,j-1))+ val(jth chip)]}

Where min[p(i+1,j-1),p(i+2,j)] corresponds to the move that when I picked ith chip from the table then if the other person takes jth chip then our problem reduces to p(i+1,j-1) but if the other person picks up the i+1th chip from the table then the problem reduces to p(i+2,j).And assuming that the other person is also smarter he will make that move so that I get the minimum from his move similar case corresponds to the other part min[p(i,j-2),p(i+1,j-1)] where I will take the jth chip and the other person has two choices that either he can take ith chip or j-1th chip. So this relation defines the appropriate recursive relation.

Now Initialization part for the DP is:

P(i,j) = val(ith chip), if (i=j)

= Max(val(ith chip),val(jth chip)), if (j=i+1).

Time Complexity is O(n2). Space Complexity is O(n2).

Case 2

Now in the extension of this problem for two Rows with four sides.

A person can pick the chip from either of the four corners. The Recursive Relation for this problem will consist of four variables. Let P(I,j,k,l) denotes the value of profit that I can take when I am left with the casino chips from I to j and from k to l.

P(i,j,k,l) = MAX{Min(P(i+2,j,k,l),P(i+1,j-1,k,l),P(i+1,j,k+1,l),P(i+1,j,k,l-1))+ val(ith chip),

Min(P(i+1,j-1,k,l),P(i,j-2,k,l),P(i,j-1,k+1,l),P(i,j-1,k,l-1))+ val(jth chip),

Min(P(i+1,j,k+1,l),P(i,j-1,k+1,l),P(i,j,k+2,l),P(i,j,k+1,l-1))+ val(kth chip),

Min(P(i+1,j,k,l-1),P(i,j-1,k,l-1),P(i,j,k+1,l-1),P(i,j,k,l-2))+ val(lth chip)}

The initialization can be performed in the same way as done for the case I.

Points Distribution

• 7 points for providing the algorithm along with the complexities for only one row
• 10 points for providing the algorithm along with the complexities for two rows

For any query post your question below.