Hi Arun. Last time we discussed this problem I came up with the same
idea. Unfortunately it doesn't work. The problem is that in order
for the "merge" to be correct, each pair of pointers must be
guarenteed to produce sums that are in non-increasing order. They
don't. For example, if you run your program with
int a[N] = { 1, 2, 3, 4,29,30};
int b[N] = { 1, 2, 3, 4,29,30};
It will produce
(30,30)=> 60 (30,29)=> 59 (29,30)=> 59 (30,4)=> 34 (4,30)=> 34
(30,3)=> 33
This is wrong because the 4th pair should be (29,29) => 58.
In fact, niether here nor in the previous discussion did we ever get a
correct solution.
If you figure it out, please post.
On Oct 14, 5:54 am, arun raghavendar <arun.s...@gmail.com> wrote:
> Start merging A and B from the tail end for N elements, just like the way
> you would do it for a merge sort but with a different constraint based on
> the sum a[i] and b[i]
>
> This should work for any value of N, I just hard-coded it for simplicity.
>
> #include<stdio.h>
> #define N 6
> struct OutputType {
> int a;
> int b;
> int value;
>
> };
>
> int main() {
> int a[N] = {1,8,13,24,25,30};
> int b[N] = {5,6,17,28,29,29};
> struct OutputType s[N];
> int i, a_candidate_1 = N-1, a_candidate_2=N-2, b_candidate_1=N-1,
> b_candidate_2=N-2;
> s[0].a = a[N-1];
> s[0].b = b[N-1];
> s[0].value = a[N-1] + b[N-1];
> for (i=1;i<N;i++) {
> if ((a[a_candidate_1]+b[b_candidate_2]) >=
> (a[a_candidate_2]+b[b_candidate_1])) {
> s[i].a = a[a_candidate_1];
> s[i].b = b[b_candidate_2];
> s[i].value = a[a_candidate_1]+b[b_candidate_2];
> b_candidate_2--;
> if (b_candidate_2 < 0) { a_candidate_1--; }
> } else {
> s[i].a = a[a_candidate_2];
> s[i].b = b[b_candidate_1];
> s[i].value = a[a_candidate_2]+b[b_candidate_1];
> a_candidate_2--;
> if (a_candidate_2 < 0) { b_candidate_1--; }
> }
> }
>
> for (i=0;i<N;i++) printf("(%d,%d)=>%3d ", s[i].a, s[i].b,
> s[i].value);
>
> return 0;
>
> }
>
> -Arun
>
>
>
> On Thu, Oct 14, 2010 at 1:25 PM, Harshal <hc4...@gmail.com> wrote:
>
> > Given two sorted postive integer arrays A[n] and B[n] (W.L.O.G, let's
>
> > say they are decreasingly sorted), we define a set S = {(a,b) | a \in A
> > and b \in B}. Obviously there are n^2 elements in S. The value of such
> > a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
>
> > from S with largest values. The tricky part is that we need an O(n)
> > algorithm.
>
> > --
> > Harshal Choudhary,
> > III Year B.Tech Undergraduate,
> > Computer Engineering Department,
> > National Institute of Technology Surathkal, Karnataka
> > India.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
