Question

Coins in a Line 12.4.1 The first game we consider is reported to arise in a problem that is sometimes asked during job interviews at major software and Internet companics (probably because it is so tempting to apply a greedy strategy to this game, whereas the optimal stral- egy uses dynamic programming). In this game. which we will call the coins-in-a-line game, an even number, n of coins, of various denominations from various countries, are placed in a line. Two players, who we will call Alice and Bob, take turns removing one of the coins from cither end of the remaining line of coins. That is, when i is a player's turn, he or she removes the coin at the left or right end of the line of coins and adds that coin to his or her collection. The player who removes a set of coins with larger total value than the other player wins, where we assume that both Alice and Bob know the value of each coin in some common currency, such as dollars. (See Figure 12.7.) $6 $s $2 $7 $3 $5 Alice: (1, $6), (6, $5), (4, $7 Total value $18 Bob: (2, $5), 5, 3), (3, $2 Total value $10 Figure 12.7: The coins-in-a-line game. In this instance, Alice goes first and ul timately ends up with $18 worth of coins. U.S. govemment images. Credit: U.S. Mint.

Design an O(n)-time non-losing strategy for the first player, Alice, in the coins in-a-line game. Your strategy does not have to be optimal, but it should be guaranteed to end in a tie or better for Alice.

Answer 1

Solution -:

Strategy -:

The idea is to first calculate the sum of all even place coins and sum of all odd place coins.

Then compare the both even and odd sums , Alice(First player) will make sure that if even sum is larger then bob (second player) will not be able to pick even number of coin.

Similarly Alice will make sure that if odd sum is large then bob will not be able to pick odd number of coin.

Executable Code -:

#include <iostream>
using namespace std;

void Totalworth(int arr[], int n)
{
int oddcoinSum = 0;
for (int i = 0; i < n; i += 2)
oddcoinSum += arr[i];
  
int evencoinSum = 0;
for (int i = 1; i < n; i += 2)
evencoinSum += arr[i];
  
if(evencoinSum>oddcoinSum)
{
   cout << "\nAlice worth is " << evencoinSum;
   cout << "\nBob worth is " << oddcoinSum;
   }
   else
   {
       cout << "\nAlice worth is " << oddcoinSum;
       cout << "\nBob's' worth is " << evencoinSum;
   }
}
  
int main()
{
int arr[] = {6,5,2,7,3,5} ;
int n = sizeof(arr) / sizeof(arr[0]);
Totalworth(arr, n);
  
return 0;
}

Output -:

CAUsers Shashank DesktoplUntitled2.exe Alice worth is 17 Bob worth is 11 Process exited after 0.07633 seconds with return valuee Press any key to continue . . . .

Explanation and Example -:

Coins ={6,5,2,7,3,5}

even place coin sum =5+7+5 =17

odd place coin sum =6+2+3=11

even place sum is large

So Alice will choose even place coin (Coin no 6).  

Then bob have no choice to choose only odd coin (either coin 1 or coin 5) suppose he choose coin no 1

Now Alice will choose Coin no 2

Suppose bob will choose coin no 5.

Now Alice will choose coin no.4

Now bob is left with only coin no 3

So total worth of Alice is 17

total worth of bob is 11

Alice Won ...!!!