How are we making sure that top n-elements would lie in this 'L' shaped array?
Also, why don't we take an extreme case, such that the origin is bottom-left
element of the grid, then we have only 2n-1 elements to chose n biggest
elements
from.
So, can we prove that taking Ist quardrant as (n-2)x(n-3) would leave n-biggest
out? What is the criterion to chose the Ist quardrant?
manish...
________________________________
From: topojoy biswas <topojoy.bis...@gmail.com>
To: algogeeks@googlegroups.com
Sent: Thu, 22 July, 2010 10:10:58 AM
Subject: Re: [algogeeks] a google question
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.
>>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.
--
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.
