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[01] = 3 > (1,2) > sum[02] = 6 > (1,2,3) > sum[12] = 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[11] = 2 >> sum[2  2] = 3 >> sum[33] = 4 >> sum[44] = 5 >> sum[01] = 3 >> sum[02] = 6 >> sum[12] = 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 0S >>>> 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 i1 sum[0  i1] < candidate sum then we can say that >>>> i*(i1)/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 += 00+1; >>>> >>>> iteration 2 >>>> sum[01] = 3 < 7, count += 10+1 >>>> >>>> iteration 3 >>>> sum[02] = 6 < 7 count += 20+1; >>>> >>>> iteration 4 >>>> sum[0,3] = 10 > 7 so now increment g such that sum[g,i] < 7 >>>> so g = 3 count += 33+1; >>>> >>>> iteration 5 >>>> sum[3  4] = 9 > 7 >>>> new g = 4 count += 44+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 0S, 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 >>>>>> k1 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.
 [algogeeks] Re : Any hints[kth smallest contiguous sum] ? shady 2012/02/21
 Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ? sunny agrawal 2012/02/21
 Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ? shady 2012/02/21
 Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ? sunny agrawal 2012/02/21
 Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ? shady 2012/02/21
 Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ? atul anand 2012/02/21
 Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ? sunny agrawal 2012/02/21
 Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ? atul anand 2012/02/21
 Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ? sunny agrawal 2012/02/21 <=
 Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ? atul anand 2012/02/21
 Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ? sunny agrawal 2012/02/21
 Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ? atul anand 2012/02/22
 Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ? Arpit Sood 2012/02/21
 Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ? atul anand 2012/02/21
 Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ? shady 2012/02/21
 [algogeeks] Re: Re : Any hints[kth smallest contiguous sum] ? Don 2012/02/21