4
\$\begingroup\$

For this problem you are given an \$n \times n\$ matrix of integers. The task is to find a pentagon in the matrix with maximum sum. The pentagon must include part (or all) of the x and y axes as two of its sides starting from the top left cell.

All the sides except one must be horizontal or vertical. The remaining side is at 45 degrees ( that is it goes up one for each step to the right).

This picture shows a matrix with a pentagonal part shaded.

enter image description here

Either one or two of the sides can have length zero, as in this example where two zero length sides have turned the pentagon into a triangle. This is an optimal triangular solution for this matrix but may not be an optimal pentagon.

enter image description here

Or this example where one zero-length side has turned a pentagon into a rectangle. This happens to be the optimal rectangle but may not be an optimal pentagon.

enter image description here

[[ 3  0  2 -3 -3 -1 -2  1 -1  0]
 [-1  0  0  0 -2 -3 -2  2 -2 -3]
 [ 1  3  3  1  1 -3 -1 -1  3  0]
 [ 0  0 -2  0  2  1  2  2 -1 -1]
 [-1  0  3  1  1  3 -2  0  0 -1]
 [-1 -1  1  2 -3 -2  1 -2  0  0]
 [-3  2  2  3 -2  0 -1 -1  3 -2]
 [-2  0  2  1  2  2  1 -1 -3 -3]
 [-2 -2  1 -3 -2 -1  3  2  3 -3]
 [ 2  3  1 -1  0  1 -1  3 -2 -1]]

The winning criterion is asymptotic time complexity. E.g. \$O(n^2)\$ time.

\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

Python, \$\mathcal O(n^2)\$

def best_pentagon(grid):
    best = float("-inf"), -1, -1, -1
    rects = [0] * len(grid[0])
    pents = [(0, 0)] * len(grid[0])
    for y, row in enumerate(grid):
        line = 0
        lines = [line := line + value for value in row]
        rects = [rect + line for rect, line in zip(rects, lines)]
        pents = [
            max((rect, y), (pent + line, z))
            for rect, (pent, z), line in zip(rects, pents[1:], lines)
        ] + [(rects[-1], y)]
        best = max(best, max((pent, x, y, z) for x, (pent, z) in enumerate(pents)))
    return best

Attempt This Online!

Returns a tuple (sum, x, y, z) for a pentagon summing to sum whose bottom row ends at \$(x, y)\$ and whose rightmost column ends at \$(x + y - z, z)\$.

How it works

A pentagon whose bottom row ends at \$(x, y)\$ is either

  • the rectangle with corner \$(x, y)\$, or
  • the union of the partial row \$(0, y)…(x, y)\$ with a pentagon whose bottom row ends at \$(x + 1, y - 1)\$.

This leads to a straightforward dynamic programming solution.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ This is really elegant and smart. How can I print out the optimal pentagon found? The final value of pentagons is "0 -15" for the last example I gave but I don't know how to interpret it. \$\endgroup\$
    – Simd
    Dec 21, 2023 at 9:33
  • 1
    \$\begingroup\$ @Simd I don’t know where you got “0 -15”, but I’ve updated the solution to return the pentagon’s coordinates. \$\endgroup\$ Dec 21, 2023 at 18:56
4
\$\begingroup\$

Python, \$\mathcal{O}(n^2)\$ time (optimal)

def solve(n, grid):
    # Pad the given grid with zeros to form a right triangle.
    # Note that any pentagonal region in this triangle can be truncated
    # to a valid pentagonal region within the original grid,
    # by stripping away the padded zeros,
    # so if we solve the maximum pentagon problem within this triangle,
    # we get a valid solution for the grid.
    # This is done to simplify coding. It adds some constant factor
    # but doesn't change the overall time complexity.
    triangle = [row[:] for row in grid]
    for r in range(n-1):
        triangle[r] += [0] * (n-1-r)
        triangle.append([0] * (n-1-r))
    m = n * 2 - 1 # size of the triangle

    # Calculate cumulative sums in two directions: rightward and downward.
    right_cumsum = [row[:] for row in triangle]
    down_cumsum = [row[:] for row in triangle]
    for r in range(m):
        for c in range(1, m - r):
            right_cumsum[r][c] += right_cumsum[r][c-1]
    for r in range(1, m):
        for c in range(m - r):
            down_cumsum[r][c] += down_cumsum[r-1][c]

    # We solve the pentagon problem by first forming a large triangle
    # containing the upper left corner, and truncating smaller triangles
    # from the rightmost and downmost ends.
    ans = float('-inf')
    for t in range(1, m+1):
        # From the cumulative sums calculated above, we can get the sums of
        # horizontal strips and vertical strips that form the triangle.
        # The cumulative sum of the horizontal strips gives all possible cutaways
        # from the bottom; that of vertical strips gives those from the right.

        # vertical_strips[k] == sum of k vertical strips from upper right
        # horizontal_strips[k] == sum of k horizontal strips from lower left
        vertical_strips = [0] + [down_cumsum[i][t-1-i] for i in range(t)]
        horizontal_strips = [0] + [right_cumsum[t-1-i][i] for i in range(t)]
        for i in range(1, t+1):
            vertical_strips[i] += vertical_strips[i-1]
            horizontal_strips[i] += horizontal_strips[i-1]
        triangle_sum = horizontal_strips[t]

        # Now, for each possible cutaway from the bottom, we will find the
        # smallest valid cutaway from the right (so we get the maximum sum
        # for the given triangle size and bottom cut size).
        # When k horizontal strips are cut, valid cuts from the right are
        # zero to t-k vertical strips (inclusive).
        # Minimum of these values can be preprocessed in O(m) via cumulative minimum.
        # To make sure that the top left cell is included, k goes up to t-1.
        for i in range(1, t+1):
            vertical_strips[i] = min(vertical_strips[i], vertical_strips[i-1])
        for k in range(0, t):
            cur_area = triangle_sum - horizontal_strips[k]
            max_area = cur_area - vertical_strips[t-k]
            ans = max(ans, max_area)
    return ans

Attempt This Online!

This is an art of cumulative operations lol. This is optimal in terms of asymptotic time complexity because you need \$\mathcal{O}(n^2)\$ time just to observe all the elements in the matrix.

\$\endgroup\$
1
  • \$\begingroup\$ This is great. How can I see what the optimal pentagon is? \$\endgroup\$
    – Simd
    Dec 21, 2023 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.