@Dave yes im also trying to say the same point as Gene these problem is similar to "*Least fare for a return trip Algorithm*" where u have suggest the exactly same algorithm.. @Gene do see these similar problem "[algogeeks] Least fare for a return trip Algorithm" here we have to find minimum n pairs sum instead of maximum.
On Mon, Oct 18, 2010 at 6:01 AM, Gene <gene.ress...@gmail.com> wrote: > Hmm... > > First, drawing the table is O(n^2). So we have to assume you never > really draw the table. > > Second, your description is too imprecise to say if it will work in > general. Give a pseudocode, please. I don't believe that any > algorithm based on local inspection of this table will work. In > general you'll be hopping around the table in a wild order. > > Third, I'm not sure why you'd pick an example where a and b are the > same array. All the interesting cases are when they're different. > > On Oct 16, 6:35 pm, ligerdave <david.c...@gmail.com> wrote: > > 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 <gene.ress...@gmail.com> 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 <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> > <algogeeks%2bunsubscr...@googlegroups .com> > > > > > . > > > > > For more options, visit this group at > > > > >http://groups.google.com/group/algogeeks?hl=en.-Hidequoted 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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile" -- 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.