Coins in a Line

February 9, 2011 in dynamic programming

There are n coins in a line. (Assume n is 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.

  1. Would you rather go first or second? Does it matter?
  2. 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.

U.S. coins in various denominations in a line. Two players take turn to pick a coin from one of the ends until no more coins are left. Whoever with the larger amount of money wins.

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.

The remaining coins are { Ai … Aj } and it is your turn. Let P(i, j) denotes the maximum amount of money you can get. Should you choose Ai or Aj?

Assume that P(i, j) denotes the maximum amount of money you can win when the remaining coins are { Ai, …, Aj }, and it is your turn now. You have two choices, either take Ai or Aj. First, let us focus on the case where you take Ai, so that the remaining coins become { Ai+1 … Aj }. 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 Ai, the maximum amount you can get is:

P1 = Sum{Ai ... Aj} - P(i+1, j)

Similarly, if you choose Aj, the maximum amount you can get is:

P2 = Sum{Ai ... Aj} - P(i, j-1)

Therefore,

P(i, j) = max { P1, P2 }
        = max { Sum{Ai ... Aj} - P(i+1, j),
                Sum{Ai ... Aj} - P(i, j-1) }

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

P(i, j) = Sum{Ai ... Aj} - 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{Ai … Aj} in each step, which is not very efficient. To avoid this problem, we can store values of Sum{Ai … Aj} 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{Ai … Aj}, therefore is more efficient in terms of time and space. Let us rewind back to the case where you take Ai, and the remaining coins become { Ai+1 … Aj }.

You took Ai from the coins { AiAj }. The opponent will choose either Ai+1 or Aj. Which one would he choose?

Let us look one extra step ahead this time by considering the two coins the opponent will possibly take, Ai+1 and Aj. If the opponent takes Ai+1, the remaining coins are { Ai+2 … Aj }, which our maximum is denoted by P(i+2, j). On the other hand, if the opponent takes Aj, 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 Ai is:

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

Similarly, the maximum amount you can get when you choose Aj is:

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

Therefore,

P(i, j) = max { P1, P2 }
        = max { Ai + min { P(i+2, j),   P(i+1, j-1) },
                Aj + 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(n2) time and takes O(n2) 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).

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?

VN:F [1.9.22_1171]
Rating: 4.7/5 (28 votes cast)
Coins in a Line, 4.7 out of 5 based on 28 ratings

56 responses to Coins in a Line

  1. 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

    VA:F [1.9.22_1171]
    -1
  2. 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?

    VA:F [1.9.22_1171]
    +3
  3. @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).

    VA:F [1.9.22_1171]
    0
  4. @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!

    VA:F [1.9.22_1171]
    0
  5. @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.

    VA:F [1.9.22_1171]
    0
  6. @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.

    VA:F [1.9.22_1171]
    0
    • @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.

      VA:F [1.9.22_1171]
      0
  7. 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.

    VA:F [1.9.22_1171]
    0
  8. 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 ?

    VA:F [1.9.22_1171]
    0
    • 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.

      VN:F [1.9.22_1171]
      0
    • The solution for the first problem doesn’t work any more. But, I think the solution for the second problem works still.

      VA:F [1.9.22_1171]
      0
      • 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.

        VN:F [1.9.22_1171]
        0
  9. 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);
    }

    VA:F [1.9.22_1171]
    0
    • 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.

      VN:F [1.9.22_1171]
      0
      • 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]……

        VA:F [1.9.22_1171]
        0
        • Maybe you could give me some hints and let me print out my move as yours. Thanks very much.

          VA:F [1.9.22_1171]
          0
          • 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.

            VA:F [1.9.22_1171]
            0
      • The reason is that you dont need to compute P[i,j] where j-i+1 is odd. Because it is never used.

        VA:F [1.9.22_1171]
        0
        • @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.

          VA:F [1.9.22_1171]
          0
  10. 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!

    VA:F [1.9.22_1171]
    0
  11. 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.

    VA:F [1.9.22_1171]
    0
    • 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].

      VA:F [1.9.22_1171]
      0
      • 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.

        VA:F [1.9.22_1171]
        0
  12. @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

    VA:F [1.9.22_1171]
    0
  13. 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;
    ……

    VA:F [1.9.22_1171]
    0
  14. 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));
    }
    }

    VA:F [1.9.22_1171]
    0
    • 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.

      VA:F [1.9.22_1171]
      +1
  15. 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;
    }

    VA:F [1.9.22_1171]
    0
    • 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.

      VN:F [1.9.22_1171]
      +1
  16. Can’t understand properly how the 2-D array P is generated.please explain !!!

    VA:F [1.9.22_1171]
    0
  17. 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;
    }

    VN:F [1.9.22_1171]
    0
  18. For the case that the opponent can be manipulated, we just need to replace “min” by “max” in the code above.

    VN:F [1.9.22_1171]
    0
  19. 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 ??

    VA:F [1.9.22_1171]
    0
  20. Anon 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.

    VA:F [1.9.22_1171]
    0
  21. 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

    VN:F [1.9.22_1171]
    0
  22. impressive

    VN:F [1.9.22_1171]
    0
  23. 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.

    VA:F [1.9.22_1171]
    +1
    • what’s the first for loop mean?

      VA:F [1.9.22_1171]
      0
      • 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.

        VN:F [1.9.22_1171]
        0
        • 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]))); } }

          VA:F [1.9.22_1171]
          0
        • could u pls explain the last part of your code?

          I understand the transfer equations..

          VA:F [1.9.22_1171]
          0
          • 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)

            VN:F [1.9.22_1171]
            0
  24. 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.

    VA:F [1.9.22_1171]
    0
  25. Here is my c++ code.

    VN:F [1.9.22_1171]
    0
  26. this is an excellent post about solving a DP problem. My understanding of DP is better after reading this post and doing exercises mysefl

    VA:F [1.9.22_1171]
    0
  27. 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?

    VN:F [1.9.22_1171]
    0
  28. Just want to contribute my code for the first solution (computation is done in diagonal order):

    VN:F [1.9.22_1171]
    0
  29. Actually, basic idea of min-max tree in AI.

    VN:F [1.9.22_1171]
    0
  30. 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.

    VA:F [1.9.22_1171]
    0
  31. VN:F [1.9.22_1171]
    0
  32. 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 ?

    VN:F [1.9.22_1171]
    0
  33. 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.

    VA:F [1.9.22_1171]
    0
  34. The first solution that ensures winning will be useful only when the original total number of coins is even. If the total number of coins is odd, then you cannot force your opponent to only choose odd numbered or even numbered coins.

    VN:F [1.9.22_1171]
    0

Leave a reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.