patternMinor
Separating the snakes
Viewed 0 times
separatingsnakesthe
Problem
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.
Below is another example with $n=4$ snakes.
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.
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.
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.
Below is another example with $n=4$ snakes.
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.
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.
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#119681, answer score: 3
Revisions (0)
No revisions yet.