Author 
Topic: stable merge the arrays (Read 1938 times) 

inexorable
Full Member
Posts: 211


stable merge the arrays
« on: Jul 26^{th}, 2010, 3:33pm » 
Quote Modify

You are given 2 sorted arrays of size ‘n’ each. You need to stablemerge 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}


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13154


Re: stable merge the arrays
« Reply #1 on: Jul 26^{th}, 2010, 11:41pm » 
Quote Modify

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.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



birbal
Full Member
Gender:
Posts: 249


Re: stable merge the arrays
« Reply #2 on: Jul 27^{th}, 2010, 3:10am » 
Quote Modify

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


IP Logged 
The only thing we have to fear is fear itself!



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7036


Re: stable merge the arrays
« Reply #3 on: Jul 27^{th}, 2010, 9:10am » 
Quote Modify

on Jul 26^{th}, 2010, 11:41pm, 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) = (da)(bc). (ad) >=0, (bc) <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.

« Last Edit: Jul 27^{th}, 2010, 9:20am by Grimbal » 
IP Logged 



inexorable
Full Member
Posts: 211


Re: stable merge the arrays
« Reply #4 on: Jul 27^{th}, 2010, 9:59am » 
Quote Modify

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


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13154


Re: stable merge the arrays
« Reply #5 on: Jul 27^{th}, 2010, 10:49am » 
Quote Modify

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.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



inexorable
Full Member
Posts: 211


Re: stable merge the arrays
« Reply #6 on: Jul 27^{th}, 2010, 1:39pm » 
Quote Modify

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][n1]=B[n1] sum[n1][n]=A[n1]; sum[n1][n1]=A[n1]*B[n1]; for(int j=n2;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=n2;i>=0;i) for(j=n2;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++]; }


IP Logged 



newb
Newbie
Posts: 38


Re: stable merge the arrays
« Reply #7 on: Jul 30^{th}, 2010, 1:52pm » 
Quote Modify

anyone,Please explain the DP solution to this problem.


IP Logged 



