[algogeeks] Re: I guess, It is a tough one!!! Lets see who solves this

Mon, 03 Apr 2006 00:17:47 -0700

Hi,
     Can you give psedocode or demonstrate with an example.
 
Here goes my O(n log n) solution.
 
Observation 1.
         ax+by can appear in the solution only if ax+bj has appeared in the solution where j > y.
 
1. Form a max heap of n elements with ai+bn where  1 <= i <= n.
2. Extract max (assume max extracted has ai+bj as its b component)
3. Add the element ai+b(j-1) to the heap.
4. Do this n times .
 
Forming a heap is of order n.
Extract max is of order 1.
Insertion is of order log n
 
 
We are doing insertion n times hence O(n log n) + n.
 
regards
Arunachalam.


 
On 4/3/06, iwgmsft <[EMAIL PROTECTED]> wrote:

assume we have set {ai+bj}.. of size n^2

we can solve using MERGE-SORT i think.. to divide this problem into
subproblems will take O(2logn) i.e. O(log n)...
now at the time of merge it will take O(2n) i.e. O(n)... so this time
we can find n largest values(by merging values in decending order)..

correct me if i m wrong..



http"//ww.livejournal.com/users/arunachalam
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---

Reply via email to