@divya You're rite. Post a solution if you have one. -- Regards, Vignesh
On 2 May 2010 13:14, divya jain <[email protected]> wrote: > @Mohit > > according to ur algo if a[1], b[0] has sum greater than a[0],b[1] > then i is incremented i is now 2 so for next iteration u ll compare a[2] > b[0] and a[1] b1]. but what about a[0] b[1] this pair s lost forever. think > for ths case also. > > > On 2 May 2010 11:22, mohit ranjan <[email protected]> wrote: > >> @Algoose Chase >> >> point taken >> Thanks >> >> >> Mohit Ranjan >> Samsung India Software Operations. >> >> >> On Sat, May 1, 2010 at 8:43 PM, Algoose Chase <[email protected]>wrote: >> >>> @mohit >>> >>> The idea of DP is fine. >>> When you find the Max i dont think you need to include A[i+1]+B[j+1] >>> because it can never be greater than both A[i+1]+B[j] and A[i]+B[j+1] since >>> both the lists are sorted in decreasing order. >>> >>> >>> On Fri, Apr 30, 2010 at 8:47 PM, mohit ranjan >>> <[email protected]>wrote: >>> >>>> oops >>>> >>>> Sorry didn't read properly >>>> last algo was for array sorted in ascending order >>>> >>>> for this case, just reverse the process >>>> >>>> >>>> A[n] and B[n] are two array >>>> >>>> loop=n, i=0, j=0; >>>> >>>> >>>> while(loop>0) // for n largest pairs >>>> { >>>> print A[i]+B[j]; // sum of first index from both array will >>>> be max >>>> >>>> foo = MAX ( A[i+1]+B[j], A[i+1]+B[j+1], A[i]+B[j+1] ) // using DP, >>>> moving forward >>>> >>>> if foo==A[i+1]+B[j]; i++ // only increment A >>>> if foo==A[i+1]+B[j+1]; i++; j++ // increment both A and B >>>> if foo==A[i]+B[j+1]; j++ // increment only B >>>> >>>> } >>>> >>>> >>>> >>>> Mohit Ranjan >>>> Samsung India Software Operations. >>>> >>>> >>>> On Fri, Apr 30, 2010 at 8:40 PM, mohit ranjan >>>> <[email protected]>wrote: >>>> >>>>> Hi Divya, >>>>> >>>>> >>>>> A[n] and B[n] are two array >>>>> >>>>> loop=n, i=n-1, j=n-1; >>>>> >>>>> while(loop>0) // for n largest pairs >>>>> { >>>>> print A[i]+B[j]; // sum of last index from both array will >>>>> be max >>>>> >>>>> foo = MAX ( A[i-1]+B[j], A[i-1]+B[j-1], A[i]+B[j-1] ) // using DP >>>>> moving backward >>>>> >>>>> if foo=A[i-1]+B[j]; i-- // only reduce A >>>>> if foo=A[i-1]+B[j-1]; i--; j-- // reduce both A and B >>>>> if foo=A[i]+B[j-1]; j-- // reduce only B >>>>> } >>>>> >>>>> Time: O(n) >>>>> >>>>> >>>>> Mohit Ranjan >>>>> >>>>> >>>>> >>>>> On Fri, Apr 30, 2010 at 5:35 PM, divya <[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. >>>>>> >>>>>> -- >>>>>> 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%[email protected]> >>>>>> . >>>>>> For more options, visit this group at >>>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>>> >>>>>> >>>>> >>>> -- >>>> 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%[email protected]> >>>> . >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> -- >>> 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%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> 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%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > 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%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- There are two kinds of people. Those who care for others and The others -- 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.
