## Friday, September 12, 2014

### a bit of uva: UVa 10688 - The Poor Giant

Problem Statement:
UVa 10688 - The Poor Giant

Summary:
There are $$N$$ apples, and each apples have weight $$K+1, K+2, \ldots, K+N$$. There is exactly one apple which is "sweet", and all other apples' taste is measured against the sweet apple: an apple is "bitter" iff it weighs less than sweet apple, otherwise it is a "sour" apple. For a sequence of apples, we have a function $$C(\{a_i\}, k) = \text{minimum total weight of apples eaten before encountering } a_k$$, and we want to minimize $$S = \sum_{k=1}^{N} C(\{a_i\}, k)$$.

Solution:
Rather than trying all possible sequences and simulating the eating process one by one to arrive at S (which has an exponential complexity btw), we can solve this problem by breaking it into a smaller sub problems by recursion. Furthermore, this problem exhibits an optimal substructure property, as will be clear once we have derived the recursive relationship.

Suppose we have $$M(L,R)$$ which is the minimum total weight of apples required for all $$k = L \ldots R$$. Let's say we choose $$a_i$$ ($$L \leq i \leq R$$) to be eaten first. If $$a_i$$ is the sweet apple, then the simulation will terminate. Otherwise, $$a_i$$ is not a sweet apple, hence it can be sour or bitter, then we need to find both $$M(L,i-1)$$ and $$M(i+1, R)$$ to cover both cases. We will end up with the following recursion: $$M(L,R) = min_{L\leq i \leq R} \{ (R-L+1)a_i + M(L,i-1) + M(i+1,R) \}$$.

Since there are a lot of overlapping subproblems, we can memoize the results based on the parameter $$L$$ and $$R$$. This will cut down the running time to $$O(N^3)$$.

Implementation in C++:

int dp[503][503];
int a[503];
int rec(int L, int R){
if(R <= L) return 0;
if(R-L == 1) return a[L]*2;
if(R-L == 2) return a[L+1]*3;
if(dp[L][R] != -1) return dp[L][R];
int ret = MAXINT;
for(int i=L; i<= R; ++i){
ret = min(a[i]*(R-L+1) + rec(L,i-1) + rec(i+1,R), ret);
}
dp[L][R] = ret;
return ret;
}