Author |
Topic: stable merge the arrays (Read 3317 times) |
|
inexorable
Full Member
Posts: 211
|
 |
stable merge the arrays
« on: Jul 26th, 2010, 3:33pm » |
 Quote  Modify
|
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}
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: stable merge the arrays
« Reply #1 on: Jul 26th, 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: 250
|
|
Re: stable merge the arrays
« Reply #2 on: Jul 27th, 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: 7527
|
|
Re: stable merge the arrays
« Reply #3 on: Jul 27th, 2010, 9:10am » |
Quote Modify
|
on Jul 26th, 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) = (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.
|
| « Last Edit: Jul 27th, 2010, 9:20am by Grimbal » |
IP Logged |
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: stable merge the arrays
« Reply #4 on: Jul 27th, 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: 13730
|
|
Re: stable merge the arrays
« Reply #5 on: Jul 27th, 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 27th, 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][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++];
}
|
|
IP Logged |
|
|
|
newb
Newbie
Posts: 38
|
|
Re: stable merge the arrays
« Reply #7 on: Jul 30th, 2010, 1:52pm » |
Quote Modify
|
anyone,Please explain the DP solution to this problem.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print