wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Largest values from cartesian product of arrays.
        
(Message started by: witee on Aug 8^th, 2010, 6:51am)

Title: Largest values from cartesian product of arrays.
Post by witee on Aug 8^th, 2010, 6:51am

Given two sorted positive integer arrays A(n) and B(n), we define a set S = {(a,b) | a http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif A and b http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif B}. Obviously there are n² 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.
T.C <=(nlogn)

//title changed --towr

Title: Re: Array
Post by towr on Aug 8^th, 2010, 8:13am

It might be nice if you tried to use somewhat more descriptive titles, we don't need a dozen threads called "array"; the whole point of having titles on a thread is so people can tell them apart and can at a glance get some idea of what they are about.
Also if you don't make up the problems yourself, you could try searching if they aren't already on the site... several times... using practically the same wording...

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1204984748
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1132204952