PROBLEM LINK:
Author: admin2
Testers: Hasan Jaddouh
Editorialist: Pawel Kacprzak
DIFFICULTY:
Easy
PREREQUISITES:
Connected components
PROBLEM:
Given a grid with 2 rows and n columns, where each cell is either white or black, find out if all black cells can form a single snake. A snake is a connected component of black cells, which, after distinguishing a head and a tail of the snake, such that we can go from H to T visiting all black cells, and visit each such cell exactly once.
EXPLANATION:
The problem can be divided into two parts:
- Finding out if all black cells form a connected component
- Finding out if there exist two black cells, H and T, such that we can go from H to T visiting all black cells, and visiting each such cell exactly once.
Part 1:
This can be solved easily by building a graph G consisting only of black cells and running a DFS over G to find out if all its vertices are in a single component. Two vertices (cells) in G are connected if and only if they share a common side. If all vertices form a single component, then we can proceed to the second part. Otherwise, the answer is clearly negative, because there are at least two black cells, such that one cannot be reached from the other, so if even some black cells can form a snake, there will still exist a black cell which is not a part of the snake.
Part 2:
Now, we know that all black cells form a connected component i.e. each two cells are reachable from each other in G. The next question is: are there two black cells, H and T, such that we can draw a path from H to T visiting all black cells, and visit each such cell only once.
If we take a closer look at the possible columns of the grid, there are only 4 possibilities:
Type 1:
Type 2:
Type 3:
Type 4:
and only the first 3 of the above ones are interesting. Now, there are two cases to consider:
Case 1: The number of columns of types 1 or 2 is at most 1
Case 2: There are at least 2 columns of types 1 and 2
Solving Case 1: In the first case, the answer is automatically positive. To illustrate that, let’s consider a few example grids (only the interesting part showing the full connected component of G is shown). Letters H and T corresponds to the first and the last vertices of the path, and the path itself is denoted by a red line:
Example 1: There is no column with one black cell:
Example 2: There is a single column with a black cell surrounded by columns with two black cells:
Of course, the situation is similar when the column with a single black cell has this cell in the bottom row.
Example 3: There is a single column with a single black cell and it’s the left-most column with black cells:
Of course, the situation is similar when the column with a single black is the right-most column with black cells.
There is also a case when there is only a single black cell in the grid, but then solution trivial - we just set H = T.
Solving Case 2: In the second case, let’s consider two columns with single black cells such that all columns between them have two black cells, and let indices of these columns to be i and j, where i < j. For simplicity, let’s assume that cell H is to the left of cell T in the grid. It should be obvious that H should be in a column with index less or equal to i, and T should be in a column with an index greater or equal to j. This is true because each black cell can be visited only once, so if the path crosses column i from the left, it cannot cross it again from the right side.
We can separate two subcases here:
Subcase 1: Columns at indices i and j have their black cells in the same rows
Subcase 2:. Columns at indices i and j have their black cells in different rows
We can claim that in the first subcase, the solution can exist if and only if the number of columns with two black cells between i and j is even.
Moreover, we can argue that in the second subcase, the solution can exist if and only if the number of columns with two black cells between i and j is odd. To see that, let’s take a look at these two cases in the pictures below:
Example of Subcase 1:
Example of Subcase 2:
The observations follow from the facts that there are only two rows in the grid, the path goes from column i to column j (because we assumed that H is to the left to T), and so it can never turn from left to right between columns i and j, in other words, it can only go vertically and to the right.
Based on the above observation, the only thing left to do is to consider every pair of columns with a single black cell such that all columns between them have two black cells. In total, there are at most n such columns. For each such pair, based on the type of these two columns and the parity of the number of columns between them, i.e. j-i-1, we can verify if such pair of columns is valid or not. The overall solution exists if and only if all such pairs of columns are valid. You can also notice, that to the left of the left-most columns with a single cell can be columns with two black cells (similarly to the right of the right-most column with a single cell), but this can be handled in the same manner as the case when there is only one column with a single black cell in the grid.
The above solution can be implemented in O(n) time.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.
