SPECIES - Editorial

PROBLEM LINK:

Practice
Contest

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:

  1. There are no two adjacent cells filled with ‘G’

  2. Each cell adjacent to a cell filled with ‘B’ can be either also filled with ‘B’, or can be empty

  3. 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:

  1. Size of X is 1, i.e. X contains only cell C
  2. 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:

  1. S = 1
  2. 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.

5 Likes

It can also be done with brute force with some optimizations.
Here’s my code - https://www.codechef.com/viewsolution/13164129

2 Likes

It should be 3^Q,right in here

there are Q^3 possible ways to replace all the questions marks with these characters, where Q is the number of question marks in the grid ?

2 Likes

can someone please tell me why my solution didn’t pass subtask 1 (2 <= n <= 3) but passed subtask 2 and 3 -_-

https://www.codechef.com/viewsolution/13163591

2 Likes

I remember trying 5 times to solve this Q…only to delete my entire code when it failed at the sample test. (And I thought only dp was a pain…:_( )

But well, first things first, time to brush up the pre-requisites then.

N<=50 is just too less to force a complexity of O(N^{2}).

1 Like

The links for tester’s and second tester’s solution are not working.
alt text

alt text

2 Likes

Was anybody else reminded of the concept of seed fill algorithm used to color the closed figures in Graphics . I used the similar function to determine the connected components which can either be ‘B’ or ‘P’.

1 Like

@coolvaibhav_94 Even i failed subtask 1.Please let me know if you find the bug.

1 Like

Awesome Explanation!

1 Like

I have no idea why my solution isn’t working. All the sample testcases specified in the problem work, and I’ve tried so many other testcases and compared the outputs on both my solution and the setter’s solution. The strange thing is that none of the sub-tasks are giving right answer. If anyone has any tricky corner cases please let me know.
My solution: https://www.codechef.com/viewsolution/13161929

1 Like

Hi @kingofnumbers, I realised that the test cases for this problem are pretty weak. My solution (link text) fails on many testcases such as the one below even though it got an AC.

4



???B

I hope such cases are overlooked in future so that only the accurate submissions get Accepted.

Hi @errichto, I have coded my solution exactly as you guys have explained in the editorial but my solution is failing for Subtasks 2 and 3. Can you post the test cases and expected outputs for all subtasks as the competition is now over? It can help me and many others debug our solution :slight_smile:

A similar problem was there in INOI this year, not really same(not complaining), which used similar concepts. I wish I solved the problem back then.

1 Like

Hi @errichto, My solution is also same as described in the editorial. It would be great if anyone can tell some corner cases. My solution failed on subtask 2 and 3. Corner cases of subtask 2 would be helpful as the solution is pretty straightforward for that.

To compute connected components we can use DSU as well. Here.

Congratulations. Still, I think the intended solution is easier :smiley:

7 Likes

Thanks. But, I think that my solution was easier for me. We all have different Point of views though.

2 Likes

Of course, corrected, thanks!

I’m glad you like it :slight_smile:

1 Like