## Coins in a Line

February 9, 2011 in dynamic programming

There are

ncoins in a line. (Assumenis even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

- Would you rather go first or second? Does it matter?
- Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

This is an interesting problem itself, and different solutions from multiple perspectives are provided in this post.

**Hints:**

If you go first, is there a strategy you can follow which prevents you from losing? Try to consider how it matters when the number of coins are odd vs. even.

**Solution for (1):**

Going first will guarantee that you will not lose. By following the strategy below, you will always win the game (or get a possible tie).

- Count the sum of all coins that are odd-numbered. (Call this
**X**) - Count the sum of all coins that are even-numbered. (Call this
**Y**) - If
**X**>**Y**, take the left-most coin first. Choose all odd-numbered coins in subsequent moves. - If
**X**<**Y**, take the right-most coin first. Choose all even-numbered coins in subsequent moves. - If
**X**==**Y**, you will guarantee to get a tie if you stick with taking only even-numbered/odd-numbered coins.

You might be wondering how you can always choose odd-numbered/even-numbered coins. Let me illustrate this using an example where you have 10 coins:

If you take the coin numbered 1 (the left-most coin), your opponent can only have the choice of taking coin numbered 2 or 10 (which are both even-numbered coins). On the other hand, if you choose to take the coin numbered 10 (the right-most coin), your opponent can only take coin numbered 1 or 9 (which are odd-numbered coins).

Notice that the total number of coins change from even to odd and vice-versa when player takes turn each time. Therefore, by going first and depending on the coin you choose, you are essentially forcing your opponent to take either only even-numbered or odd-numbered coins.

Now that you have found a non-losing strategy, could you compute the maximum amount of money you can win?

**Hints:**

One misconception is to think that the above non-losing strategy would generate the maximum amount of money as well. This is probably incorrect. Could you find a counter example? (You might need at least 6 coins to find a counter example).

Assume that you are finding the maximum amount of money in a certain range (ie, from coins numbered i to j, inclusive). Could you express it as a recursive formula? Find ways to make it as efficient as possible.

**Solution for (2):**

Although the simple strategy illustrated in **Solution (1)** guarantees you not to lose, it does not guarantee that it is optimal in any way.

Here, we use a good counter example to better see why this is so. Assume the coins are laid out as below:

{ 3, 2, 2, 3, 1, 2 }

Following our previous non-losing strategy, we would count the sum of odd-numbered coins, **X** = 3 + 2 + 1 = **6**, and the sum of even-numbered coins, **Y** = 2 + 3 + 2 = **7**. As **Y** > **X**, we would take the last coin first and end up winning with the total amount of **7** by taking only even-numbered coins.

However, let us try another way by taking the first coin (valued at 3, denote by **(3)**) instead. The opponent is left with two possible choices, the left coin **(2)** and the right coin **(2)**, both valued at 2. No matter which coin the opponent chose, you can always take the other coin **(2)** next and the configuration of the coins becomes: **{ 2, 3, 1 }**. Now, the coin in the middle **(3)** would be yours to keep for sure. Therefore, you win the game by a total amount of 3 + 2 + 3 = **8**, which proves that the previous non-losing strategy is not necessarily optimal.

To solve this problem in an optimal way, we need to find efficient means in enumerating all possibilities. This is when Dynamic Programming (DP) kicks in and become so powerful that you start to feel magical.

First, we would need some observations to establish a recurrence relation, which is essential as our first step in solving DP problems.

_{i}… A

_{j}} and it is your turn. Let P(i, j) denotes the maximum amount of money you can get. Should you choose A

_{i}or A

_{j}?

Assume that P(i, j) denotes the maximum amount of money you can win when the remaining coins are { A_{i}, …, A_{j} }, and it is your turn now. You have two choices, either take A_{i} or A_{j}. First, let us focus on the case where you take A_{i}, so that the remaining coins become { A_{i+1} … A_{j} }. Since the opponent is as smart as you, he must choose the best way that yields the maximum for him, where the maximum amount he can get is denoted by P(i+1, j).

Therefore, if you choose A_{i}, the maximum amount you can get is:

P_{1}= Sum{A_{i}... A_{j}} - P(i+1, j)

Similarly, if you choose A_{j}, the maximum amount you can get is:

P_{2}= Sum{A_{i}... A_{j}} - P(i, j-1)

Therefore,

P(i,j) = max { P_{1}, P_{2}} = max { Sum{A_{i}... A_{j}} - P(i+1, j), Sum{A_{i}... A_{j}} - P(i, j-1) }

In fact, we are able to simplify the above relation further to (Why?):

P(i, j) = Sum{A_{i}... A_{j}} - min { P(i+1, j), P(i, j-1) }

Although the above recurrence relation is easy to understand, we need to compute the value of Sum{A_{i} … A_{j}} in each step, which is not very efficient. To avoid this problem, we can store values of Sum{A_{i} … A_{j}} in a table and avoid re-computations by computing in a certain order. Try to figure this out by yourself. (Hint: You would first compute P(1,1), P(2,2), … P(*n*, *n*) and work your way up).

**A Better Solution:**

There is another solution which does not rely on computing and storing results of Sum{A_{i} … A_{j}}, therefore is more efficient in terms of time and space. Let us rewind back to the case where you take A_{i}, and the remaining coins become { A_{i+1} … A_{j} }.

_{i}from the coins { A

_{i}… A

_{j}}. The opponent will choose either A

_{i+1}or A

_{j}. Which one would he choose?

Let us look one extra step ahead this time by considering the two coins the opponent will possibly take, A_{i+1} and A_{j}. If the opponent takes A_{i+1}, the remaining coins are { A_{i+2} … A_{j} }, which our maximum is denoted by P(i+2, j). On the other hand, if the opponent takes A_{j}, our maximum is P(i+1, j-1). Since the opponent is as smart as you, he would have chosen the choice that yields the minimum amount to you.

Therefore, the maximum amount you can get when you choose A_{i} is:

P_{1}= A_{i}+ min { P(i+2, j), P(i+1, j-1) }

Similarly, the maximum amount you can get when you choose A_{j} is:

P_{2}= A_{j}+ min { P(i+1, j-1), P(i, j-2) }

Therefore,

P(i, j) = max { P_{1}, P_{2}} = max { A_{i}+ min { P(i+2, j), P(i+1, j-1) }, A_{j}+ min { P(i+1, j-1), P(i, j-2) } }

Although the above recurrence relation could be implemented in few lines of code, its complexity is exponential. The reason is that each recursive call branches into a total of four separate recursive calls, and it could be *n* levels deep from the very first call). Memoization provides an efficient way by avoiding re-computations using intermediate results stored in a table. Below is the code which runs in *O*(*n*^{2}) time and takes *O*(*n*^{2}) space.

**Edit:**

Updated code with a new function *printMoves *which prints out all the moves you and the opponent make (assuming both of you are taking the coins in an optimal way).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | const int MAX_N = 100; void printMoves(int P[][MAX_N], int A[], int N) { int sum1 = 0, sum2 = 0; int m = 0, n = N-1; bool myTurn = true; while (m <= n) { int P1 = P[m+1][n]; // If take A[m], opponent can get... int P2 = P[m][n-1]; // If take A[n] cout << (myTurn ? "I" : "You") << " take coin no. "; if (P1 <= P2) { cout << m+1 << " (" << A[m] << ")"; m++; } else { cout << n+1 << " (" << A[n] << ")"; n--; } cout << (myTurn ? ", " : ".\n"); myTurn = !myTurn; } cout << "\nThe total amount of money (maximum) I get is " << P[0][N-1] << ".\n"; } int maxMoney(int A[], int N) { int P[MAX_N][MAX_N] = {0}; int a, b, c; for (int i = 0; i < N; i++) { for (int m = 0, n = i; n < N; m++, n++) { assert(m < N); assert(n < N); a = ((m+2 <= N-1) ? P[m+2][n] : 0); b = ((m+1 <= N-1 && n-1 >= 0) ? P[m+1][n-1] : 0); c = ((n-2 >= 0) ? P[m][n-2] : 0); P[m][n] = max(A[m] + min(a,b), A[n] + min(b,c)); } } printMoves(P, A, N); return P[0][N-1]; } |

**Further Thoughts:**

Assume that your opponent is so dumb that you are able to manipulate him into choosing the coins you want him to choose. Now, what is the maximum possible amount of money you can win?

Noob said on February 10, 2011

what modification should i do to the logic in order to get the list of coins the winning player has chosen

eg: 1 3 5 2 are the coins

i need to print

winner: 1 , 5

loser : 2 , 3

-1Anonymous said on February 10, 2011

can you shed some light on "Count the sum of all coins that are odd-numbered"? what does 'odd-numbered' mean? is it something you assign to coin in initializing stage? or the value of coin?

+31337c0d3r said on February 10, 2011

@Anonymous:

"odd-numbered" means coins that are in odd number positions. (ie, if there are 6 coins, the odd-numbered coins are coin number 1, 3, and 5).

01337c0d3r said on February 10, 2011

@Noob:

You can utilize the calculated results in the table to print out both players' moves. It is pretty straightforward. Check out my updated code above!

0Anonymous said on February 10, 2011

@1337c0d3r, You are doing amazing job here. Your analysis is awesome. I wonder if you would be my mentor, because I am preparing for job interviews.

01337c0d3r said on February 11, 2011

@Anonymous:

Thanks for your compliments. Feel free to work out the interview problems here and I'm sure you'll do good in your interview. Feel free to leave a comment if you have any questions, I would try my best to help.

0surebh said on February 18, 2011

@1337c0d3r: Thanks for your reply.Sorry for being late because I was busy with some interviews, but no success yet. I am getting many rejections. Is it possible for you to give me your email address so that I can discuss my problem with you. If you feel that it would be hard for you to give your email address here, I can share mine. Kindly let me know if it is convenient for you.

0nephoapp said on March 10, 2011

I have some questions regards to the codes

In the for iteration it seems have some problems.

For example when m=0 n=0, a=P[2][0] which is not calculated yet.

0lipingwu said on August 6, 2011

P[2][0] is 0, which is calculated already when initializing the P.

0anon said on March 11, 2011

Lets say the set is {1,2,1,2,1} ; it seems that the proposed solution does not work in this case… could you elaborate on this ?

01337c0d3r said on March 11, 2011

You are right. This method does not work when total number of coins is odd. In that case, the game is not meaningful anyway, since the player who goes first will have an unfair advantage of getting one less coin.

0lipingwu said on August 6, 2011

The solution for the first problem doesn’t work any more. But, I think the solution for the second problem works still.

0alpha123 said on July 26, 2013

how about {1,2,1,2,1,2,1,1,2,1,2,1,2,1}? This has even number of elements and the first player loses? Right.

0speeddy said on March 13, 2011

Hi, I find that your code is not efficient here and I check you code using the input in your post. Your code will use 21 calculation to get the result 8. I use the recursion to get the result with 9 calculation. Not sure whether my code is right. I paste here:

#include

#include

#define MAX(A,B) ((A>=B)? A: B)

#define MIN(A,B) ((A<B)? A: B)

int coin_input[] = {3, 2, 2, 3, 1, 2};

int P2[7][7] = {0};

static int counter = 0; //counter how many times

int maxMoney2(int A[], int P[7][7], int i, int j) {

if ((i <0) || (j j))

return 0;

if (P2[i][j] == 0) {

counter ++;

P2[i][j] = MAX(A[i] + MIN(maxMoney2(A, P2, i+2, j), maxMoney2(A, P2, i+1, j-1)),

A[j] + MIN(maxMoney2(A, P2, i+1,j-1), maxMoney2(A, P2, i, j-2)));

}

return P2[i][j];

}

int main()

{

int value;

value = maxMoney2(coin_input, P2, 0, 5);

printf(“The max money is %d, total calculation: %d\r\n”, value, counter);

}

01337c0d3r said on March 13, 2011

Essentially the number of calculations should be the same, the only difference is the top-down vs. bottom-up approach. I found that in your code, you only increase the counter when P2[i][j] == 0. If the index of i is out of bound, you return 0 without increasing the counter. Are you using the same method when comparing your code to my code? I would say the majority of extra counts you claimed is spent setting the values to 0.

0speeddy said on March 13, 2011

Hi, thanks for your quick reply. I have compare my code and your code very carefully. I dump my P matrix and your P matrix to compare and then know the reason.

Your P matrix:

3 3 5 5 6 8

0 2 2 5 5 5

0 0 2 3 3 5

0 0 0 3 3 4

0 0 0 0 1 2

0 0 0 0 0 2

My P matrix:

0 3 0 5 0 8

0 0 2 0 5 0

0 0 0 3 0 5

0 0 0 0 3 0

0 0 0 0 0 2

0 0 0 0 0 0

So you could see that i resolve fewer subproblem as yours.

You resoleve the sub problem P[1,1],P[1,4]…..

We both get the final correct answer 8. But my P matrix could not let me print our the move as yours.

But I could not convince myself why I need to resolve the sub problem P[1,4]……

0speeddy said on March 13, 2011

Maybe you could give me some hints and let me print out my move as yours. Thanks very much.

0lipingwu said on August 6, 2011

Just use the the same function of printing the order. The sub problems that were not computed will not be referred to either in the print function. Also, your solution is indeed more efficient than the 1337′s, I think, which is also the advantage of recursion with memoization that only related sub problems are solved.

0codingC said on May 28, 2011

The reason is that you dont need to compute P[i,j] where j-i+1 is odd. Because it is never used.

0codingC said on May 28, 2011

@speeddy: After further thoughts, your way to measure is misleading. Although your P matrix has fewer elements, setting P[][] takes four comparisons. The OP’s solution only takes two comparisons to set P[][]. Thus the number of elements in P matrix is not a good measurement.

0xTristan said on April 2, 2011

Great detailed analysis. Your website is very helpful.

One nitpick:

“Although the above recurrence relation could be implemented in few lines of code, its complexity is exponential. ” i think you meant polynomial.

Keep the good job up!

0xTristan said on April 2, 2011

I took a look at your code and it doesn’t seem correct.

Line 30-32, you are now calculating P[m][n]. But in order to do that, you need P[m+2][n], which has not been calculated at this time because your m is only going up when n remains the same.

I think you meant to use a recursive function instead of referencing P[m+2][n] directly.

Take a counter example. Say N = 10. At the step m = 0, n =3

a = P[2][3] because 0+2 <= 10 -1,

b = P[1][2] because 0+1 =0

c = P[0][1] because 3-2 >= 0

At this time, P[2][3] has not been calculated yet, “a” would be zero. This is wrong because:

1. coin value are positive numbers. So in theory P[2][3] should definitely > 0.

2. your P[0][3] would be incorrect as a result of that because it fails to calculate the case when you take coin m and your opponent takes coin m-1.

0lipingwu said on August 6, 2011

I think the 1337′s codes used the bottom-up approach, and it starts with the sub problems with fewer coins in the range. So P[m+2][n] actually is computed before P[m][n] since there are fewer coins considered when compute P[m+2][n] than P[m][n].

0anonymous said on December 13, 2011

I am also confused here. you still need P[m+2][n] to get P[m][n] doesn’t matter top down or bottom up.

0anonymous1 said on June 4, 2011

@1337c0d3r: Thankx for posting the explanations for these questions. This is really helpful .

I am wondering if you can also start adding some comments in your code, because sometimes it might get difficult to understand it to some newbies. e.g: In this case, I am trying to understand how a 2-d array P is used and populated to lookup intermediate answers. I will post back with more specific query, but this is just a request.

Thanks

0newbie001 said on June 26, 2011

We can use the similar “for loops” of matrix multiplication in CLRS books. Thus P[i+2, j] … can be calculated before P[i,j].

The main idea is:

for len: 2->n increment by 2

for i: 1 -> n-len+1

j = n – i – 1;

……

0Yifan said on August 4, 2011

As the second question only ask for maximum, can we do this:

(minnor change on your first solution without calculate sum)

int MaximunValue(int[] coins, int i, int j){

//i is start index, j is end index

if ( i== j ) { return coins[i]; }

else {

return Max(coins[i] + Max(MaximumValue(coins, i+2, j), MaximumValue(coins, i+1, j-1)),

coins[j] + Max(MaximumValue(coins, i+2, j-1), MaximumValue(coins, i+1, j-2));

}

}

0lipingwu said on August 6, 2011

This would be a solution using recursion but without memoization, which will have exponential time since many sub problems will be solved repeatedly. This is also why we use dynamic programming to avoid the duplicate solving of sub problems and to be more efficient.

+1lipingwu said on August 6, 2011

If the opponent is very dumb, I think, we need to compute the amount of the money picked for all the ways of picking and find the maximal amount. Following are my codes. And how do you think?

void pickCoinsDumb(int A[], int l, int r, int sum, int *maxMount){

if(l > r){ *maxMount = max(*maxMount, sum); return; }//No coin left, then compare the new sum with the maxMount

if(l == r){ *maxMount = max(*maxMount, sum+A[l]); return; }//Only one coin left, then pick it and then compare the new sum with the maxMOunt

pickCoinsDumb(A, l+2, r, sum+A[l], maxMount);//l and l+1 coins are picked in turn.

pickCoinsDumb(A, l+1, r-1, sum+A[l], maxMount);//l and r coins are picked in turn

pickCoinsDumb(A, l+1, r-1, sum+A[r], maxMount);//r and l coins are picked in turn

pickCoinsDumb(A, l, r-2, sum+A[r], maxMount);//r and r-1 coins are picked in turn

}

int pickCoinsDumb(int A[], int n){

if(A == NULL || n == 0) return 0;

int maxMount = 0;//initialize the maxMount into 0 first;

pickCoinsDumb(A, 0, n-1, 0, &maxMount);

return maxMount;

}

0iezhr said on October 13, 2011

I think for the dumb opponent problem, we only need to change the way to formulate the DP:

P1 = Ai + max { P(i+2, j), P(i+1, j-1) }

P2 = Aj + max { P(i+1, j-1), P(i, j-2) }

Therefore,

P(i, j) = max { P1, P2 }

= max { Ai + max { P(i+2, j), P(i+1, j-1) },

Aj + max { P(i+1, j-1), P(i, j-2) } }

So only small changes to the original codes.

0Anonymous said on September 1, 2011

Can’t understand properly how the 2-D array P is generated.please explain !!!

0lamothy said on February 18, 2012

The explanation is very clear. What an amazing work!

Btw, I modified the code a little. Instead of calculating the whole matrix P[N][N], I only calculate half of it. The printmoves function is also modified. The code is listed below. Any comments are welcome. Thank you in advance!

int A[N];

void printmoves(int P[][N]){

int i=0,j=N-1;

while(j>i){

cout<<"I pick "<<(P[i][j]==A[i]+min(P[i+2][j],P[i+1][j-1])? A[i++]:A[j--])<<endl;

cout<<"You pick "<<(P[i+1][j]<P[i][j-1]? A[i++]:A[j--])<<endl;

}

}

int main(){

int i, j, k,P[N][N];

srand(time(0));

for (i=0; i<N; ++i)

{ A[i]=rand()%100; cout<<A[i]<<" ";}

cout<<endl;

/*The main function of calculating the optimal money is blew.*/

for (k=0, i=1; i<=N-1; i=2*(++k)+1)

for (j=0; j+i<= N-1; ++j)

P[j][i+j]= max(A[j]+min(P[j+2][i+j], P[j+1][i+j-1]), A[i+j]+ min(P[j+1][i+j-1],P[j][i+j-2]));

printmoves(P);

cout<<"The optimal amount of money for the first player is "<<P[0][N-1]<<endl;

}

0lamothy said on February 18, 2012

For the case that the opponent can be manipulated, we just need to replace “min” by “max” in the code above.

0Anonymous said on April 14, 2012

A great solution indeed.

I just wanted to ask one thing that what is the invariant outermost loop i is mantaining in the above. Like in the dp Matrix multiplication we have the outermost loop mantains the length of the matrix. Clearly inner loop m and n denote the left and right position to take the coin.

And why is that the answer is in a[0][n-1] .. Magic ??

0Anon said on May 9, 2012

So, I have a similar problem for an assignment that I’ve been trying to work with. Can anyone shed some light on it? It’s the same problem, except each player can only pick 2 coins from one side in a row. Thanks! I get this solution, but I cannot figure out how to extend it at all.

0Davy said on August 16, 2012

Could you explian how to solve the further thoughts? I changed the recurrence relation to be

P(i, j) = max { P1, P2 }

= max { Ai + max { P(i+2, j), P(i+1, j-1) },

Aj + max { P(i+1, j-1), P(i, j-2) } }

But I got the the wrong answer. I don’t know why

Could you help me?

my email :caidawei12345@126.com

0Xiaolong Jiang said on October 6, 2012

impressive

0roger said on January 4, 2013

following piece of code implement the same idea, but might be easier to understand as it doesn’t need handle those coner cases, and it is more similar to the MATRIX CHAIN problem.

+1Xrismas said on January 7, 2013

what’s the first for loop mean?

0roger said on January 7, 2013

first loop means that the first guy will grab it if that is the only item,

second loop means the first guy will grab the largest one of two items.

0Xrismas said on January 8, 2013

Sorry, I meant the first loop of the last 2 loops, I am not totally understand this loop.

for (s=2;s<N;s++) //step size

{

for (i=0;i<N-s;i++)

{

j = i+s;

max_v[i][j] = max ( (val[i] + min(max_v[i+2][j],max_v[i+1][j-1])),

(val[j] + min(max_v[i][j-2],max_v[i+1][j-1]))); } }

0Xrismas said on January 8, 2013

could u pls explain the last part of your code?

I understand the transfer equations..

0roger said on January 12, 2013

Basically, it is trying to build a table from bottom up, starting from 1 coin, 2 coins, then 3 coins (s=2), 4 coins (s=3), util it build table for N coins (s=N-1)

0the simpsons movie 2007 said on February 21, 2013

L’Oreal For Men, Macho Maybelline, Elizabeths Boxers. Haunted House Ride Video. It’s likely that my attitude around it came, on some level, from knowing that

I still liked boys.

0frank said on May 17, 2013

Here is my c++ code.

0coder said on June 1, 2013

this is an excellent post about solving a DP problem. My understanding of DP is better after reading this post and doing exercises mysefl

0ZhigangZhao said on July 27, 2013

it is a good problem and analysis and solution are perfect .but it is not logical.the opponent already knows that he will lose the game at first .there is no need for him to make reasonable decisions during the game,isn’t it? it is useless.so why we can assume that the opponent will try his best to make a good choice?

0Hardy said on September 13, 2013

Just want to contribute my code for the first solution (computation is done in diagonal order):

0GuojiaAgain said on January 22, 2014

Actually, basic idea of min-max tree in AI.

0theOtherWC said on January 30, 2014

One question regarding the first solution.

Why can that guarantee no lose？

What if the sequence of coin is 1 1 5 1? Going second will win.

0theOtherWC said on February 16, 2014

Oops…

0Max said on February 2, 2014

0Ankit said on February 13, 2014

Interesting problem, but I wonder if this is a good question to ask in an interview. Would you expect someone to solve this problem in 45 mins along with coding and border scenarios in an efficient way ? Personally, I found it difficult to understand (not the concept), but the code. What do you guys think ?

0William Li said on August 4, 2014

It’s possible to further refine the algorithm such that it takes O(n^2) time and O(n) space by the observation that only the previous diagonal is needed for calculation of the next one.

0