wu :: forums « wu :: forums - stable merge the arrays » Welcome, Guest. Please Login or Register. Nov 25th, 2015, 10:51pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: Eigenray, william wu, Grimbal, SMQ, Icarus, towr, ThudnBlunder)    stable merge the arrays « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: stable merge the arrays  (Read 2437 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: 13276
 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: 7076
 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: 13276
 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board