Loading...

algogeeks@googlegroups.com

[Prev] Thread [Next]  |  [Prev] Date [Next]

Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ? sunny agrawal Tue Feb 21 21:00:32 2012

Yes, read my first post


On Wed, Feb 22, 2012 at 10:19 AM, atul anand <[EMAIL PROTECTED]>wrote:

> sum[0-1] = 3 --> (1,2)
> sum[0-2] = 6 --> (1,2,3)
> sum[1-2] = 5 --> (2,3)
>
> ok...so we can consider 3 , (1,2) as different contiguous.
>
> how did you choose candidate sum for the given input  ?? will it not add
> to the complexity
>
>
> On Wed, Feb 22, 2012 at 9:59 AM, sunny agrawal <[EMAIL PROTECTED]>wrote:
>
>> @atul  there are 8 sums less than 7
>>
>> sum[0 - 0] = 1
>> sum[1-1] = 2
>> sum[2 - 2] = 3
>> sum[3-3] = 4
>> sum[4-4] = 5
>> sum[0-1] = 3
>> sum[0-2] = 6
>> sum[1-2] = 5
>>
>> contiguous sum (1,2) , (2,3) --> these contiguous sum has already been
>> counted ??? where ?
>> Read problem statement carefully !!
>>
>>
>> On Wed, Feb 22, 2012 at 9:39 AM, atul anand <[EMAIL PROTECTED]>wrote:
>>
>>> @sunny : before moving to your algorithm , i can see wrong output in
>>> your example:-
>>>
>>> in you example dere are 8 sums less than 7.
>>> but for given input contiguous sum less than 7 are
>>> 1,2,3,4,5 = 4
>>> so output is 4.
>>>
>>> correct me if i am wrong...
>>>
>>>
>>> On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal <[EMAIL PROTECTED]
>>> > wrote:
>>>
>>>> we need to find how many sums are less than candidate Sum chosen in one
>>>> iteration of binary search in range 0-S
>>>> To count this, for each i we try to find how many sums ending at i are
>>>> lesser than candidate sum !!
>>>>
>>>> lets say for some i-1 sum[0 - i-1] < candidate sum then we can say that
>>>> i*(i-1)/2 sums are less than candidate sum.
>>>> now lets say after adding a[i] again sum[0 - i] < candidateSum then u
>>>> can add (i+1) to previous count because all sums [0 - i], sum[1 - i],
>>>> ............. sum[i - i] will be lesser than candidate sum
>>>> or if adding a[i] causes sum[0 - i] > candidateSum then u have to find
>>>> a index g such that sum[g - i] < candidate sum, and increase the count by
>>>> ((i)-(g) +1).
>>>>
>>>> eg lets say your candidate sum is 7 (for the given example{1,2,3,4,5})
>>>> k = 3 n = 5
>>>> initially g = 0
>>>> sum = 0;
>>>> candidateSum = 7;
>>>> count = 0
>>>> iteration one:
>>>> sum[0 - 0] = 1 < 7  so count += 0-0+1;
>>>>
>>>> iteration 2
>>>> sum[0-1] = 3 < 7,  count += 1-0+1
>>>>
>>>> iteration 3
>>>> sum[0-2] = 6 < 7 count += 2-0+1;
>>>>
>>>> iteration 4
>>>> sum[0,3] = 10 > 7 so now increment g such that sum[g,i] < 7
>>>> so g = 3    count += 3-3+1;
>>>>
>>>> iteration 5
>>>> sum[3 - 4] = 9 > 7
>>>> new g = 4 count += 4-4+1
>>>>
>>>> final count = 8, so there are 8 sums less than 7
>>>>
>>>>
>>>>
>>>> On Wed, Feb 22, 2012 at 12:16 AM, shady <[EMAIL PROTECTED]> wrote:
>>>>
>>>>> didn't get you, how to check for subsequences which doesn't start from
>>>>> the beginning ? can you explain for that same example... should we check
>>>>> for all contiguous subsequences of some particular length?
>>>>>
>>>>>
>>>>> On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal <
>>>>> [EMAIL PROTECTED]> wrote:
>>>>>
>>>>>> i dont know if a better solution exists
>>>>>> but here is one with complexity O(N*logS)...
>>>>>> N = no of elements in array
>>>>>> S = max sum of a subarray that is sum of all the elements as all are
>>>>>> positive
>>>>>>
>>>>>> algo goes as follows
>>>>>> do a binary search in range 0-S, for each such candidate sum find how
>>>>>> many sums are smaller than candidate sum
>>>>>>
>>>>>> there is also need to take care of some cases when there are exactly
>>>>>> k-1 sums less than candidate sum, but there is no contigious where sum =
>>>>>> candidate sum.
>>>>>>
>>>>>>
>>>>>> On Tue, Feb 21, 2012 at 11:02 PM, shady <[EMAIL PROTECTED]> wrote:
>>>>>>
>>>>>>> Problem link <http://www.spoj.pl/ABACUS12/status/ABA12E/>
>>>>>>>
>>>>>>> --
>>>>>>> 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.
>>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> --
>>>>>> Sunny Aggrawal
>>>>>> B.Tech. V year,CSI
>>>>>> Indian Institute Of Technology,Roorkee
>>>>>>
>>>>>>  --
>>>>>> 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.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Sunny Aggrawal
>>>> B.Tech. V year,CSI
>>>> Indian Institute Of Technology,Roorkee
>>>>
>>>>  --
>>>> 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.
>>>
>>
>>
>>
>> --
>> Sunny Aggrawal
>> B.Tech. V year,CSI
>> Indian Institute Of Technology,Roorkee
>>
>>  --
>> 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.
>



-- 
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee

-- 
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.