Consider the following game. A dealer produces a sequence s1 sn of cards, face u

Question

Consider the following game. A dealer produces a sequence s1 sn of cards, face up, where each card si has a value vi. Then two players take turns picking a card from the sequence, but
can only pick the rst or the last card of the (remaining) sequence. The goal is to collect cards of
largest total value. (For example, you can think of the cards as bills of different denominations.)
Assume n is even.

Give an O(n^2) algorithm to compute an optimal strategy for the rst player. Given the
initial sequence, your algorithm should precompute in O(n^2) 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

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.