You pass a carnival booth and the man operating the booth asks you to try his ga

Question

You pass a carnival booth and the man operating the booth asks you to try his game. He lays out an even number of coins, n, in an array. Each coin has an associated value v_1, .., v_n. In this game, you and the man take turns picking up either the first coin or the last coin in the array and adding it to your stash. The person with the most money at the end of the game wins. You are the first player to take a coin, and the game goes on until no coins remain. Give an algorithm to determine the maximum amount of money you will have in your stash if your opponent plays optimally.

Explanation / Answer

There are 2 possibilities in this case:

1.) You choosing the (i)th coin with the value (v)i . The Man choosing (i+1)-th or (j)th coin. i.e., the Man intent to choose the coin with greater value leaving the minimum value coin to You.

2.) You choosing the (j)th coin with value (v)j. Like previous the Man is intend to choose the coin which leaves the you with minimum value.

Consider the following example:

5,3,8,9,2,6

user--> 6

5,3,8,9,2

opponent--> 5

3,8,9,2

user--> 6+ 3

opponent --> 5+8

9,2

user-->6+3+9 (18)

opponent --> 5+8+2(15)

User Collect Maximum

Algorithm:

Here, I'm providing a solution based on above two possibilities using dynamic programing. This solution is recursive.

first coin =x and second coin = y

If You select (x)th coin then the Man is left with either (y)th coin or the (x+1)th coin.

The value that you collect is Vx + min(F(x+2,y),F(x+1,y-1))

if You choose yth coin then the Man can choose from xth or (y-1)th coin.

The value that you collect is Vy + min(F(x+1, y-1), F(x, y-2))

Note: I mentioned the passer/user as You and the man operating the booth as the Man

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.