Oops, please ignore. I did not notice that you were not talking about the first problem on that page.
On Feb 6, 3:51 pm, dor <[EMAIL PROTECTED]> wrote: > Since N is at most 60, an O(N^3) algorithm should be fast enough (you > can probably do better, this is just a straightforward solution). > > Let sum(i, j) = the sum of all cells in the rectangle spanning rows 1 > through i, and columns 1 through j (that is, the rectangle with upper > left corner at cell (1, 1), and lower right corner at cell (i, j)). > You can find sum(i, j) for all (i, j) in O(N^3). > > Suppose you are given a square with upper left corner at (a, b) and > lower left corner (c, d). Can you find its sum in O(1) using the sum > values you've already computed? > > Now you can simply loop all possible squares and pick the best. You > can do this in O(N^3) as follows. Represent a square using the > coordinates of its upper left corner and its edge length (i.e., a > square with upper left corner (i, j) and length l spans l rows > starting with row i, and l columns starting with column j). For a > fixed square with upper left corner at (i, j) and edge length l, find > its lower right corner and compute the sum of the square in O(1). > > On Feb 6, 12:30 pm, robin <[EMAIL PROTECTED]> wrote: > > > Hi > > I was trying to solve problem number 5 from 15th bulgarian > > informatics > > olympiad. > > on the following website: > > >http://www.math.bas.bg/bcmi/noi99.html > > > (we have to find the minimum and maximum possible values of numbers > > on > > the star board) > > I don't know how to go about it. Any ideaz?? --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
