4
\$\begingroup\$

Consider an \$n \times n\$ grid of integers. The task is to draw a straight line across the grid so that the part that includes the top left corner sums to the largest number possible. Here is a picture of an optimal solution with score 45:

enter image description here

We include a square in the part that is to be summed if its middle is above or on the line. Above means in the part including the top left corner of the grid. (To make this definition clear, no line can start exactly in the top left corner of the grid.)

The task is to choose the line that maximizes the sum of the part that includes the top left square. The line must go straight from one side to another. The line can start or end anywhere on a side and not just at integer points.

The winning criterion is worst case time complexity as a function of \$n\$. That is using big Oh notation, e.g. \$O(n^4)\$.

Test cases

I will add more test cases here as I can.

The easiest test cases are when the input matrix is made of positive (or negative) integers only. In that case a line that makes the part to sum the whole matrix (or the empty matrix if all the integers are negative) wins.

Only slightly less simple is if there is a line that clearly separates the negative integers from the non negative integers in the matrix.

Here is a slightly more difficult example with an optimal line shown. The optimal value is 14.

enter image description here

The grid in machine readable form is:

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

Here is an example with optimal value 0.

enter image description here

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

Posted a question to cstheory about lower bounds for this problem.

\$\endgroup\$
10
  • 1
    \$\begingroup\$ Must the line end at integer? \$\endgroup\$
    – l4m2
    Dec 16, 2023 at 23:20
  • \$\begingroup\$ @l4m2 No, although a fast algorithm for that case would be really interesting too. \$\endgroup\$
    – Simd
    Dec 17, 2023 at 3:25
  • 2
    \$\begingroup\$ I can't think of an approach that is better than O(n^4). There are O(n^2) meaningfully distinct directions of the line (the number of slopes = 2 + 2 * number of distinct x/y where 1<=x,y<n = A002088(n-1) = asymptotically n^2). For each slope, as the line moves in one direction, the points will be included one at a time. You need to account for every single partition made with the slope, so it is O(n^2) per slope, giving O(n^4) in total. Maaaaaaybe one can deduplicate the partitions, but I doubt the count is asymptotically lower. \$\endgroup\$
    – Bubbler
    Dec 18, 2023 at 23:42
  • 1
    \$\begingroup\$ It's worth noting the relation with Euclid's orchard. The "meaningful directions" @Bubbler mentions are all the (dx, dy) where dx, dy are coprimes. There are (n^2 * 6/π^2) of them on average, i.e. ~61% of n^2. Not a big improvement but at least one can avoid duplicated slopes. \$\endgroup\$
    – Pierre D
    Jan 1 at 18:54
  • 1
    \$\begingroup\$ BTW, when I have time, I've been thinking about a branch-and-bound algorithm that might possibly save some exploration time (on average, but not on the worst case). I have no definite idea of how much of the computation can be avoided. I'll post probably on the SO question rather than here if I get to it and it's successful. If I get to it and it's not successful, I'll let you know as well, of course. \$\endgroup\$
    – Pierre D
    Jan 3 at 2:13

1 Answer 1

4
+50
\$\begingroup\$

Python3, O(n^4):

I'm not 100% sure this is correct, but I think at least the approach is solid and it seems to work OK.


import numpy as np
import fractions

def best_line(grid):
    n, m = grid.shape
    D = [(di, dj) for di in range(-(n - 1), n) for dj in range(-(n - 1), n)]
    def slope(d):
        di, dj = d
        if dj == 0:
            return float('inf') if di <= 0 else float('-inf'), -di
        else:
            return fractions.Fraction(di, dj), fractions.Fraction(-1, dj)
    D.sort(key=slope)
    D = np.array(D, dtype=np.int64)
    s_max = grid.sum()
    for grid in (grid, grid.T):
        left_sum = 0
        for j in range(grid.shape[1]):
            left_sum += grid[:,j].sum()
            for i in range(grid.shape[0]):
                p = np.array([i, j], dtype=np.int64)
                Q = p + D
                Q = Q[np.all((0 <= Q) & (Q < np.array(grid.shape)), axis=1)]
                s = left_sum 
                for q in Q:
                    if not np.any(q):
                        break
                    if q[1] <= j:
                        s -= grid[q[0],q[1]]
                    else:
                        s += grid[q[0],q[1]]
                    s_max = max(s_max, s)
    return s_max
\$\endgroup\$
13
  • \$\begingroup\$ Can you explain the method? \$\endgroup\$
    – Simd
    Dec 18, 2023 at 9:05
  • \$\begingroup\$ @Simd It spins a line around each grid point, incrementally adding and removing points as it crosses them. \$\endgroup\$ Dec 18, 2023 at 16:56
  • \$\begingroup\$ I am impressed that method gives the optimal solution for my 10 by 10 problem now given in the question. I wonder where it is drawing the line. \$\endgroup\$
    – Simd
    Dec 18, 2023 at 17:48
  • \$\begingroup\$ Sounds it work correctly but I feel it not optimal complexity \$\endgroup\$
    – l4m2
    Dec 19, 2023 at 0:48
  • 1
    \$\begingroup\$ In the code for D (the slopes), you can avoid duplicates (there should be about 39% of them where dx, dy are not coprime). Doesn't change the O() of course. \$\endgroup\$
    – Pierre D
    Jan 1 at 18:56

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.