im sry the L should look like this:
10 9 8 5 3 2 1 7 17 16 8 18 17 9 19 18 10 20 19 11 21 20 19 16 14 13 12 12 22 21 20 17 15 14 13 13 23 22 21 18 16 15 14 I missed a row in the last mail. On Thu, Jul 22, 2010 at 10:03 AM, topojoy biswas <topojoy.bis...@gmail.com>wrote: > consider these arrays: > > 10 9 8 5 3 2 1 > > and > > 13 12 11 10 9 8 7 > > > form a grid like this: > > 10 9 8 5 3 2 1 > 7 17 16 15 12 10 9 8 > 8 18 17 16 13 11 10 9 > 9 19 18 17 14 12 12 10 > 10 20 19 18 15 13 12 11 > 11 21 20 19 16 14 13 12 > 12 22 21 20 17 15 14 13 > 13 23 22 21 18 16 15 14 > > basically have an array descending and have one array ascending. > > If you add them in a grid, check that for any sum, all sums to its right > are less than it( in the same row), al sums above it( in the same column) > are less than it, all sums below it( in the same row) are greater than it. > > 10 9 8 5 3 2 1 > 7 17 16 15 *12 10 9 8* > 8 18 17 16 *13 11 10 9* > 9 19 18 17 *14 12 12 10* > 10 20 19 18 *15 13 12 11* > 11 *21 20 19* 16 14 13 12 > 12 *22 21 20* 17 15 14 13 > 13 *23 22 21* 18 16 15 14 > > So all sums which form the first quadrant origining at 19 are less than 19. > > And the 3rd quadrant formed by origining 19 including 19 are strickedly > grater than or equal to 19. > > This means in the added array will look like this: > __________________________________________________________ > |________________|___________________|______________________| > <-------x----------><------m---------------><-----------------y---------> > > x = no of elements in the underlined first quadrant > y= no of elements in the 3rd quadrant excluding 19. > m= the number of elements in the 2nd and the 4th quadrant including 19. > > So 19 would lie some whr in the 2n slot of this divided aray picture. > > So if we make x big enough so that m+y is small enough=O(n), we will reduce > our load. > > so choose x=(n-2)(n-3) which means something like this: > <------(n-2)-------> > 10 9 8 5 3 2 1 > 7 17 16 15 12 10 9 8 --------------- > 8 18 17 16 13 11 10 9 > 9 19 18 17 14 12 12 10 (n-3) > 10 20 19 18 15 13 12 11 ----------------- > 11 21 20 19 16 14 13 12 > 12 22 21 20 17 15 14 13 > 13 23 22 21 18 16 15 14 > > Then we will be left with an array of size m+y=5n-6 which is >n for all n > >2 like this: > > 10 9 8 5 3 2 1 > 7 17 16 > 8 18 17 > 9 19 18 > 10 20 19 > 11 21 20 > 12 22 21 20 17 15 14 13 > 13 23 22 21 18 16 15 14 > > Till this point it takes constant time. > > Now the first column of the "L" formed is sorted. So is the 2nd column. > > So is the horizonal part of L which is comprized of two sorted arays > (20-13) and (21-14). > > All of the elements add to 5n-6. We can merge sort them in O(n) time. Take > the biggest n elements. > > > > > > On Mon, Jul 19, 2010 at 12:18 PM, ankur aggarwal <ankur.mast....@gmail.com > > wrote: > >> >> >> this ques was asked by google.. i* could find any gud soln than order n*n >>> >>> >>> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Topo. > > There are days when solitude is a heady wine that intoxicates you with > freedom, others when it is a bitter tonic, and still others when it is a > poison that makes you beat your head against the wall. ~Colette > -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.