(Feb 24, 2015 03:51 PM)Trisomy 21 Wrote:  I don't understand how this is possible if coins have random values, and you didn't specify the possible number values of the coins.

(Feb 24, 2015 04:32 PM)DevinFSP Wrote:  If player one is the first person to pick and it's a two-person game, then he will pick the coins 1, 3, 5, 7, 9, 11, etc. From the vague information you gave, just have the odd coins valued at 2 and the even coins valued at 1. That way, player one will always have more points than player two.

Although I'm pretty that's not what you meant, that's what it appears to other people. So either I'm right or you need to clear up your problem/challenge.

(Feb 24, 2015 05:28 PM)DаrkStorm Wrote:  You can use a recursive solution with memoization:

Code

int[][] memo = ...
int[] values = ...

int choose(int l, int r) {
    if(l > r) return 0;
    if(memo[l][r] != -1) return memo[l][r];

    int takeBothLeft = choose(l + 2, r);
    int takeLeftRight = choose(l + 1, r - 1);
    int takeBothRight = choose(l, r - 2);
    int startVal = values[l] + Math.min(takeBothLeft, takeLeftRight);
    int endVal = values[r] + Math.min(takeLeftRight, takeBothRight);
    int best = Math.max(startVal, endVal);

    return memo[l][r] = best;
}

This assumes both take optimally. For an odd number of moves a win/tie is not guaranteed.

I like the cases:

Code

1 1 5 1

and

Code

1 5 1 1

(Feb 24, 2015 06:15 PM)Leostraza Wrote:  I think I got it..

Code

int scoreP1, scoreP2, numCoins;
for (int i = 0; i < numCoins; i++) {
  if (i % 2 == 0) {
    scoreP1 += i;
  } else {
    scoreP2 += i;
  }
}

As you can see, P1 will always have the higher score.
100 + 98 + 96...

P2: 99 + 97 + 95...

(Feb 25, 2015 04:40 AM)caudex Wrote:  Still cant get the point. You say there is a row of coins with random to-the-players-unknown values. If so, how can there be a strategy to win?

As I understood this:
- A random row starting anywhere and ending anywhere
- The row got an even coin-count (lets say 4 to make it easy understanding MY problem with this)
- Each player picks a coin from one of the ends

From that point lets take two examples:
1| 4 - 6 - 5 - 3 (a range from 3-6)
2| 12 - 11 - 10 - 13 (10-13)

As the players dont know the values, instead of this only the range, they cant choose effectivly where to pick the next coin. So for the first game it would look like X - X - X - X to the players. How should they get any difference into that to build up a strategy?

(Feb 25, 2015 08:03 AM)AstroJack Wrote:  The players DO know the values, that's the whole point.
I don't think I mentioned they don't know the values.

(Feb 25, 2015 08:03 AM)AstroJack Wrote:  The players DO know the values, that's the whole point.
I don't think I mentioned they don't know the values.

(Feb 25, 2015 11:46 AM)▁▂▃▄▅▆M1kep▆▅▄▃▂▁ Wrote:  Please rewrite the first post, makes no sense to anybody

(Feb 25, 2015 01:04 PM)AstroJack Wrote:  Can't edit the post, 1440 mins has passed.
But I don't really understand what isn't clear.
I think the rules&who wins are said just fine, and I 'added' that players know each value of each coin.. That's about it.

(Feb 25, 2015 01:04 PM)Massive Wrote:  You really need to specify that the players can see the values after they are randomized. I nor my team understood this post.

Kind Regards,
Massive

(Feb 25, 2015 02:12 PM)▁▂▃▄▅▆M1kep▆▅▄▃▂▁ Wrote:  Ok.... Then wouldn't the best approach be to pick from the end the had the higher value?

(Feb 25, 2015 02:17 PM)SunnyAkuma Wrote:  We can just take an array with size even, Sort it in ascending order , then Player1 start picking coins from the End and Player2 starts picking from the beginning one by one.
IF that's what you meant by "Each player, in his turn, takes a coin from one of the ends of the row".
well here , Player 1 will win even if player2 decides to pick coins from the end.

Since player1 starts first , and picks the last coin which is the largest cause we sorted the array,
Then Player2 decides from whichever end he wants to pick up the coin,

Basically , player1 will always pick from the end , and even if player 2 does the same , Player1 will still win cause he started first and the largest number came to his pocket.

If all numbers are same in the array , then it'll always be a draw because the length of the array is even. Both players will end up with exactly same number of coins with same value.