[AstroJack]

*not really related to Java, but I did the code to solve it with Java, so..

I've Done it optimally with O(n)
Will add more if you'd like.

The problem:
Say you have a row of coins (let's say the range is between 10-100,000, and the amount of coins is an even number)
and each coin has a number on it. (Think of the row as a double-ended queue)
Each player, in his turn, takes a coin from one of the ends of the row, and keeps it to himself. The game ends when there's no coins left.
The winner is the person who has the biggest sum of coins' values.
Player number 1 plays first.
Think of an algorithm/Write a code that will give a strategy for player number 1 to ALWAYS make him the winner, or make the game end with a tie.

It's pretty easy, I'm sure you'll figure it out quickly.
GL!

[Trisomy 21]

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.

[DevinFSP]

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.

[DаrkStorm]

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

[Leostraza]

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

[AstroJack]

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.

Let's say positive integer between 1-100, although it doesn't really matter.
The point is to think about efficiency and do it as fast as possible, even for 100,000 coins.

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.

The values of the coins are random.

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

You COULD use recursion, although this will be so slow for numbers above N coins, so it's not optimal, and definitely not O(n), like I did.

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

I'm not sure what you did there.. but the coins don't have a value by their position, their values are random.

*If the problem isn't too well-written I'm sorry, I'll re-write it soon.

[caudex]

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?

[AstroJack]

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?

The players DO know the values, that's the whole point.
I don't think I mentioned they don't know the values.

[▁▂▃▄▅▆M1kep▆▅▄▃▂▁]

The players DO know the values, that's the whole point.
I don't think I mentioned they don't know the values.

Please rewrite the first post, makes no sense to anybody

[Doug Dimmadome]

The players DO know the values, that's the whole point.
I don't think I mentioned they don't know the values.

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

[AstroJack]

Please rewrite the first post, makes no sense to anybody

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.

[▁▂▃▄▅▆M1kep▆▅▄▃▂▁]

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.

Ok.... Then wouldn't the best approach be to pick from the end the had the higher value?

[SunnyAkuma]

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.

[AstroJack]

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

I kinda thought it was obvious, because obviously you can't think of a strategy without knowing the next possible moves.
Anyways, the 2 players can see the whole row of the coins, and their attached values. Hope this clears it up.

Ok.... Then wouldn't the best approach be to pick from the end the had the higher value?

No, because what if the next coin after the one you took has a value which's 1000 times bigger than what you've picked? Probably gonna lose!

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.

You can't rearrange the coins. You can only pick one from each side every turn, and you cannot change the deck. That's the whole point.
And even if it was allowed - ordering the deck in an ascending/descending order is a minimum time complexity of O(n log n), while the optimal solution has a complexity of O(n), so it's still not qualified as an optimal solution.

Edit :
A picture to emphasize what the players see, and visual aspects might help you find the solution. I know it helped me :


Still no solution for this problem. :)

[DаrkStorm]

The problem asks: given an array of coins that are not sorted and have some random value that is potentially not unique and two players who take turns choosing from either end of the array (and thus removing the coin they choose) what strategy ensures that player 1 always either ties or wins. It's really a fairly simple question.