@hemesh, amol = correct solutions ABCDEF another problem on SPOJ, incase people want to try.
On Sun, Jun 24, 2012 at 2:13 AM, Sourabh Singh <singhsourab...@gmail.com>wrote: > @ Amol Sharma > > thanx got it.. > > yup, overlooked those case's :-) my bad.. > > > On Sat, Jun 23, 2012 at 1:31 PM, Amol Sharma <amolsharm...@gmail.com>wrote: > >> @sourabh: >> for this particular question.. >> in your code replace >> >> if(binary_search(c,c+size,-b[i])) >> count++; >> >> by >> >> count+=upper_bound(c,c+size,-b[i])-lower_bound(c,c+size,-b[i]); >> >> you are actually missing some of the quadruples....as there can be more >> than one element with value -b[i] in the array c and you are actually >> ignoring them. >> -- >> >> >> Amol Sharma >> Final Year Student >> Computer Science and Engineering >> MNNIT Allahabad >> >> <http://gplus.to/amolsharma99> >> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/><http://facebook.com/amolsharma99> >> >> >> >> >> >> >> On Sun, Jun 24, 2012 at 1:22 AM, Sourabh Singh >> <singhsourab...@gmail.com>wrote: >> >>> @ALL >>> >>> O(n^2 lg(n^2)) >>> >>> http://www.spoj.pl/problems/SUMFOUR/ >>> >>> my code : >>> http://ideone.com/kAPNB >>> >>> plz. suggest some test case's : >>> >>> On Sat, Jun 23, 2012 at 6:59 AM, Amol Sharma <amolsharm...@gmail.com>wrote: >>> >>>> @bhaskar,rammar: >>>> >>>> I don't think your algo willn not work for the following test case -- >>>> >>>> >>>> test case : >>>> arr : 2 4 6 8 >>>> arr^2 : 6 8 10 10 12 14 (sum of each unique pair in >>>> arr[i]) >>>> >>>> let's say target sum is 26 >>>> >>>> your solution will return true as they 12+14=26 but in 12 and 14, 8 is >>>> common, infact 26 is not possible in the given array >>>> >>>> -- >>>> >>>> >>>> Amol Sharma >>>> Final Year Student >>>> Computer Science and Engineering >>>> MNNIT Allahabad >>>> >>>> <http://gplus.to/amolsharma99> >>>> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/><http://facebook.com/amolsharma99> >>>> >>>> >>>> >>>> >>>> >>>> >>>> On Fri, Jun 22, 2012 at 11:45 PM, Bhaskar Kushwaha < >>>> bhaskar.kushwaha2...@gmail.com> wrote: >>>> >>>>> We first compute the N^2 two sums, and sort the two sums. The for each >>>>> TwoSum t, we check whether there is another two sum t' such that t.value + >>>>> t'.value = target. The time complexity of this approach is O(N^2 logN) >>>>> >>>>> >>>>> On Wed, Jun 20, 2012 at 1:36 AM, rammar <getam...@gmail.com> wrote: >>>>> >>>>>> Lets see ur example... We can have two other arrays corresponding to >>>>>> our n^2 array. >>>>>> For every (target-arr[i]) which we search in our look up array, we >>>>>> can also search the components which were used to get that sum. This can >>>>>> be >>>>>> done in addition constant amount search. >>>>>> I hope we can still go with Hemesh's algo. Please let me know if it >>>>>> breaks somewhere... >>>>>> >>>>>> let's take a test case : >>>>>> arr : 2 4 6 8 >>>>>> arr[0] : 6 8 10 10 12 14 >>>>>> arr[1] : 2 2 2 4 4 6 >>>>>> arr[2] : 4 6 8 6 8 8 >>>>>> >>>>>> >>>>>> P.S. Can we do better? >>>>>> >>>>>> On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote: >>>>>>> >>>>>>> @rammar: >>>>>>> can you please explain the case...which i took in the earlier >>>>>>> post..with this method. >>>>>>> >>>>>>> -- >>>>>>> >>>>>>> >>>>>>> Amol Sharma >>>>>>> Final Year Student >>>>>>> Computer Science and Engineering >>>>>>> MNNIT Allahabad >>>>>>> >>>>>>> <http://gplus.to/amolsharma99> >>>>>>> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/><http://facebook.com/amolsharma99> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> On Tue, Jun 19, 2012 at 11:27 PM, rammar <getam...@gmail.com> wrote: >>>>>>> >>>>>>>> @Hemesh +1 >>>>>>>> >>>>>>>> Please correct me if i am wrong. >>>>>>>> Creation of our look up array a[n*n] -> sum of all the pairs will >>>>>>>> take O(n^2). >>>>>>>> Search using binary sort or quick sort in O(n^2 log (n^2) ) == >>>>>>>> O(n^2 log n) >>>>>>>> We will traverse this array, and for every element we will find >>>>>>>> (target - a[i]) -> This traversal will again take O(n^2). >>>>>>>> For every (target -a[i]) we will search it in our >>>>>>>> lookup array using binary search -> This will take O(log n^2) = O(2log >>>>>>>> n) = >>>>>>>> O(log n) >>>>>>>> We will store all the matched for the target. >>>>>>>> >>>>>>>> Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O >>>>>>>> (n^2 log n) >>>>>>>> If the values of max of a[n] is not very high, we can go with a >>>>>>>> hash map. This will result in a quick look up. And we can get the >>>>>>>> answer in >>>>>>>> O(n^2). >>>>>>>> >>>>>>>> >>>>>>>> P.S. Can we do better? >>>>>>>> >>>>>>>> >>>>>>>> On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: >>>>>>>>> >>>>>>>>> @KK and hemesh >>>>>>>>> target is not a constant value , it can be any element in array , >>>>>>>>> so you need to do binary search for all (array[i] - (a+b)) to find >>>>>>>>> which >>>>>>>>> increases the complexity to n^3logn. >>>>>>>>> So, i think the n^3 approach which i gave before do it ?? >>>>>>>>> >>>>>>>>> ------ Correct me if m wrong >>>>>>>>> >>>>>>>>> On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma < >>>>>>>>> amolsharm...@gmail.com> wrote: >>>>>>>>> >>>>>>>>>> @hemesh,kk: >>>>>>>>>> >>>>>>>>>> let's take a test case : >>>>>>>>>> arr : 2 4 6 8 >>>>>>>>>> arr^2 : 6 8 10 10 12 14 (sum of each unique pair >>>>>>>>>> in arr[i]) >>>>>>>>>> >>>>>>>>>> let's say target sum is 26 >>>>>>>>>> >>>>>>>>>> your solution will return true as they 12+14=26 but in 12 and 14, >>>>>>>>>> 8 is common, infact 26 is not possible in the given array >>>>>>>>>> >>>>>>>>>> can u please elaborate how will you take care of such situation ? >>>>>>>>>> >>>>>>>>>> @jalaj: >>>>>>>>>> yes it's O( (n^3)*logn) >>>>>>>>>> >>>>>>>>>> @bhavesh: >>>>>>>>>> fyi.. >>>>>>>>>> log(n^3)=3*log(n)=O(log(n)) >>>>>>>>>> so it's same.. :P >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> -- >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> Amol Sharma >>>>>>>>>> Final Year Student >>>>>>>>>> Computer Science and Engineering >>>>>>>>>> MNNIT Allahabad >>>>>>>>>> >>>>>>>>>> <http://gplus.to/amolsharma99> >>>>>>>>>> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/><http://facebook.com/amolsharma99> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> On Mon, Jun 18, 2012 at 12:29 AM, KK <kunalkapadi...@gmail.com>wrote: >>>>>>>>>> >>>>>>>>>>> @Hemesh : +1 >>>>>>>>>>> @Jalaj : read Hemesh's solution again it is for 4sum. >>>>>>>>>>> In short, make a new array having sum of each unique pair of >>>>>>>>>>> given array. -> O(n^2) >>>>>>>>>>> sort it -> O(n^2) >>>>>>>>>>> for each number bi in new array, binary search (target - bi) in >>>>>>>>>>> the same array -> O(n^2) >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: >>>>>>>>>>>> >>>>>>>>>>>> The solution which hemesh gave was solution to 3SUM hard >>>>>>>>>>>> problem the best solution for which can be achieved in n^2 . >>>>>>>>>>>> And the original question is a kind of 4SUM hard problem for >>>>>>>>>>>> which best possible solution i think is again n^3 and Amol what >>>>>>>>>>>> you told is >>>>>>>>>>>> not n^3 , finding all triplets will itself take n^3 and doing a >>>>>>>>>>>> binary >>>>>>>>>>>> search again that sums upto n^3*logn. >>>>>>>>>>>> >>>>>>>>>>>> @shashank it is not a variation of 3SUM problem as in 3SUM >>>>>>>>>>>> problem a+b+c = some constant , but in your case it is "b+c+d = >>>>>>>>>>>> s-a", where >>>>>>>>>>>> a can change again and again so if you do even apply 3SUM logic to >>>>>>>>>>>> it you >>>>>>>>>>>> will have to do it for every a which will make it n^2*n = n^3 >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey < >>>>>>>>>>>> sanjaypandey...@gmail.com> wrote: >>>>>>>>>>>> >>>>>>>>>>>>> @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also >>>>>>>>>>>>> ur solution... >>>>>>>>>>>>> >>>>>>>>>>>>> -- >>>>>>>>>>>>> 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+unsubscribe@**googlegr****oups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>>>>>>>>>> . >>>>>>>>>>>>> For more options, visit this group at >>>>>>>>>>>>> http://groups.google.com/**group****/algogeeks?hl=en<http://groups.google.com/group/algogeeks?hl=en> >>>>>>>>>>>>> . >>>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> -- >>>>>>>>>>> You received this message because you are subscribed to the >>>>>>>>>>> Google Groups "Algorithm Geeks" group. >>>>>>>>>>> To view this discussion on the web visit >>>>>>>>>>> https://groups.google.com/d/**ms**g/algogeeks/-/9jCCN5iHDB8J<https://groups.google.com/d/msg/algogeeks/-/9jCCN5iHDB8J> >>>>>>>>>>> . >>>>>>>>>>> >>>>>>>>>>> To post to this group, send email to algogeeks@googlegroups.com. >>>>>>>>>>> To unsubscribe from this group, send email to >>>>>>>>>>> algogeeks+unsubscribe@**googlegr**oups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>>>>>>>> . >>>>>>>>>>> For more options, visit this group at http://groups.google.com/* >>>>>>>>>>> *group**/algogeeks?hl=en<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+unsubscribe@**googlegr**oups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>>>>>>> . >>>>>>>>>> For more options, visit this group at http://groups.google.com/** >>>>>>>>>> group**/algogeeks?hl=en<http://groups.google.com/group/algogeeks?hl=en> >>>>>>>>>> . >>>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>> -- >>>>>>>>> Regards, >>>>>>>>> >>>>>>>>> Jalaj Jaiswal >>>>>>>>> Software Engineer, >>>>>>>>> Zynga Inc >>>>>>>>> +91-9019947895 >>>>>>>>> * >>>>>>>>> * >>>>>>>>> FACEBOOK <http://www.facebook.com/jalaj.jaiswal89> >>>>>>>>> LINKEDIN<http://www.linkedin.com/profile/view?id=34803280&trk=tab_pro> >>>>>>>>> >>>>>>>>> -- >>>>>>>> You received this message because you are subscribed to the Google >>>>>>>> Groups "Algorithm Geeks" group. >>>>>>>> To view this discussion on the web visit >>>>>>>> https://groups.google.com/d/**msg/algogeeks/-/SGN_A_YrZlkJ<https://groups.google.com/d/msg/algogeeks/-/SGN_A_YrZlkJ> >>>>>>>> . >>>>>>>> >>>>>>>> To post to this group, send email to algogeeks@googlegroups.com. >>>>>>>> To unsubscribe from this group, send email to >>>>>>>> algogeeks+unsubscribe@**googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>>>>> . >>>>>>>> For more options, visit this group at http://groups.google.com/** >>>>>>>> group/algogeeks?hl=en<http://groups.google.com/group/algogeeks?hl=en> >>>>>>>> . >>>>>>>> >>>>>>> >>>>>>> -- >>>>>> You received this message because you are subscribed to the Google >>>>>> Groups "Algorithm Geeks" group. >>>>>> To view this discussion on the web visit >>>>>> https://groups.google.com/d/msg/algogeeks/-/eDvKXozaZV8J. >>>>>> >>>>>> 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. >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> regards, >>>>> Bhaskar Kushwaha >>>>> Student >>>>> CSE >>>>> Third year >>>>> M.N.N.I.T. Allahabad >>>>> >>>>> >>>>> -- >>>>> 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. >>> >> >> -- >> 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.
