Massive Algorithms: Given an array A of positive i

Given an array A of positive i | CareerCup
Given an array A of positive integers. Convert it to a sorted array with minimum cost. The only valid operation are:
1) Decrement with cost = 1
2) Delete an element completely from the array with cost = value of element
https://github.com/xiaoningning/algorithm/blob/master/PuzzleCoding/src/MinCostSortedArray.java
* 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).
* 
* 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
* )
* 
* 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.
* 
* 
* Now the solution becomes easy to understand: it is a DP in two dimensions.
* If we sort the elements of the distinct elements of the original sequence d into a sorted array s,
* the length of d becomes the first dimension of the DP; the length of s becomes the second dimension.
* 
* We declare dp[d.Length,s.Length]. The value of dp[i,j] is the cost of solving subproblem d[0 to i]
* while keeping the last element of the solution under s[j].
* Note: this cost includes the cost of eliminating d[i] if it is less than s[j].
* 
* The first row dp[0,j] is computed as the cost of trimming d[0] to s[j],
* or zero if d[0] < s[j]. The value of dp[i,j] next row is calculated
* as the minimum of dp[i-1, 0 to j] + trim,
* where trim is the cost of trimming d[i] to s[j],
* or d[i] if it needs to be eliminated because s[j] is bigger than d[i].
*/
public static void main(String[] args) {
int[] a1 = new int[]{4, 3, 5, 6};
int[] a2 = new int[]{10, 3, 11, 12};
int[] a3 = new int[]{1, 10, 2, 11, 12};
int[] a4 = new int[]{5, 1, 1, 1, 3, 1};

minCostNonDecreasingArray(a1);
minCostNonDecreasingArray(a2);
minCostNonDecreasingArray(a3);
minCostNonDecreasingArray(a4);

}

public static void minCostNonDecreasingArray(int[] a) {

System.out.println(Arrays.toString(a));
if (a.length <= 1) {
System.out.println("min cost: " + 0);
return;
}

int[] sorted = a.clone();
Arrays.sort(sorted);

int[][] cost = new int[a.length][sorted.length];

int[] index = new int[a.length];
for (int i = 0; i < a.length; i++) {
for (int k = 0; k < sorted.length; k++) {
if (sorted[k] == a[i])
index[i] = k;
}
}

for (int j = 0; j < sorted.length; j++) {
cost[0][j] = (sorted[j] < a[0]) ? (a[0] - sorted[j]) : 0; // to a[0]
}

for (int i = 1; i < a.length; i++) {
for (int j = 0; j < sorted.length; j++) {

int del_cost = cost[i - 1][j] + a[i];
int decr_cost = (a[i] > sorted[j]) ? (cost[i - 1][j] + (a[i] - sorted[j])) : cost[i - 1][index[i]];

cost[i][j] = Math.min(del_cost, decr_cost);

}

}

int min = Integer.MAX_VALUE;
for (int j = 0; j < cost[0].length; j++) {
min = Math.min(min, cost[a.length - 1][j]);
}
// System.out.println(Arrays.deepToString(cost));
System.out.println("min cost: " + min);
}
http://stackoverflow.com/questions/8928061/convert-array-to-a-sorted-one-using-only-two-operations

You can solve this problem using a dynamic programming approach. The key observation is that it never makes sense to decrement a number to a value not found in the original array. (Informal proof: suppose that you decremented a number O1 to a value X that is not in the original sequence in order to avoid removing a number O2 > X from the result sequence. Then you can decrement O1 to O2 instead, and reduce the cost by O2-X).

Now the solution becomes easy to understand: it is a DP in two dimensions. If we sort the elements of the distinct elements of the original sequence d into a sorted array s, the length of dbecomes the first dimension of the DP; the length of s becomes the second dimension.

We declare dp[d.Length,s.Length]. The value of dp[i,j] is the cost of solving subproblem d[0 to i] while keeping the last element of the solution under s[j]. Note: this cost includes the cost of eliminating d[i] if it is less than s[j].

The first row dp[0,j] is computed as the cost of trimming d[0] to s[j], or zero if d[0] < s[j]. The value of dp[i,j] next row is calculated as the minimum of dp[i-1, 0 to j] + trim, where trim is the cost of trimming d[i] to s[j], or d[i] if it needs to be eliminated because s[j] is bigger than d[i].

The answer is calculated as the minimum of the last row dp[d.Length-1, 0 to s.Length].

Here is an implementation in C#:

static int Cost(int[] d) {
    var s = d.Distinct().OrderBy(v => v).ToArray();
    var dp = new int[d.Length,s.Length];
    for (var j = 0 ; j != s.Length ; j++) {
        dp[0, j] = Math.Max(d[0] - s[j], 0);
    }
    for (var i = 1; i != d.Length; i++) {
        for (var j = 0 ; j != s.Length ; j++) {
            dp[i, j] = int.MaxValue;
            var trim = d[i] - s[j];
            if (trim < 0) {
                trim = d[i];
            }
            dp[i, j] = int.MaxValue;
            for (var k = j ; k >= 0 ; k--) {
                dp[i, j] = Math.Min(dp[i, j], dp[i - 1, k] + trim);
            }
        }
    }
    var best = int.MaxValue;
    for (var j = 0 ; j != s.Length ; j++) {
        best = Math.Min(best, dp[d.Length - 1, j]);
    }
    return best;
}

This direct implementation has space complexity of O(N^2). You can reduce it to O(N) by observing that only two last rows are used at the same time.

Read full article from Given an array A of positive i | CareerCup

Given an array A of positive i | CareerCup

Labels

Popular Posts