like i said before, draw a table w/ x=a and y=b
come out w/ the matrix and you would see a patten
30 29 4 3 2 1
30 60 59 34 33 32 31
29 59 58 33 32 31 30
4 34 33 8 7 6 5
3 33 32 7 6 5 4
2 32 31 6 5 4 3
1 31 30 5 4 3 2
you start from a[0] and b[0], compare them, take the bigger one, set
the smaller one(for next iteration) and set a limit.
for instance, in this case, either one works. let's say a[0] is
bigger, the limit will be a[1]+b[0]. limit is always the element next
to the bigger one in array, plus the biggest in another array.
you loop through a[0]+b[i] where i=0 to length of b. stop when the
outcome is less than limit.
now you take what is stored(the smaller one) to start the next
iteration(steps above)
On Oct 15, 7:56 pm, Gene <[email protected]> wrote:
> 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 <[email protected]> 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 <[email protected]> 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 [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected]<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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
