@venkat +1 On Sun, Aug 12, 2012 at 9:09 PM, ~*~VICKY~*~ <[email protected]>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~*~ <[email protected]>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 < >> [email protected]> 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~*~ <[email protected]>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 < >>>> [email protected]> wrote: >>>> >>>>> >>>>> @ Vicky >>>>> >>>>> Can yo explain with an illustration ? >>>>> >>>>> >>>>> On Sat, Aug 11, 2012 at 10:07 PM, ~*~VICKY~*~ <[email protected] >>>>> > 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 <[email protected]>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 >>>>>>> <[email protected]>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 [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. >>>>>>> >>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> 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 [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. >>>>> >>>> >>>> >>>> >>>> -- >>>> 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 [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. >>> >> >> >> >> -- >> 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 [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.
