OK, problem 5 yes? (hopefully I got it right this time). Very cute problem, by the way. I thought about a solution that seems tedious to prove (if it's actually correct). I did not prove it myself, so this might be totally bogus. So be on the lookout for easy counterexamples.
OK, here is the first idea that came to mind. First, finding the max sum seems easier. For each cell, fill it with the minimum value of the maximums of the lines that share that cell (e.g., if a cell is shared by 3 lines l1, l2, l3, and l1's maximum is 1, l2's maximum is 2, and l3's maximum is 3, we place 1 in that cell). The value of any cell cannot be increased, since otherwise the maximum of at least one line that contains it will be violated. For the min, here is what I had in mind. Let's say that we have resolved a line when we have placed its maximum in some cell on that line. For each cell, if all the lines that meet at that cell have the same maximum, resolve all the cells by placing their max in that cell. While there are still two unresolved lines that have the same maximum and share a cell, resolve them (by placing their max in that cell) provided that the third line (if it exists) that shares that cell has a bigger max. Consider some unresolved line l. No matter where we place l's maximum, we cannot resolve more than one line. So let's construct a bipartite graph that has a node on the left for each unresolved line, and a node on the right for each empty cell. Place an edge between line l and cell c if and only if we can place l's maximum in cell c (that is, iff each line that contains cell c has a maximum at least as big as l's maximum). Find a maximum matching in this graph. If line l is matched with line c, place l's maximum in cell c. Fill the remaining cells with 0. By construction, for each line, none of the cells on that line have a value greater than the line's maximum. If the graph above has a perfect matching, then we have resolved each line. I think you can prove that the graph has a perfect matching using Hall's theorem, but don't take my word for it. If you manage to prove that, maybe you can figure out the rest (or disprove it). 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 -~----------~----~----~----~------~----~------~--~---
