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
<[email protected]>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 <[email protected]
> > 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> 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 [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.
