In a two-dimensional grid, there are $n$ "snakes" (sets of contiguous grid-blocks). The snakes do not touch each other. The goal is to cut the grid into $n$ rectangles using $n-1$ "fences" (horizontal or vertical lines along grid lines, from edge to edge or to a previously-built fence). It is allowed to "trim" at most a single sqaure from each snake (by all fences together).

Below is an example with $n=3$ snakes. Fence #1 runs from edge to edge and trims a square from the bottom snake. Fence #2 runs from the leftmost edge to fence #1 and trims a square from the upper-left snake.

enter image description here

Below is another example with $n=4$ snakes.

enter image description here

Finally, here is an example where the snakes cannot be separated, since each initial fence would trim at least two squares from one of the snakes.

enter image description here

QUESTION: Is there a polynomial-time algorithm for deciding whether or not it is possible to separate the snakes?

NOTE: without the option to trim a single square from each snake, there is a simple greedy polynomial algorithm: at each step, find a horizontal or vertical fence that can be built without trimming any snake. If such a fence exists, build it; otherwise, declare that it is impossible.

  • 1
    $\begingroup$ Have you tried reducing from some NP-hard problem, like 3SAT? Maybe each variable $x_i$ corresponds to a snake $s_i$, where trimming one side of $s_i$ corresponds to setting $x_i$ to true and trimming the other side corresponds to setting $x_i$ to false, or something? $\endgroup$
    – D.W.
    Jan 18 '20 at 17:35
  • $\begingroup$ @D.W. Indeed my intuition was that the problem is NP-hard, but I could not think of similar two-dimensional problems. I will try to think about 3SAT. $\endgroup$ Jan 18 '20 at 20:04

This can be solved in polynomial time.

Say that in the input we are given the number of snakes $n$ and for every snake the squares it occupies. Let $m$ denote the total number of squares in all snakes. Assume every snake occupies at least three squares.

If no square has $x$-coordinate in some interval $[a, b]$, we can compress that interval into a single point. Then, the squares have coordinates in range $[0, 2m - 1]$. We will do DP in $\mathcal{O}(m^{5})$.

We calculate a DP with a state for every rectangle $(x_{0}, y_{0}), (x_{1}, y_{1})$.

We say that some snake is inside the rectangle if at least two of its squares are inside the rectangle. If at least two of some snake's squares are outside the rectangle, we say it is outside the rectangle. Notice that a snake can be both inside and outside the rectangle.

Say there are $k$ snakes inside the rectangle. The DP will represent whether we can separate the $k$ snakes with at most $k-1$ fences while obeying the trimming rules.

If any snake is both inside and outside the rectangle, we automatically fail and set $DP[x_{0}, y_{0}, x_{1}, y_{1}] = 0$. If only one snake is inside the rectangle, we set $DP[x_{0}, y_{0}, x_{1}, y_{1}] = 1$.

Otherwise, for every $x_{0} < x < x_{1}$, we will try to add a fence at this $x$-coordinate. If $DP[x_{0}, y_{0}, x, y_{1}]$ and $DP[x, y_{0}, x_{1}, y_{1}]$ and no snake inside the rectangle is outside of both of the two rectangles the fence splits our rectangle to, the fence works and we set the value of the DP to true. We similarly loop $y$-coordinates inside the rectangle. If no working fence was found, we set the DP to false.

In the end, the algorithm outputs $DP[0, 0, 2m-1, 2m-1]$

This DP can be optimised to $\mathcal{O}(n^{5} + m)$ by trimming states from the DP. We can assume that the DP-box doesn't start or end with an empty column or row, therefore there has to exist some snake with the leftmost square in the box, and we can store $x_{0}$ as the index of that snake, and whether the leftmost square in the box is the leftmost or second leftmost square of that snake (It cannot be any square after that, since then the snake would be outside the box). Storing $y_{0}, x_{1}, y_{1}$ similarly gives us $\mathcal{O}(n^{4})$ dp-states. We can further loop the $x$-coordinate of a fence over just the first and last $x$-coordinates of squares of snakes in the rectangle plus minus at most one, as every other fence either trims too much from a snake or would be equivalent to a fence placed directly to the left of it. Loop similarly over $y$. The number of such coordinates is $\mathcal{O}(n)$.

  • $\begingroup$ Your $O(m^5)$ solution seems to work but I cannot understand the sentence " and no snake inside the rectangle is contained in neither of the subrectangles". Basically the two subrectangles sum to the full rectangle, don't they ? On the $O(n^5)$ improvement, it deserves more explanation. Along x-axis, if snake $i$ extends from $x^i_l$ to $x^i_r$, there is actually no reason to cut on any $x$ which is not in $\{ x^i_l, x^i_l+1, x^i_r-1, x^i_r \}_i$ . $\endgroup$
    – Optidad
    Jan 20 '20 at 16:16
  • 1
    $\begingroup$ That check is necessary, since if the snake is three squares long, one square of it is outside the DP state we are currently solving, and we split the part of the snake inside the box into two parts, the snake will be in three parts, which is not allowed, but the DP doesn't fail since neither of the subrectangles contains that snake. $\endgroup$ Jan 20 '20 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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