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 -~----------~----~----~----~------~----~------~--~---
