# Coins in a Line

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.8/5 (61 votes cast)
Coins in a Line, 4.8 out of 5 based on 61 ratings

## 75 thoughts on “Coins in a Line”

1. Noob

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]
-3
2. Anonymous

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. 1337c0d3r

@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. 1337c0d3r

@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. Anonymous

@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]
-1
6. 1337c0d3r

@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]
-1
1. surebh

VA:F [1.9.22_1171]
0
7. nephoapp

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 which is not calculated yet.

VA:F [1.9.22_1171]
0
1. lipingwu

P is 0, which is calculated already when initializing the P.

VA:F [1.9.22_1171]
0
8. anon

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
1. 1337c0d3r Post author

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
2. lipingwu

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

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

Nope, you can force a tie as the first player. Imagine indexing the coins:
1 2 3 4 5 6 7 8 9 10 11 12 14
1st player’s coins: 1 3 5 7
2nd player’s coins: 2 4 6 (8 or 14)
at this point it would be {1111} vs {2221}
What would be left would be 212121 or 121212 with the first player’s turn next.
Now the first player can get {222} while the 2nd would get {111} evening things.
As long as the first player plays correctly s/he will tie. (Assuming even amount of coins).

VA:F [1.9.22_1171]
0
9. speeddy

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 = {0};
static int counter = 0; //counter how many times

int maxMoney2(int A[], int P, 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
1. 1337c0d3r Post author

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

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.

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

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

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
2. codingC

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

@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. xTristan

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]
-1
11. xTristan

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 because 0+2 <= 10 -1,
b = P because 0+1 =0
c = P because 3-2 >= 0

At this time, P has not been calculated yet, “a” would be zero. This is wrong because:
1. coin value are positive numbers. So in theory P should definitely > 0.
2. your P 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
1. lipingwu

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

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

@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. newbie001

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. Pingback: Coins in a Line | 口├人人│의 Blog

15. Yifan

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

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
16. lipingwu

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

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
17. Anonymous

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

VA:F [1.9.22_1171]
0
18. lamothy

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[N-1]<<endl;
}

VN:F [1.9.22_1171]
0
19. lamothy

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
20. Anonymous

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[n-1] .. Magic ??

VA:F [1.9.22_1171]
0
21. Anon

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
22. Davy

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
23. roger

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

what’s the first for loop mean?

VA:F [1.9.22_1171]
0
1. roger

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

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
2. Xrismas

could u pls explain the last part of your code?

I understand the transfer equations..

VA:F [1.9.22_1171]
0
1. roger

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. the simpsons movie 2007

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

Here is my c++ code.

VN:F [1.9.22_1171]
0
26. coder

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

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

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

VN:F [1.9.22_1171]
0
29. GuojiaAgain

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

VN:F [1.9.22_1171]
0
30. theOtherWC

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

Oops…

VA:F [1.9.22_1171]
0
2. qilu xie

you choose the left most coin then you obviously will win…..

VN:F [1.9.22_1171]
0
31. Max

VN:F [1.9.22_1171]
0
32. Ankit

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. William Li

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. qilu xie

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
35. Amit

i have little doubt understanding the first non-loosing strategy. Can you please help me understand in case of below example –
a[] = 3 5 2 10 1
Even Sum = Y = 5 + 10=15
Odd Sum = X = 3+ 2 +1 = 6
Y > X so, user takes = 1 and opponent takes 10.
Then we are left with 3 5 2
Now as per rule, user should select even number coin but here no choice ….?

VA:F [1.9.22_1171]
0
36. Pingback: N coins in a line | Sleeping beauty!

37. Pingback: Coins in a Line | moonstonelin

38. BD

This is a very interesting problem. Actually, if the total # of coins are odd, the first player are not guaranteed to win. See this example:
3,5,2,3,1

VA:F [1.9.22_1171]
+1
39. Pingback: coins in line | Moonstone

40. Quan

If the line is 2, 10, 1, the first mover would loose.

VA:F [1.9.22_1171]
0
41. derry

How is the dp solution related to minimax algorithm and alpha-beta pruning? This looks pretty much like it. We then can generalize the solution structure

VA:F [1.9.22_1171]
0
42. sacrishi

How to proceed for the case in which the number of total coins is odd for ensuring our win ? As in that case we cannot force ouselves or the oponent to pick only odd or even numbered coins.

VN:F [1.9.22_1171]
0
43. Bhagwant

.

VA:F [1.9.22_1171]
0
44. Pingback: Coins in a Line | 海淘好deal

45. Kim Sh

hey everyone, this is the answer i found which works for even number of coins, but here also comes the question : how can i show the choices I’ve made?
I’d really appreciate answers

VA:F [1.9.22_1171]
0
46. Prasad Prabhu

In the last part of the explanation –

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) }

Why is it min { P(i+2, j), P(i+1, j-1) } , shouldn’t it be max considering if want to maximize P1 and you have picked Ai then the next coin would you be picking should also be maximum?

VA:F [1.9.22_1171]
0
47. Milan Mansinghka

static int collectMaxAmountHelper(int startIndex, int endIndex, int[] arr,int total){
if (endIndex-startIndex == 1)
return Math.max(arr[startIndex],arr[endIndex]);
collectMaxAmountHelper(startIndex, endIndex-1, arr,total-arr[startIndex]));
}

static int collectMaxAmount(int [] arr){
int total =0;
for (int i:arr)
total+=i;
return (collectMaxAmountHelper(0,arr.length-1,arr,total) );
}

Can improve further by storing calculated values based on array’s index in a HashMap (class level).

VA:F [1.9.22_1171]
+1
48. Terry

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) }

I think this is incorrect. If the opponent is as smart as you, he will not just yield the minimum amount to you. For example, if you choose Ai, he can consider to take Ai+1 or Aj. Then your next optimum choose is P(2+1, j) or P(i+1, j-1). He can not just consider the minimum number of P(i+2, j) or P(i+1, j-1). He also needs to consider what he gets which is the value of A[i+1] and A[j]. My thought is that he will computer p[i+2, j]-A[i+1] and p[i+1, j-1] -Aj and choose the minimum one.

VA:F [1.9.22_1171]
0