I just ran the code with your example and it produced 22.
Here is the C table:
m = 11 13 20 22
n = 1 : 9 7 0 0
n = 2 : 20 16 2 0
n = 3 : 22 16 15 13
n = 4 : 22 22 22 22
On Sep 3, 2:18 pm, Discover <[email protected]> wrote:
> @gene: nice solution..
>
> but it's not working for a[]={20,22,13,11};
>
> ur code will give soln : 24
> but ans should be: 22 {11,11,11,11}
>
> pls correct me if i m wrong
>
> On Aug 28, 8:26 am, jagadish <[email protected]> wrote:
>
>
>
> > @Gene: Thanks alot! :-) your solution works like charm!
>
> > On Aug 28, 7:09 am, Gene <[email protected]> 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 <[email protected]> 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 [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.
