CF Step
Youtube Linkedin Discord Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Back to homepage


Define adj_cc_count[i][j] to be the number of unique connected components that are directly connected to cell (i, j).

Can you come up with an O(row*col) algorithm to populate adj_cc_count?

Start a DFS from each unvisited green cell. Assign the same cc_id to each cell that you encounter. Every time you start a new DFS, increment the cc_id.

At the end of this process, you will have the total connected components, and also the info on which cell lies on which connected component. Using the cc_id, how to compute adj_cc_count[i][j]?

Insert the cc_id of each of the 4 neighbors in a set. The size of the set is the number of unique connected components that are adjacent to this cell.

Now, what happens when you turn this particular cell green? How would the number of connected components change?

This cell is the link that connects those unique connected components. Hence, we can forget about the old components and combine them into one. Hence, the new connected components would be

new_cc_count[i][j] = old_cc_count - adj_cc_count[i][j] + 1

Using this info, how do you compute the expected value?

Each red cell has an equal probability p of being picked. We already know the resulting connected components when a particular red cell is picked. Hence, the answer is

E = p*new_cc_count[i][j]

for each red cell. Since p is fixed, you can just sum up all these values and divide by p at the end. If modular divison sounds scary, use Atcoder Modint libray (See my code for implementation details).