Consider the following card game. A dealer produces a sequence s1,...,sn of card

Question

Consider the following card game. A dealer produces a sequence s1,...,sn of cards, face up, where each card si has a positive integer value vi. Then two players take turns drawing a card from the sequence, but each player can only take the rst or the last card of the remaining sequence. The goal is to collect cards of maximal total value. Assume that n is even.

(i) Find a sequence of cards such that it is not optimal for the rst player to start by choosing the available card of largest value.

(ii) Give an O(n2) algorithm that computes an optimal strategy for the rst player. Given the initial sequence, your algorithm should pre-compute in O(n2)time, some information, and then the rst player should be able to make each move optimally in O(1) time by looking up the precomputed information

Explanation / Answer

a) 2, 100, 1, 1

If the first player picks the first card (the 2), then the second player gets the 100. However if the first player picks the last card, then he gets the 100.

b) For every i, j such that 1<= i < j <= n, we need to decide whether we should pick card i or card j, if presented with the cards i through j. To decide this, let v(i) be the value of card i and opt(i,j) be the largest sum a player can get from starting with the cards i through j and let sum(i,j) simply be the sum of the values of cards i through j. Then when presented with cards i through j a player should pick card i if and only if:

v(i) + sum(i+1, j) - opt(i+1,j) > v(j) + sum(i,j-1) - opt(i,j-1)

because the left side is what he would receive if he picked card i and the right side is what he would receive is he picked card j.

In O(n^2) we can create a table of opt(i,j) by calculating them in order of increasing interval size (j-i).

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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