wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> stable merge the arrays
        
(Message started by: inexorable on Jul 26^th, 2010, 3:33pm)

Title: stable merge the arrays
Post by inexorable on Jul 26^th, 2010, 3:33pm

You are given 2 sorted arrays of size ‘n’ each. You need to stable-merge these arrays such that in the new array sum of product of consecutive elements is maximized.
eg
A= { 1, 2, 3}
B= { 3, 7, 9}
Stable merging A and B will give an array C with ’2n’ elements say C={c1, c2, c3, c4, c5, c6}
You need to find a new array C by merging (stable) A and B such that sum= c1*c2 + c3*c4 + c5* c6….. n terms is maximum.
For the above C={3,7,1,9,2,3}

Title: Re: stable merge the arrays
Post by towr on Jul 26^th, 2010, 11:41pm

C={1,2,3,3,7,9} has a greater sum, namely 74 instead of 36
In fact, I don't think the criterion of getting the greatest sum c1*c2 + c3*c4 + ... is different from simply sorting on order.

Title: Re: stable merge the arrays
Post by birbal on Jul 27^th, 2010, 3:10am

We can try dynamically merging these arrays and maximizing the sum.
Something like this :
A = { 1 ..... n }
B = { 1 .....m }
Sum( A(i,n) , B(j,m) ) = maximum sum that can be obtained by merging i to n elements of A and j to m elements of B. Base case would be
Sum ( A(n,n) , B(m,m) ) = A[n]*B[m] ;

But i don't think after doing this, we will get output as different from a sorted array :P

Title: Re: stable merge the arrays
Post by Grimbal on Jul 27^th, 2010, 9:10am

on 07/26/10 at 23:41:40, towr wrote:

In fact, I don't think the criterion of getting the greatest sum c1*c2 + c3*c4 + ... is different from simply sorting on order.

And dare to say I think it is the same.
If you relax the rules so that you can order freely the elements of A and B into C, the solution to order the ci is optimal.

If the sum contains 2 products a*b and c*d where a,b,c,d are not ordered, you can rearrange them to have a<=b, c<=d and a<=c without changing the sum. If after that you have b>c you can switch b and c, the sum will not decrease.
If b>c,
(ac+bd) - (ab+cd) = (d-a)(b-c).
(a-d) >=0, (b-c) <0, so the expression is <=0. That means (ac+bd) >= (ab+cd).
Using this, you can reorder all of C without ever reducing the sum of products.

Title: Re: stable merge the arrays
Post by inexorable on Jul 27^th, 2010, 9:59am

If the 2 arrays were not sorted, how to find C?

Title: Re: stable merge the arrays
Post by towr on Jul 27^th, 2010, 10:49am

I'd hazard to guess dynamic programming. At each step you take either an element from A or from B, so in a table that can either down or right. It might be complicated by having to take two steps at a time, but I don't think that should make a fundamental difference.

Title: Re: stable merge the arrays
Post by inexorable on Jul 27^th, 2010, 1:39pm

The following DP solution would take O(n^2) space and O(n^2) time. can we reduce space further?

int sum[100][100]={0};//assuming size of arrays is atmost 99//

void sum(int A[], int B[], int c[], int n)
{
sum[n][n-1]=B[n-1]
sum[n-1][n]=A[n-1];
sum[n-1][n-1]=A[n-1]*B[n-1];
for(int j=n-2;j>=0;j--)
{
sum[n][j]=sum[n][j+1]*B[j];
sum[j][n]=sum[j+1][n]*A[j];
}
int i=0,j=0,k;
for(i=n-2;i>=0;i--)
for(j=n-2;j>=0;j--)
{
ij=A[i]*B[j]+sum[i+1][j+1];
ijplus=B[j]*B[j+1]+sum[i][j+2];
iplusj=A[i]*A[j+1]+sum[i+2][j];
sum[i][j]=max(ij,ijplus,iplusj);

}

for(k=0,i=0,j=0;i<n && j<n;)
{
if(sum[i][j]==(A[i]*B[j]+sum[i+1][j+1]))
{

c[k++]=A[i++];
c[k++]=B[j++];
continue;
}

if(sum[i][j]==(B[j]*B[j+1]+sum[i][j+2]))
{
c[k++]=B[j++];
c[k++]=B[j++];
continue;
}
if(sum[i][j]==(A[i]*A[j+1]+sum[i+2][j]))
{

c[k++]=A[i++];
c[k++]=A[i++];
continue;
}
}
while(i<n)c[k++]=A[i++];
while(j<n)c[k++]=B[j++];
}

Title: Re: stable merge the arrays
Post by newb on Jul 30^th, 2010, 1:52pm

anyone,Please explain the DP solution to this problem.