@Dave..:-O well catch...
On Sat, Sep 3, 2011 at 9:00 PM, Dave <[email protected]> wrote: > @Piyush: Try your code with > > n = 10 > a[10] = {11,22,33,44,55,66,77,88,99,110} > b[10] = {10,20,30,40,50,60,70,80,90,100} > > Your code gets > > (110, 100) = 210 > (110, 90) = 200 > (99, 100) = 199 > (110, 80) = 190 > (88, 100) = 188 > (110, 70) = 180 > (77, 100) = 177 > (110, 60) = 170 > (66, 100) = 166 > (110, 50) = 160 > > but it should get > > (110, 100) = 210 > (110, 90) = 200 > (99, 100) = 199 > (110, 80) = 190 > (99, 90) = 189 > (88, 100) = 188 > (110, 70) = 180 > (99, 80) = 179 > (88, 90) = 178 > (77, 100) = 177 > > It fails because, after choosing the first four pairs, it does not > consider all three candidates, (110, 70) = 180, (99, 90) = 189, and > (88, 100) = 188. It only looks at the first and last of these. Later > on, it fails to consider (99, 80) = 179 and (88, 90) = 178. > > After you have chosen the maximum pair, every unused pair that is the > last unused pair in both its row and column of the (implicit) n by n > matrix of pairwise sums is a candidate. When you have chosen n-1 > pairs, there can be O(sqrt(n)) candidates for the last choice. You are > considering only two of them. > > Dave > > On Sep 2, 3:09 pm, Piyush Grover <[email protected]> wrote: > > if I have understood the question correctly then: > > > > a[n-1] + b[i] > a[j] + b[i] for all 0 <= j < n-1 > > and a[j] + b[n-1] > a[j] + b[i] for all 0 <= i < n-1 > > therefore, > > > > i = j =n-1; > > count = 1; > > S[0] <-- (a[n-1], b[n-1]) > > p = a[n-1] + b[n-2]; > > q = a[n-2] + b[n-1] > > > > while(count < n){ > > > > if(p > q){ > > j--; > > S[count++] <-- (a[n-1], b[j]); > > }else{ > > i--; > > S[count++] <-- (a[i], b[n-1]); > > } > > > > p = a[n-1] + b[j-1]; > > q = a[i-1] + b[n-1]; > > > > } > > > > Time complexity: O(n) : http://ideone.com/FXfVj > > > > On Fri, Sep 2, 2011 at 10:05 PM, WgpShashank <[email protected] > >wrote: > > > > > > > > > @Dave Correct , Missed to Provide the Correct Time Complexity in Worst > Case > > > it Will be O(N^2) , as we need to find out n such maximum pair , will > think > > > about O(N0) Algo, if able to do it, will post the Algo here > > > > > Thanks > > > Shashank Mani > > > Computer Science > > > Birla Institute of Technology,Mesra > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To view this discussion on the web visit > > >https://groups.google.com/d/msg/algogeeks/-/a14Pj22tbJgJ. > > > > > 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.- Hide quoted text - > > > > - Show quoted text - > > -- > 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. > > -- 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.
