@vicky Got it . thanks ..is it possible to ignore the preprocessing time when calculating time complexity?
On Sun, Aug 12, 2012 at 10:02 PM, shady <sinv...@gmail.com> wrote: > @venkat +1 > > On Sun, Aug 12, 2012 at 9:09 PM, ~*~VICKY~*~ <venkat.jun...@gmail.com>wrote: > >> @Arun: This approach is constant time once the array is build for any >> queries that follows. :) You know sum for all possible rectangles in the >> given 2d array thats makes it better than computing sum for each input. >> Hope it makes sense >> >> >> On Sun, Aug 12, 2012 at 9:07 PM, ~*~VICKY~*~ <venkat.jun...@gmail.com>wrote: >> >>> Fine, the basic idea of using dp here is sum of each rectangle is a >>> dependent sub problem. So when u find sum for smaller rectangle we can use >>> it to compute sum of bigger rectangle with new coordinates added to >>> previous small rectangle. So u can compute the sum array by using this >>> formula >>> >>> sum[i][j] = sum[i-1][j-1] + (sum[i-1][j] - sum[i-1][j-1]) + (sum[i][j-1] >>> - sum[i-1][j-1])+ip[i][j] >>> [smaller rect] [that row sum value] [that >>> col sum value] >>> >>> >>> >>> On Sun, Aug 12, 2012 at 8:54 PM, Srividhya Sampath < >>> srisam261...@gmail.com> wrote: >>> >>>> @vicky >>>> >>>> can yo explain the logic behind the 'Sum Array' computation (if >>>> possible elaborately )? >>>> >>>> >>>> On Sun, Aug 12, 2012 at 8:19 PM, ~*~VICKY~*~ >>>> <venkat.jun...@gmail.com>wrote: >>>> >>>>> Lets build the array for the example you gave. >>>>> >>>>> i/p: >>>>> >>>>> 0 1 2 3 >>>>> 4 5 6 7 >>>>> 8 9 10 11 >>>>> >>>>> (x1,y1) = (0,0) >>>>> (x2,y2) = (1,2) >>>>> sumArray >>>>> 0 1 2 3 >>>>> 4 10 18 28 >>>>> 12 27 45 66 >>>>> (will take O(n^2) to build above array) >>>>> So now when you get coordinates as input, you can calc the sum by >>>>> >>>>> Ans = sumArray[x2][y2] - sumArray[x1][y1] + ip[x1][y1] >>>>> >>>>> For our case it will be Ans = 18-0+0 = 18 >>>>> >>>>> Please lemme know if any bugs with the logic. >>>>> >>>>> >>>>> On Sun, Aug 12, 2012 at 6:27 PM, Srividhya Sampath < >>>>> srisam261...@gmail.com> wrote: >>>>> >>>>>> >>>>>> @ Vicky >>>>>> >>>>>> Can yo explain with an illustration ? >>>>>> >>>>>> >>>>>> On Sat, Aug 11, 2012 at 10:07 PM, ~*~VICKY~*~ < >>>>>> venkat.jun...@gmail.com> wrote: >>>>>> >>>>>>> May be you can consider creating a 2d array to pre process and store >>>>>>> all the rectangle sums as a dependent subproblem, the sum of larger rect >>>>>>> will be currValuesAdded+OldRectSum. So when you get the coordinate as >>>>>>> input >>>>>>> u can calc the needed sum by subtracting sum of big rect and small rect >>>>>>> which is not included in the given coordinates. This can be called >>>>>>> constant >>>>>>> time if u don't include the preprocessing time. >>>>>>> >>>>>>> >>>>>>> On Sat, Aug 11, 2012 at 9:57 PM, adarsh kumar <algog...@gmail.com>wrote: >>>>>>> >>>>>>>> Sum of the integers meaning? Do you mind giving an example test >>>>>>>> case? >>>>>>>> >>>>>>>> regards. >>>>>>>> >>>>>>>> On Sat, Aug 11, 2012 at 7:10 PM, Srividhya >>>>>>>> <srisam261...@gmail.com>wrote: >>>>>>>> >>>>>>>>> hi all:) >>>>>>>>> >>>>>>>>> The coordinates of a rectangle will be specified. there is a >>>>>>>>> matrix of integers. yo should find the sum of the integers that fall >>>>>>>>> in the >>>>>>>>> region specified by the coordinates . >>>>>>>>> >>>>>>>>> The solution to be in constant time . >>>>>>>>> >>>>>>>>> -- >>>>>>>>> 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/-/qHSmXBshmS4J. >>>>>>>>> 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. >>>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> -- >>>>>>> Cheers, >>>>>>> >>>>>>> Vicky >>>>>>> >>>>>>> -- >>>>>>> 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. >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> Cheers, >>>>> >>>>> Vicky >>>>> >>>>> -- >>>>> 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. >>>> >>> >>> >>> >>> -- >>> Cheers, >>> >>> Vicky >>> >>> >> >> >> -- >> Cheers, >> >> Vicky >> >> -- >> 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.
