nice explanation gene :) On Sep 2, 8:35 am, Gene <[email protected]> wrote: > Okay. First, you can make the DP more efficient than the one I gave > earlier. You don't need to scan the whole previous column when > calculating costs of decrementing. Rather there are only two > possibilities. > > I will add that rahul patil's solution looks correct, but it's > exponential time. DP is better for this problem. > > Remember C(n, m) is the cost of making a[1 .. n] into a non-decreasing > sequence with the last element being no more than m. And we always > draw m from the set V of values in a. > > So here is the new DP: > > C(1, m) = max(a[1] - m, 0) // first row only decrement is possible > C(n, m) = min ( > a[n] + C(n - 1, m), // delete > (a[n] <= m) ? C(n - 1, a[n]) : C(n - 1, m) + a[n] - m // decrement > ) > > In case you don't follow, the "//delete" line is saying that we > already know the cost of making everything up to element n-1 non- > decreasing and no more than m. This, by recursive assumption, is just > C(n-1,m). The additional cost of deleting a[n] is a[n]. > > The "//decrement" line is similar, but there are 2 cases. If a[n] is > more than m, we must decrement it. The cost here consists of making > everything up to n-1 non-decreasing and no more than m, i.e. C(n-1,m). > Plus we have the cost of chopping a[n] down to m, which is a[n]-m. > > In the other case, a[n] is m or less. So there's no need to > decrement, but we must get the elements a[1..n-1] to be no more than > a[n]. Again by recursive assumption this cost is C(n-1,a[n]). > > Here is an example. Suppose we have a = [5, 1, 1, 1, 3, 1]. The > least cost here is obtained by decrementing the 5 to 1 (cost 4) and > deleting the final 1 (cost 1) for a total cost of 5. > > So let's try the algorithm. (You must view this with a fixed font.) > > Table of C(n, m) values: > m = 1 3 5 > n = 1 : 4 2 0 > n = 2 : 4 3* 1* > n = 3 : 4 4 2* > n = 4 : 4 4 3* > n = 5 : 6m 4 4 > n = 6 : 6 5* 5* > > Here * means C resulted from decrementing and "m" means that a > decrement was based on the value of m rather than a[n]. > > We take the answer from C(6,5) = 5. > > Implementing this is a little tricky because m values are drawn from > V. You could use a hash table for the m-axis. But it's more > efficient to store V in an array and convert all the values of m in > the DP into indices of V. Because all the indices lie in [ 1 .. | > V| ], we can use simple arrays rather than hash tables to represent > the rows of the table C. > > We only need 2 rows at a time, so O(|V|) storage does the job. > > For C, we also need to convert all the indices to origin 0. > > So here's the final O(n^2) code. I think this is a correct > implementation. If anyone has an example that breaks it, I'd like to > see. > > #include <stdio.h> > > #define NMAX 10000 > > int cost(int *a, int N) > { > int i, j, max, Nv; > int V[NMAX], A[NMAX], B[NMAX]; > int *Cm = A, *Cn = B; // (n-1)'th and n'th rows of C > > // Compute set V with no duplicates. > // Remember where max element is. > Nv = max = 0; > for (i = 0; i < N; i++) { > for (j = 0; j < Nv; j++) > if (a[i] == V[j]) > break; > if (j == Nv) { > V[Nv++] = a[i]; > if (V[j] > V[max]) > max = j; > } > a[i] = j; // Convert a to indices. > } > // Fill in first row of C. > for (i = 0; i < Nv; i++) > Cm[i] = (V[a[0]] >= V[i]) ? V[a[0]] - V[i] : 0; > > // Fill in the rest of the rows of C. > for (i = 1; i < N; i++) { > for (j = 0; j < Nv; j++) { > int del = Cm[j] + V[a[i]]; > int dec = (V[a[i]] <= V[j]) ? Cm[a[i]] : Cm[j] + V[a[i]] - V[j]; > Cn[j] = (del < dec) ? del : dec; > } > // Swap row buffers so current becomes previous. > int *tmp = Cn; Cn = Cm; Cm = tmp; > } > return Cm[max]; > > } > > int main(void) > { > static int a[] = { 5, 1, 1, 1, 3, 1 }; > printf("Min cost = %d\n", cost(a, sizeof a / sizeof a[0])); > return 0; > > } > > On Aug 30, 9:19 pm, vikash jain <[email protected]> wrote: > > > > > @gene ..if u just give an example here....that will make things more > > clear...
-- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
