PROBLEM LINK:
Author: Kamil Dębowski
Testers: Hasan Jaddouh, Sergey Kulik
Editorialist: Pawel Kacprzak
DIFFICULTY:
Simple
PREREQUISITES:
Graphs, connected components, dfs
PROBLEM:
For a given grid of size N \times N, we say that two of its cells are adjacent if and only if they share a side. Moreover, each cell contains either a determined character from set \{., B, G, P\}, or a question mark. Cells containing character ‘.’ are considered empty. The task is to count the number of ways to replace all question marks with characters \{B, G, P\}, in such a way that in the resulting grid:
-
There are no two adjacent cells filled with ‘G’
-
Each cell adjacent to a cell filled with ‘B’ can be either also filled with ‘B’, or can be empty
-
Each cell adjacent to a cell filled with ‘P’ can be either also filled with ‘P’, or can be empty
Two ways of replacing all question marks with \{B, G, P\} are considered different in and only if there exists a cell originally filled with a question mark which is replaced with different characters in both these ways.
QUICK EXPLANATION:
Use dfs to compute connected components of adjacent non-empty cells in the grid. Solve the problem independently for each component and multiply obtained sub-results.
EXPLANATION:
In all the subtasks there are T \leq 50 test cases to handle. Since we are going to solve the problem independently for all these test cases, the time complexity of each of the below approaches has to be multiplied by T to get the total time complexity of a solution.
Subtask 1
In the first subtask N is either 2 or 3, so one can just try all possibilities of replacing the question marks in the grid, and for each such possibility, check if it produces a valid grid according to the rules defined in the problem. Since each question mark can be replaced either with ‘B’, ‘G’, or ‘P’, there are 3^Q possible ways to replace all the questions marks with these characters, where Q is the number of question marks in the grid. Notice that verifying if a resulting grid is valid can be done in O(N \cdot N) time by just iterating over all the cells, and for a single cell, checking if its adjacent cells are filled in a valid way. Since Q can be at most N \cdot N, the total complexity of this method is O((3^{N^2}) \cdot N^2), which is acceptable for such limited N as we have in this subtask.
Subtask 2 and 3
In both these subtasks, we are going to represent the grid as a graph G, where cells are vertices and there is an edge between two cells if and only if both of them are not empty and they are adjacent. Next, we are going to dfs to compute connected components of G. Connected components can be computed efficiently using a dfs.
Approaches for both these subtasks use these precomputed connected components of G.
Subtask 2
In the second subtask, N can be at most 50, but we know that the each cell in the grid is either empty or contains a question mark. Let’s consider an arbitrary cell C containing a question mark. Cell C belongs to exactly one connected component of G, let’s call this component X. Now, there are two cases to consider:
- Size of X is 1, i.e. X contains only cell C
- Size of X is at least two, i.e. X contains at least two question marks
In the first case, we know that there are 3 possibilities to replace the question mark in C. Thus, it can be replaced with any character in \{B, G, P\}, because it is isolated.
In the second case, we know there are at least 2 adjacent cells with question marks in X. Let Q be the number of question marks in X. First of all, we know that none of these question marks can be replaced with ‘G’ because no two ‘G’ can be adjacent. Secondly, if we replace one of these question marks with let’s say ‘B’, then all other X-1 question marks have to replaced also with ‘B’, because replacing one question mark with ‘B’ forces all its adjacent cells also to be replaced with ‘B’, and this process will continue until all question marks in X are replaced with ‘B’. Since we can replace the first question mark in X with either ‘B’ or ‘P’, then there are exactly 2 ways of replacing all question marks in X.
The final result is just the product of result obtained for all connected components of G. Notice that we need to only know the size of a component to get its result, then the total time complexity is the time needed to compute the connected components plus the time proportional to the number of these components. Thus, overall time complexity can be bounded by O(N \cdot N).
Subtask 3
In the third subtask we also have N \leq 50, but now the initial grid can contain characters ‘B’, ‘G’ and ‘P’. The solution is very similar to the second subtask, but there are more cases to consider. Again, we are going to solve the problem independently for each component and multiply the obtained results to get the final result.
Let’s consider a connected component X and let’s define:
c_G := number of cells containing ‘G’ in X
c_B := number of cells containing ‘B’ in X
c_P := number of cells containing ‘P’ in X
c_? := number of cells containing a question mark in X
Let also S be the number of cells in X.
There are several cases to consider:
- S = 1
- S \geq 2
In the first case, when there is only one cell in X there are two sub-cases: either this cell contains a question mark or not. If it contains a question mark, we can replace this question mark with either of characters ‘B’, ‘G’, or ‘P’, so there are 3 ways to do that. Otherwise, there is no question mark to replace, and the component X is valid, because the only cell in it is not adjacent to any other cells, so it doesn’t affect the result in any way.
In the second case, S \geq 2, so there are at least two adjacent cells in X. Now, if c_G > 0, then the result for X is 0, because cell filled with ‘G’ cannot be adjacent to any other non-empty cell. Moreover, if c_B > 0 and c_P > 0, then also the result for X is 0, because there is at least one pair of adjacent cells in X, where one them contains ‘B’ and the other contains ‘P’, which is not allowed. Otherwise, we know that there is no ‘G’ in X and all cells in X contain ‘B’ or all cells in X contain ‘P’. Thus, if c_? > 0, there are exactly 2 ways to replace all questions marks in X: either we can replace all of them with ‘B’ or replace all of them with ‘P’.
As mentioned earlier, the final result is just the product of result obtained for all connected components of G. Since all the counters needed to compute a result for one component can be computed while computing the component itself, the total time complexity of the solution is O(N \cdot N).
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
First tester’s solution can be found here.
Second tester’s solution can be found here.
_1.png)
_2.png)
