CareerCup

Dynamic programming works, that is right.

Perhaps it is similar to Dr House's verbose solution, but the below is O(yx) (and not Omega(y^2x) which Dr House claims his solution is).

Sub problem:

Try to find the solution (Sol[i,j]) for A[1...i] and B[1...j] where 1 <= i <= x and 1 <= j <= y.

We get the recurrence relation:

Sol[i,j] = min {A[i]*B[j] + Sol[i-1, j-1], Sol[i, j-1]}

The first term corresponds to multiplying B[j] by A[j] and the second term corresponds to multiplying B[j] by 0.

Since the recurrence step is O(1), the complete algorithm is O(yx).

This is my solution. You can create a InsertZeros.java to take a look. It uses dynamic programming.

class Path {
	Integer value;
	String sequence;

	Path(Integer v, String s) {
		value = v;
		sequence = s;
	}
}

public class InsertZeros {
	public static void main(String args[]) {
		Integer[] a = { 1, -1 };
		Integer[] b = { 1, 2, 3, 4 };
		Path result = minimize(a, b, b.length - 1, b.length - a.length);
		System.out.println(result.sequence.substring(1));

	}

	public static Path minimize(Integer[] a, Integer[] b, Integer pos,
			Integer quota) {

		if (pos < 0) {
			return new Path(0, "");
		}

		if (quota > 0) {

			if (pos + 1 > quota) {

				Path opt1 = minimize(a, b, pos - 1, quota - 1);
				Path opt2 = minimize(a, b, pos - 1, quota);

				Integer opt1_value = opt1.value;
				Integer opt2_value = b[pos] * a[pos - quota] + opt2.value;

				String opt1_sequence = opt1.sequence + ",0";
				String opt2_sequence = opt2.sequence + "," + a[pos - quota];

				if (opt1_value < opt2_value) {
					return new Path(opt1_value, opt1_sequence);
				} else {
					return new Path(opt2_value, opt2_sequence);
				}
			} else {
				Path opt1 = minimize(a, b, pos - 1, quota - 1);
				Integer opt1_value = opt1.value;
				String opt1_sequence = opt1.sequence + ",0";
				return new Path(opt1_value, opt1_sequence);
			}

		} else {
			Path opt2 = minimize(a, b, pos - 1, quota);
			Integer opt2_value = b[pos] * a[pos - quota] + opt2.value;
			String opt2_sequence = opt2.sequence + "," + a[pos - quota];
			return new Path(opt2_value, opt2_sequence);

		}

	}
}

Nice problem.

Assume M = [m1, m2, m3, ....my ], and N = [n1, n2, n3, ....ny ], the product of the two vectors will be m1n1 + m2n2 + m3n3....my. ny

Here N is the vector B, of size y and is composed of constants (meaning that the vector is given to you). M, on the other hand, is supposed to be comprised of either elements from another vector A (of size x) and zeroes (totaling y-x). The other constraint is that the elements in A need to appear in the same order (read: insert zeroes in between the elements). Minimizing the product means minimizing the expression above (m1n1 + m2n2 + m3n3....my. ny). n1, n2, n3 ... are constants. You need to determine m1, m2....

Assume you are looking at the last element in this expression. We can either place the last element of A, or a 0, whichever minimizes the value of the expression.

Let F(i, j, k) be the value of the expression where i zeros are placed in j + 1 locations with kth element of the array A the next to be placed in the expression. We need to find F(y-x, y-1, x-1). The optimal substructure thus becomes:

F(i, j, k) = min { F(i-1, j-1, k), F(i, j-1, k-1) + A[k]*B[j] }

F(i-1, j-1, k) indicating that you placed a zero in the jth position and F(i, j-1, k-1) indicating that you placed the kth element of A in jth position and you still have i zeros to fill up.

The solution can be found by filling up this 3D matrix leading to a solution of time complexity O(y^2.x)

What are the base conditions of this recursion? I'll leave it to the astute reader.

my dp algorithm:

for (int i = 0; i <= y-x; i++)dp[0][i] = 0;
    for (int i=y-x+1; i <= y; i++)dp[0][i] = INF;
    for (int i = 1; i <= x; i++) {
        for (int j = 0; j <= y; j++) {
            if (j < i)dp[i][j] = INF;
            else {
                if (j - i > y -x )dp[i][j] = INF;
                else dp[i][j] = min(dp[i][j-1],dp[i-1][j-1] + a[i-1] * b[j-1]);
            }   
        }   
    }   
    return dp[x][y];

A rustic approach:

1. imagine x is the array with more elements and y with less elements [x > y]
so we have to add zeros to y.

Step 1: Add zeroes to y such that sizeof(x) = sizeof(y).
Step 2: sort x in ascending order, xlogx;
Step 3: sort y in descending order. xlogx (since at this point sizes of x,y will be the same).
step 4: go multiply everything and return the value. (x) complexity.

examples:

x=> 1,5,8,4,0,-1,9,2
y=> -2, -1, 5, -3,2.

after step2, y=>-2,-1,5,-3,2,0,0,0.

x sorted in ascending; -1,0,1,2,4, 5, 8 ,9
y sorted in descending: 5,2,0,0,0,-1,-2,-3

Product of them and find.
I agree this is very rustic than a good DP solution, but this has a complexity xlogx+x.
Comments are appreciated.
--
A mistake is a crash course in learning.
--

if x is O(n) then dp solution is O(n^2). I think we can do better in this case using O(n) space. Sort the array B and keep track of indices of of all the numbers(i.e. use an array of size y to keep track of indices). We can use a variation of quicksort to do this. Now for pick index of top (y-x) elements and insert 0 in corresponding positions in A.

what does the question mean "A*B is minimized" iam not clear with the question"

1. Add zeros to end of A
2. Sort A in descending order
3. Sort B in acending order

Sorry if this is a repeat of any answer, but I didn't feel like reading some of the long ones entirely.

So the gist is from this example:
B = (1,2, 3, 4) , A = (1, 0, 0, -1)

seems to be:
1. match the -ve elements of A against largest elements of B. Call # of -ve elements in A = g. i.e we need to find the largest g elements in A.
2. match the 0s against the largest of the remaining ones = y-x.

Why not just run selection to find the top elements ranked g+1 to g+y-x, then put the 0's in the same indices in A.
[I was trying to post a link but it isn't allowed you can search wikipedia for selection algorithm. Although I read it in the TH Corem, C Leiserson et al book]

does this make sense guys?

This is a typical sequence alignment problem with gap penalty = 0.

Optimal Structure

p(i, j) = min{A[i] * A[j] + p(i - 1, j - 1), 0 * A[j] + p(i, j - 1)}

Algorithm

t[i][j] store the minimum multiplication formed by a[i] and b[j]

ideone.com/squ8Qw

public int min(int[] a, int[] b) 
        {
                int m = a.length;
                int n = b.length;
                // the minimum multiplication formed by the subarrays a[i] and b[j]
                int[][] t = new int[m][n]; 
                for(int i = 0; i < m; i++) {
                        for(int j = i; j < i + (n - m) + 1; j++) {
                                if(j > 0) {
                                        if(i > 0) t[i][j] = Math.min(a[i] * b[j] + t[i - 1][j - 1], t[i][j - 1]);
                                        else t[i][j] = Math.min(a[i] * b[j], t[i][j - 1]);
                                } else {
                                        t[i][j] = a[i] * b[j];
                                }
                        }
                }
                // construct the array with zeros
                int[] c = new int[n];
                int i = m - 1; // the pointer of the array a
                int j = n - 1; // the pointer of the array b
                int k = n - 1; // the pointer of the array c
                for(; i >= 0 && j >= 0; j--) {
                        // set a[i] to c[k] 
                        if(j == 0 || t[i][j] < t[i][j - 1]) c[k--] = a[i--];
                        // set 0 to c[k]
                        else c[k--] = 0;
                }                               
                System.out.println(Arrays.toString(c));
                System.out.println(Arrays.toString(b));
                return t[m - 1][n - 1];
        }

Test Case

Onput

-2 1
2 5 3 1 6

-1
5 8 3

1 -1
1 2 3 4

Output

[0, -2, 0, 1, 0]
[2, 5, 3, 1, 6]
-9

[0, -1, 0]
[5, 8, 3]
-8

[1, 0, 0, -1]
[1, 2, 3, 4]
-3

1. Insert zeroes at A's end and sort it in increasing order.
2. Make a copy of B and sort the copy in descending order keeping a track of original positions at same time.
Ex: after steps 1 & 2
A = ( -1, 0, 0, 1)
B (original) = (3, 1, 2, 4)
B copy after sorting = ( (4,3), (3,0), (2, 2), (1,1))

now arrange A's elements in order provided by B's copy i.e. 0th value will go to 3rd pos, 1st -> 0th, 2nd -> 2nd, 3rd -> 1st
a = (0, 1, 0, -1)

int dp[n][m];

int solve(int i, int j)
{
         if (i < 0) return 0; 
         if (dp[i][j] != -1) return dp[i][j];
         dp[i][j] = a[i]*b[j] + solve(i-1, j-1);
         if (i <= j-1) 
            dp[i][j] = min(dp[i][j], solve(i, j-1));  
}

let dp[i][j] denote the answer if we consider first i elements of arr[] and first j elements of brr[].

if i == j then we have a single choice as we cannot put any 0. dp[i][j] = arr[i] * brr[j] + dp[i - 1][j - 1]

if j > i then it makes the condition invalid. Hence we simply put dp[i][j] = INT_MAX

for the general case, we put 0 or multiply we take min of both.

dp[i][j] = min(dp[i - 1][j - 1] + arr[i] * brr[i], dp[i - 1][j]);

former is the case wherein we choose to multiply, latter we choose to use 0.

dp[0][0] = 0;

    for(i = 1; i <= n; ++i) {
    	dp[i][0] = 0;
    }

    for(i = 1; i <= n; ++i) {
    	for(j = 1; j <= m; ++j) {
    		if(j > i) {
    			dp[i][j] = INT_MAX;
    		} else if(i == j) {
    			dp[i][j] = arr[i - 1] * brr[j - 1] + dp[i - 1][j - 1];
    		} else {
    			dp[i][j] = min(dp[i - 1][j], arr[i - 1] * brr[j - 1] + dp[i - 1][j - 1]);
    		}
    	}
    }

    return dp[n][m];