wu :: forums
« wu :: forums - stable merge the arrays »

Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 2:45am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Eigenray, Grimbal, william wu, towr, ThudnBlunder, Icarus, SMQ)
   stable merge the arrays
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: stable merge the arrays  (Read 3306 times)
inexorable
Full Member
***





   


Posts: 211
stable merge the arrays  
« on: Jul 26th, 2010, 3:33pm »
Quote Quote Modify 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: male
Posts: 13730
Re: stable merge the arrays  
« Reply #1 on: Jul 26th, 2010, 11:41pm »
Quote Quote Modify 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: male
Posts: 250
Re: stable merge the arrays  
« Reply #2 on: Jul 27th, 2010, 3:10am »
Quote Quote Modify 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 Tongue
IP Logged

The only thing we have to fear is fear itself!
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7526
Re: stable merge the arrays  
« Reply #3 on: Jul 27th, 2010, 9:10am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 13730
Re: stable merge the arrays  
« Reply #5 on: Jul 27th, 2010, 10:49am »
Quote Quote Modify 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 Quote Modify 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 Quote Modify Modify

anyone,Please  explain the DP solution to this problem.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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