great solution :D thanks. On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal <sunny816.i...@gmail.com>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 <sinv...@gmail.com> 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 >> <sunny816.i...@gmail.com>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 <sinv...@gmail.com> 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 algogeeks@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. >>>> >>> >>> >>> >>> -- >>> 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 algogeeks@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 algogeeks@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. >> > > > > -- > 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 algogeeks@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 algogeeks@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.