Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
@Sunny: A little doubt, how are you making sure that the candidate sum is actually a sum that can be formed by contiguous elements of the array? Can you please explain your algo for this array : 1 , 2 , 99 , 100 , we need the 3rd smallest sum. On Wed, Feb 22, 2012 at 3:11 PM, atul anand atul.87fri...@gmail.com wrote: ok got it ..thanks for resolving queries :) :) On Wed, Feb 22, 2012 at 11:10 AM, sunny agrawal sunny816.i...@gmail.comwrote: *NO, u r getting it wrong* *given a value x, we can find how many contiguous sums are lesser than x using the above mentioned algorithm in O(N)* *so we are searching a x in range 0-S such that, x has exactly k-1 sums lesser than x and x is kth* * * *Algorithm: * *for * On Wed, Feb 22, 2012 at 10:41 AM, atul anand atul.87fri...@gmail.comwrote: /* 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 */ do a binary search in range 0-S-- to search what?? acc to the complexity , O(N *log S) it seems that you are searching each element in given input array from range 0-S for given input = 1,2,3,4,5 S= 15 please clarify . sorry but i am not getting it ... On Wed, Feb 22, 2012 at 10:25 AM, sunny agrawal sunny816.i...@gmail.com wrote: Yes, read my first post On Wed, Feb 22, 2012 at 10:19 AM, atul anand atul.87fri...@gmail.comwrote: 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 sunny816.i...@gmail.com 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 atul.87fri...@gmail.comwrote: @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 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 = 3count += 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.comwrote: 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
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
ok got it ..thanks for resolving queries :) :) On Wed, Feb 22, 2012 at 11:10 AM, sunny agrawal sunny816.i...@gmail.comwrote: *NO, u r getting it wrong* *given a value x, we can find how many contiguous sums are lesser than x using the above mentioned algorithm in O(N)* *so we are searching a x in range 0-S such that, x has exactly k-1 sums lesser than x and x is kth* * * *Algorithm: * *for * On Wed, Feb 22, 2012 at 10:41 AM, atul anand atul.87fri...@gmail.comwrote: /* 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 */ do a binary search in range 0-S-- to search what?? acc to the complexity , O(N *log S) it seems that you are searching each element in given input array from range 0-S for given input = 1,2,3,4,5 S= 15 please clarify . sorry but i am not getting it ... On Wed, Feb 22, 2012 at 10:25 AM, sunny agrawal sunny816.i...@gmail.comwrote: Yes, read my first post On Wed, Feb 22, 2012 at 10:19 AM, atul anand atul.87fri...@gmail.comwrote: 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 sunny816.i...@gmail.com 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 atul.87fri...@gmail.comwrote: @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 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 = 3count += 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
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
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.
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
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.comwrote: 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.
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
if i am getting it right input has only positive number then if k = N (number of elements) , then it would similar to finding kth smallest element in the array. because we can consider each element in the input as a sub array. now if k N , then we need to find (k-N)th smallest element which should be sum two or more elements. On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal sunny816.i...@gmail.comwrote: 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.
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
can you do it for some example where k N... i am confused On Wed, Feb 22, 2012 at 12:22 AM, atul anand atul.87fri...@gmail.comwrote: if i am getting it right input has only positive number then if k = N (number of elements) , then it would similar to finding kth smallest element in the array. because we can consider each element in the input as a sub array. now if k N , then we need to find (k-N)th smallest element which should be sum two or more elements. On Tue, Feb 21, 2012 at 11:15 PM, sunny agrawal sunny816.i...@gmail.comwrote: 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. -- 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.
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
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 = 3count += 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.comwrote: 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.
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
great solution :D thanks. On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal sunny816.i...@gmail.comwrote: 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 = 3count += 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.comwrote: 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.
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
@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 contiguous sum (1,2) , (2,3) -- these contiguous sum has already been counted so output is 4. correct me if i am wrong... On Wed, Feb 22, 2012 at 12:41 AM, sunny agrawal sunny816.i...@gmail.comwrote: 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 = 3count += 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.comwrote: 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.
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
@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 atul.87fri...@gmail.com 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 sunny816.i...@gmail.comwrote: 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 = 3count += 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. -- 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
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
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 sunny816.i...@gmail.comwrote: @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 atul.87fri...@gmail.comwrote: @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 sunny816.i...@gmail.comwrote: 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 = 3count += 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
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
Yes, read my first post On Wed, Feb 22, 2012 at 10:19 AM, atul anand atul.87fri...@gmail.comwrote: 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 sunny816.i...@gmail.comwrote: @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 atul.87fri...@gmail.comwrote: @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 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 = 3count += 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
Re: [algogeeks] Re : Any hints[kth smallest contiguous sum] ?
*NO, u r getting it wrong* *given a value x, we can find how many contiguous sums are lesser than x using the above mentioned algorithm in O(N)* *so we are searching a x in range 0-S such that, x has exactly k-1 sums lesser than x and x is kth* * * *Algorithm: * *for * On Wed, Feb 22, 2012 at 10:41 AM, atul anand atul.87fri...@gmail.comwrote: /* 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 */ do a binary search in range 0-S-- to search what?? acc to the complexity , O(N *log S) it seems that you are searching each element in given input array from range 0-S for given input = 1,2,3,4,5 S= 15 please clarify . sorry but i am not getting it ... On Wed, Feb 22, 2012 at 10:25 AM, sunny agrawal sunny816.i...@gmail.comwrote: Yes, read my first post On Wed, Feb 22, 2012 at 10:19 AM, atul anand atul.87fri...@gmail.comwrote: 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 sunny816.i...@gmail.comwrote: @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 atul.87fri...@gmail.comwrote: @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 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 = 3count += 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