There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.
Solution:
this looks like a Dynamic Programming problem. Say M(i, j) is the maximum when there are the coins from i to j available. In this case I have 2 options.
Pick from A[i], so i get value A[i]. The other player takes either A[j] or A[i+1] leaving me the options either for M(i+1, j-1) or M(i+2, j). The other player will try to minimize my gains so he will chose min(M(i+1, j-1), M(i+2, j))
Pick from A[j], so i get value A[j]. The other player takes either A[i] or A[j-1] leaving me the options either for M(i+1, j-1) or M(i, j-2) and again the other player will try to minimize my choices min(M(i+1, j-1), M(i, j-2))
I select the two above trying to maximize my ROI, so the total formula would be
max (A[i]+min(M(i+1, j-1), M(i+2, j)), A[j]+min(M(i+1, j-1), M(i, j-2)))
Pretty cool isnt'it?
Standard memoization is suggested
The solution you presented looks like an O(n^2). However, this problem can be done in O(n log n).
ReplyDelete1. Observe that whenever the coin of highest value is available at one of the ends of the line, it is always optimal to take this coin. This can be easily proven by induction.
2. Observe that it suffices to compute the optimum value of a situation i.e. the maximum amount of (money you get minus money your opponent gets). There are easy formulas converting ROI to value and back.
3. Consider the following O(n log n) that reduces the computation of the value V of a situation to a computation of the a value V' of a similar smaller situation. The are two following cases.
a) The coin of highest value v is available at one of the ends. Then V=v-V', where V' is obtained from V by removing the available coin.
b) The coin of highest value v is between two coins of values a and b, respectively. The V=V', where V' is obtained from V by replacing the subsequence (a,v,b) by (a+b-v).
4. The computation ends after at most n steps (we reach an empty situation with value 0).