Yes. Exactly. DP will get it. On Aug 27, 11:34 pm, jagadish <jagadish1...@gmail.com> wrote: > Ya it fails.. Should it then be Dynamic Programming then?? > > On Aug 28, 8:32 am, jagadish <jagadish1...@gmail.com> wrote: > > > > > @Aravind: I think the solution given by Gene works!. > > The answer for 8 2 2 2 2 2.. is six.. > > > On Aug 28, 8:26 am, jagadish <jagadish1...@gmail.com> wrote: > > > > @Gene: Thanks alot! :-) your solution works like charm! > > > > On Aug 28, 7:09 am, Gene <gene.ress...@gmail.com> wrote: > > > > > This is a nice problem. It looks like a trivial matroid, so a greedy > > > > algorithm will work fine. The obvious greedy algorithm is to work > > > > left-to-right and incorporate elements into the sorted order one-by- > > > > one. In each case, you have 2 choices. The first is to decrement > > > > elements to the left by the amount needed to restore non-decreasing > > > > order. The second is to delete the new element. The cost of each is > > > > easy to calculate. Pick the choice with least cost and continue. > > > > This algorithm is O(n^2). There may be a faster way to do it, but I > > > > can't see one. > > > > > #include <stdio.h> > > > > > int make_nondecreasing(int *a, int n) > > > > { > > > > int i, j, dec, dec_cost, total_cost; > > > > > total_cost = 0; > > > > for (i = 0; i < n - 1; i++) { > > > > > // If we find a decrease... > > > > if (a[i] > a[i + 1]) { > > > > > // Find cost of decrementing all to the left. > > > > dec_cost = dec = a[i] - a[i + 1]; > > > > for (j = i - 1; j >= 0; j--) { > > > > > // Find decrement that would be needed. > > > > dec += a[j] - a[j + 1]; > > > > > // If no decement, we're done. > > > > if (dec <= 0) > > > > break; > > > > > // Count cost of decrement. > > > > dec_cost += dec; > > > > } > > > > > // Compare decrement cost with deletion cost. > > > > if (dec_cost < a[i + 1]) { > > > > > // Decrement is cheaper. Do it. > > > > for (j = i; j >= 0; j--) { > > > > if (a[j] > a[i + 1]) > > > > a[j] = a[i + 1]; > > > > } > > > > total_cost += dec_cost; > > > > } > > > > else { > > > > > // Deletion is cheaper. Do it. > > > > total_cost += a[i + 1]; > > > > for (j = i + 1; j < n - 1; j++) > > > > a[j] = a[j + 1]; > > > > --n; > > > > } > > > > } > > > > } > > > > return total_cost; > > > > > } > > > > > int main(void) > > > > { > > > > int a[] = { 14, 15, 16, 13, 11, 18 }; > > > > //int a[] = { 4, 3, 5, 6}; > > > > //int a[] = { 10, 3, 11, 12 }; > > > > int cost = make_nondecreasing(a, sizeof a / sizeof a[0]); > > > > printf("cost=%d\n", cost); > > > > return 0; > > > > > } > > > > > On Aug 27, 12:15 pm, jagadish <jagadish1...@gmail.com> wrote: > > > > > > You are given an array of positive integers. Convert it to a sorted > > > > > array with minimum cost. Only valid operation are > > > > > 1) Decrement -> cost = 1 > > > > > 2) Delete an element completely from the array -> cost = value of > > > > > element > > > > > > For example: > > > > > 4,3,5,6, -> cost 1 > > > > > 10,3,11,12 -> cost 3
-- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.