#cs/cp #review ## Summary Let $N = [n_0, n_{1}, \dots, n_k]$. Alice and Bob alternate turns, with Alice moving first. On each turn, the player removes a nonempty subarray that is shorter than the current array. This repeats until one number remains. Alice wants the final number to be as large as possible, while Bob wants it to be as small as possible. Assuming both players play optimally, what is the final number? ## Idea: Only the Endpoints Matter The result is simply $ \max(n_0, n_k). $ Alice can achieve this immediately by deleting every element except the larger endpoint. She cannot force a larger interior value: after any first move that does not end the game, at least one original endpoint remains an endpoint of the new array, and Bob can end the game by keeping that endpoint. Thus Alice can guarantee, but cannot exceed, the larger original endpoint. The prefix walkthrough below reaches the same result by tracking the best outcome when either player moves first. Let $N = [6,2,4,9,3,5]$. For each prefix, track the largest final number Alice can achieve when she moves first and the smallest final number Bob can achieve when he moves first. $i=0$ $ [6] $ $ \frac{\text{(First) Alice's Best Outcome \qquad}}{6} \quad \quad \quad \quad \quad \quad \frac{\text{(First) Bob's Best Outcome \quad}}{6} $ The final number is $6$ regardless of who moves first. ---- $i=1$ $ [6,2] $ $ \frac{\text{Alice \qquad \qquad}}{6} \quad \quad \quad \quad \quad \quad \frac{\text{Bob \qquad \qquad \quad \quad}}{2} $ The final number is $6$ if Alice moves first and $2$ if Bob moves first. ---- $i=2$ $ [6,2,4] $ $ \frac{\text{Alice \qquad \qquad}}{6} \quad \quad \quad \quad \quad \quad \frac{\text{Bob \qquad \qquad \quad \quad}}{4} $ The final number is $6$ if Alice moves first and $4$ if Bob moves first. Bob can delete $[6,2]$ and leave $4$ immediately; deleting $4$ instead would leave $[6,2]$ for Alice and result in $6$. ---- $i=3$ $ [6,2,4,9] $ $ \frac{\text{Alice \qquad \qquad}}{9} \quad \quad \quad \quad \quad \quad \frac{\text{Bob \qquad \qquad \quad \quad}}{6} $ Alice can leave $9$ immediately. Bob compares $9$ with Alice's previous final outcomes $(6,6,6)$, so his best result is $6$; for example, he can delete $[2,4,9]$ and leave $6$. ---- $i=4$ $ [6,2,4, 9,3] $ $ \frac{\text{Alice \qquad \qquad}}{6} \quad \quad \quad \quad \quad \quad \frac{\text{Bob \qquad \qquad \quad \quad}}{3} $ Alice compares $3$ with Bob's outcome for $i=3$, which is $6$. Since $6$ is larger, it is better to remove $3$. Bob compares the current element, $3$, with all of Alice's previous results ($9,6,6,6$). Since Bob wants to minimize the final number, he leaves $3$. --- $i=5$ $[6,2,4,9,3,5]$ $\frac{\text{Alice \qquad \qquad}}{6} \quad \quad \quad \quad \quad \quad \frac{\text{Bob \qquad \qquad \quad \quad}}{5}$ Alice compares the new number, $5$, with Bob's previous outcomes ($3,6,4,2,6$). The maximum she can achieve is $6$ by leaving Bob with the prefix from $i=3$ or $i=0$. Bob compares $5$ with Alice's previous outcomes ($6,9,6,6,6$). The minimum he can achieve is $5$. ---