Finding two disjont longest possible vertical or horizontal lines in 2D matrix with non-usable cells

Question

The problem is to find two disjont longest possible (but with equal length) horizontal or vertical lines in given 2D matrix, where some cells are excluded from use. The disjont means that any cell that is part of first line cannot be neighbour to any other cell in second line (they can diagonally), and any cell included in first line cannot be included in second line. That's a bit modified problem statement from XXXI Polish Olympiad in Informatics, link to the problem in polish language

The 2D matrix has N*N size and 1 <= N <= 1500, so we can implement solution with something about O(N^2) time complexity.

If matrix[i][j] is usable (our line can include this cell), then it's equal to .. Otherwise, it's X.

Let's see an example for below input:

5 -> this is N
.X...
.XXXX
XX...
.....
.X.X.

Assume matrix[i][j] = 1 if i,j cell belongs to first line, and matrix[i][j] = 2 if cell belongs to second line. Our solution might be:

.X...
.XXXX
XX..2
111.2
.X.X2

I'm really unable to think of solution to this problem. I see too many different cases to handle, so it smells like DP, but I cannot see recursive relation. Especially if problem has to be solved with O(N^2) time complexity. I hope for well explained solution or algorithm idea.

I'm not sure if it's good place to ask this type of question, but as long as I don't have any code just because I also have no idea, my question on StackOverflow would be closed immediately

Answer 1

It seems like a straightforward matter of programming.

Finding a single longest line

Suppose you just want to find one line, and you want it to be the longest possible. You can do this in $O(N^2)$ time.

Precompute, at each location $\ell$, the length of the longest horizontal line that starts at $\ell$ and goes to the right. This can be precomputed in $O(N^2)$ time by first filling in the values for the right column of the array, then scanning left-to-right.

Similarly, you can precompute at each location the length of the longest vertical line goes down.

Now you can iterate over all $O(N^2)$ locations, look up the length of the longest line that goes down or to the right from it, and take the max over all of these.

Finding two lines: Naive algorithm

Search over all possible choices of the first line. There are only $O(N^3)$ possibilities ($N^2$ choices for the starting point, 2 choices for the direction, and $\le N$ choices for the length of the line), so you can enumerate all of them in $O(N^3)$ time.

Now the other line must be either entirely above the first line, entirely below it, entirely to the right of it, or entirely to the left of it. Try each of these four cases separately.

Let's focus on the case where the second line is entirely above the first line. That means there is some known $k$ such that the second line must be entirely within the top $k$ rows of the matrix (i.e., within the $k \times n$ rectangle at the top of the matrix).

So precompute in advance, for each $k$, the length of the longest line within the first $k$ rows. Do the same for the last $k$ rows, the right $k$ columns, and the left $k$ columns. This can be done in $O(N^2)$ time: you iterate over $k:=1,2,\dots,N$, and for each $k$, search over all locations in the $k$th row (column) and look up the length of the longest line starting there (using the precomputed arrays mentioned above), and take the max of those $N$ values along with the value for $k-1$.

This means that for each candidate for the first line, you can compute in $O(1)$ time the length of the longest possibility for the second line, which means you can compute in $O(1)$ time whether it is possible to place a second line of equal length.

Since there are $O(N^3)$ candidates for the first line, this leads to an algorithm with running time $O(N^3)$. This is probably already fast enough for the parameter values you list.

Optimization

You can speed up this algorithm to $O(N^2 \lg N)$ time, as follows. Iterative over all possibilities for the starting location of the 1st line. Now do a binary search over the length of the 1st line. For each candidate, you are able to tell whether there exists a way to draw 2nd line of equal length. Keep increasing the candidate length of the 1st line until it is maximized, using binary search to find the maximum.

I wouldn't be surprised if there is a way to achieve $O(N^2)$ time, but $O(N^2 \lg N)$ should already be more than sufficient for your parameters.

Answer 2

Theorem. If we have more than two rows (or more than two columns) with longest line value k then we can introduce two disjount row (column) lines as a solution. Then $z^*\ge k$.

For an algorithm of order $O(N^2)$, you can find the longest line in each row i in O(N) and the longest line in each column j in O(N); Let these values as $MR_i$ and $MC_j$.

For N rows and N columns it takes $O(N^2)$.

Suppose that we select 3 rows and 3 columns according to the 3 maximum values of them as $MR_{i1},MR_{i2},MR_{i3}$ and $MC_{j1},MC_{j2},MC_{j3}$. Moreover, we can assume that $MR_{i3}\ge MC_{j3}$.

Then $z^*\ge MR_{i3}$, since for such a solution value we can introduce two disjoint rows with values $MR_{i1},MR_{i2}$ or two disjoint rows with values $MR_{i2},MR_{i3}$ or two disjoint rows with values $MR_{i1},MR_{i3}$.

Based on the produced solution, it is sufficient to search for a solution with $z=\ MR_{i1}\ or\ MR_{i2}\ or \ MC_{j1}\ or \ MC_{j2}$

(if $MC_{j1}\ or \ MC_{j2}\ >\ MR_{i3}$).

Based on the above theorem, we have at most two rows (columns) with values $MR_{i1}\ or\ MR_{i2}$ ($MC_{j1}\ or \ MC_{j2}$). Otherwise, we had produced a better solution (for example with value $MR_{i2}$) and based on the produced solution, it was sufficient to search for a solution with $z=\ MR_{i1}\ or \ MC_{j1}\ or \ MC_{j2}$.

Therefore, we have at most 16 comparisons to test that a couple of selected rows and selected columns can produce a better solution or not.

Therefore, we have an $O(N^2)$ algorithm.