Digital Garden
Computer Science
Algorithms & Data Structures
Dynamic Programming
Coins in a Line

Coins in a Line

This game is a tricky little coding problem that works has the following rules:

  • There are an even number nn of coins in a line, with values v1,v2,...,vnv_1, v_2, ..., v_n, i.e. viv_i is the value of the i-th coin.
  • Two players, often called Alice and Bob, take turns to take a coin either from the left or the right end of the line until there are no more coins left.
  • The player whose coins have the higher total value wins.
Coins in a Line Game.

The goal is to find an algorithm that maximizes the value of the coins that the first player (Alice) gets.

Example

There are 4 coins with values [1, 2, 3, 4], Alice will get the maximum value of 6 by taking the last coin twice (4 + 2), assuming Bob also plays optimally.

Greedy Algorithm

This game isn't as simple as it seems, and it's not immediately obvious how to solve it. Most commonly people will start with a greedy algorithm, which is to take the coin with the highest value at each turn. This is a good start, and will win in the example above, but it's not optimal. Consider the following example:

Example

There are again 4 coins but with the values [5, 10, 25, 10].

  1. Alice takes the right coin with value 10.
  2. Bob takes the right coin with value 25.
  3. Alice takes the right coin with value 10.
  4. Bob takes the last coin with value 5.

Alice will have a total value of 20, and Bob will have a total value of 30. Bob wins!

By tweaking the greedy algorithm, we can get an algorithm that will always win, but not necessarily get the maximum value. Instead of taking the coin with the highest value, Alice first calculates the total value of coins in the odd positions, and then calculates the total value of coins in the even positions (starting at 0). She then takes the coin in the positions with the highest total sum.

Example

There are again 6 coins but with the values [1,3,6,3,1,3]. First Alice calculates the total value of coins in the even positions, which is 1 + 6 + 1 = 8. Then she calculates the total value of coins in the odd positions, which is 3 + 3 + 3 = 9. So she takes the coins in the odd positions. If Bob uses the greedy approach we get the following:

  1. Alice takes the right coin with value 3 (original position=5).
  2. Bob takes the left coin with value 1.
  3. Alice takes the left coin with value 3 (original position=1).
  4. Bob takes the left coin with value 6.
  5. Alice takes the left coin with value 3 (original position=3).
  6. Bob takes the last coin with value 1.

Alice will have a total value of 9, and Bob will have a total value of 8. Alice wins, but there is a way to get 10!

If Bob uses the same tweaked greedy approach as Alice, we get the following:

  1. Alice takes the right coin with value 3 (original position=5).
  2. Bob can't take an odd position coin, so he can take either coin as they are both odd positions and have the same value. Let's say he takes the left coin with value 1 because he built his algorithm to scan from left to right.
  3. Alice takes the left coin with value 3 (original position=1).
  4. Bob again can't take an odd position coin, but he takes the left coin with value 6 because it has a higher value than the right coin with value 1.
  5. Alice takes the left coin with value 3 (original position=3)
  6. Bob takes the last coin with value 1.

The result is the same as if Bob used the normal greedy approach, because Alice always take the coins away from Bob as she gets to go first.

Dynamic Programming Algorithm

We always assume that Bob will play optimally, optimally meaning that he will always take the coin which minimizes the total amount of coins that Alice can get.

Longest Increasing SubsequenceGeneral Definition