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

Mon, 03 Apr 2006 01:54:43 -0700

Hi,
    It is very hard for me to get the basic flow of this algorithm. Can you explain the basic idea behind the algorithm.
 
regards
Arunachalam.

 
On 4/3/06, Mayur <[EMAIL PROTECTED]> wrote:
right... that's correct. Arunachalam's right...  Sorry... My second attempt at it...

One assumption, though - the output need not be sorted...

1: curMin <- min( a[0], b[0] ) - 1

2: i <- n, j<-n
3: cnt <- 0, whoSurged = NONE;
4: while ( cnt < n )
{
5:     output a[i] + b[j]
6:     cnt <- cnt + 1
7:     if a[i] + b[j]  < curMin
8:           then if whoSurged == A
9:                  then j <- j - 1
10:                       i = n
11:                else  i <- i - 1
12:                        j = n
12.5:              curMin = min(a[0], b[0]) - 1
13:                goto step 4
14:     if (a[i-1] + b[j]) < (a[i] + b[j-1])
15:     then  j <- j - 1
16:            if curMin == (min(a[0], b[0]) -1 )
17:                then whoSurged = B
18:                        curMin = a[i-1] + b[j+1]
19:     else  i <- i - 1
20:            if curMin == (min(a[0], b[0]) -1 )
21:                 then whoSurged = A
22:                         curMin = a[i+1] + b[j-1]
}



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