Hi sunny.. i dont understand the second part that is
now do the following n times
extract a pair value (i,j)
and insert (i+1,j) and (i,j+1) in heap not inserted
why are u inserting (i+1,j) and (i,j+1)... can u explain it please....
On Sat, Jul 9, 2011 at 10:59 PM, sunny agrawal <sunny816.i...@gmail.com>wrote:
> i have an O(nlgn) solution in mind using O(n^2) memory
>
> All the values can be thought as the following matrix
> (a0+b0) (a0+b1) (a0+b2).................................(a0+bn-1)
> (a1+b0) (a1+b1) (a1+b2).................................(a1+bn-1)
> . .
> . .
> . .
> . .
> . .
> . .
> . .
> (an-1+b0) (an-1+b1) (an-1+b2)......................(an-1+bn-1)
>
> now as we can see all the rows and columns are sorted.....
> now i will refer (ai,bj) as (i,j)
> make a heap
> insert (0,0) in heap
>
> now do the following n times
> extract a pair value (i,j)
> and insert (i+1,j) and (i,j+1) in heap not inserted
>
> TC : O(nlgn)
> SC: O(n^2) to take care of already present elements in the heap
>
>
>
>
> On Sat, Jul 9, 2011 at 4:54 AM, Piyush Sinha <ecstasy.piy...@gmail.com>wrote:
>
>> Given two sorted positive integer arrays A(n) and B(n). 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.
>>
>>
>> --
>> *Piyush Sinha*
>> *IIIT, Allahabad*
>> *+91-8792136657*
>> *+91-7483122727*
>> *https://www.facebook.com/profile.php?id=100000655377926 *
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@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.
>>
>>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>
--
Warm Regards,
Sunny T
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
