Question

Consider the following game. A “dealer” produces a sequence ${\mathit{s}}_{\mathbf{1}}\mathbf{}\mathbf{·}\mathbf{}\mathbf{·}\mathbf{}\mathbf{·}\mathbf{}{\mathit{s}}_{\mathbf{n}}$ of “cards,” face up, where each card ${\mathbf{s}}_{\mathbf{i}}$ has a value ${\mathbf{v}}_{\mathbf{i}}$. Then two players take turns picking a card from the sequence, but can only pick the first 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 $\mathbf{n}$ is even. (a) Show a sequence of cards such that it is not optimal for the first player to start by picking up the available card of larger value. That is, the natural greedy strategy is suboptimal. (b) Give an $\mathbf{O}\left(n^2\right)$ algorithm to compute an optimal strategy for the first player. Given the initial sequence, your algorithm should precompute in $\mathbf{O}\left(n^2\right)$ time some information, and then the first player should be able to make each move optimally in $\mathbf{O}\left(1\right)$ time by looking up the precomputed information.

Short answer

1. The sequence of cards is $\left(2,10,3,1\right)$.
2. we will provide an algorithm which give optimal solution.

Step-by-step solution

Define Greedy Algorithms

In greedy algorithms, the solution to the problem is obtained by picking a best option at the moment. At each stage of the algorithm, local optimal choice is selected. The aim of the question is to give sequence for the given game in which greedy approach will not give optimal solution.

Determine the sequence for which greedy approach fails

Consider a card sample with values: $\left(2,10,3,1\right)$. Consider First player and Second player be $P_1$ and $P_2$ respectively.

$P_1$picks the card with value $2$. Card remaining: $\left(10,3,1\right)$

And then $P_2$ picks the card:$10$. Card remaining: $\left(3,1\right)$

Now $P_1$ will pick card:$3$.

And finally $P_2$ will pick remaining last card: $1$

Now, add the total value of player $P_1$ and $P_2$.

$P_1=2+3=5$

Whereas,

$P_2=10+1=11$

So player $P_1$ loose, this proves that greedy approach is not optimal for first player for sequence $\left(2,10,3,1\right)$.

Create recursive formula

Let $OPT\left(i,j\right)$ be the score difference between largest total score of first player and the corresponding score of second player for sequence$s_i\dots s_j$.

There are two choices for first player:

• Either picks the first card to gaining score $v_i,-OPT\left(i+1,j\right)$ in the next game.
• Pick the last to gain score $v_j,\text{\hspace{0.33em}cmd}-OPT\left(i,j-1\right)$ from remaining cards

So, the recursive equation is:

$OPT\left(i,j\right)=\left\{\begin{array}{c}max\left\{\left({\text{v}}_{\text{i}}-\text{OPT}\left(\text{i}+1,\text{j}\right)\right),\left({\text{v}}_{\text{j}}-OPT\left(\text{i},\text{j}-1\right)\right)\right\}\\ {\text{v}}_{\text{i}};ifi=j\end{array}\right.$

Determine an algorithm

The algorithm is as follows:

$\begin{array}{l}\text{for}\left(i=1\text{to\hspace{0.33em}}n\right)\\ OPT\left(i,i\right)=v_i\\ \text{for}\left(j=1\text{to\hspace{0.33em}}n\right)\\ \text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}for}\left(i=j\text{\hspace{0.33em}to\hspace{0.33em}}1\right)\end{array}$

$\begin{array}{l}OPT\left(i,j\right)=max\left\{\left(v_i-OPT\left(i+1,j\right)\right),v_j-OPT\left(i,j-1\right)\right\}\\ \text{return\hspace{0.33em}}OPT\left(1,n\right)\end{array}\begin{array}{l}OPT\left(i,j\right)=max\left\{\left(v_i-OPT\left(i+1,j\right)\right),v_j-OPT\left(i,j-1\right)\right\}\\ \text{return\hspace{0.33em}}OPT\left(1,n\right)\end{array}$

Determine the runtime of the algorithm

Each update takes $O\left(n\right)$. There are two inner loops that run n times each, which takes run time $O\left(n^2\right)$.

Thus, the time complexity is $O\left(n^2\right)$.