PROBLEM LINK:Author: Jakub Safin DIFFICULTY:MediumHard PREREQUISITES:BFS, DFS, Probability, Expected value PROBLEM:Given a $R\times C$ maze where each cell is either empty (colored white) or blocked (colored black), you can click on any white cell. Whenever you click on a white cell, it turns red and all cells reachable from it also turn red. The process is repeated until there is a redcolored connected path from start $(0, 0)$ to end $(R1, C1)$, when the game ends. You are required to find the expected number of clicks to finish the game. EXPLANATION:The first thing to notice is that given a set of connected white cells, clicking on any of them turns all these cells to red. Hence, we first need to group the cells into connected components. This can be achieved by using a DFS  Depth first search (or) BFS  Breadth first search. It is given that there is at least one connected path of white cells from start $(0, 0)$ to end $(R1, C1)$. It is easy to note that after breaking the white cells into groups of connected components, there is exactly one component which contains both start and end cells. One more thing to note is that we are only interested in the number of cells in each component, since clicking on any cell in a component turns all cells in that component to red. Let us assume that there are $(n+1)$ connected components with sizes $x_{0}, x_{1}, ..., x_{n}$, where $(n >= 0)$. Let $x_{0}$ be the component which contains both the start and end cells. The game ends when we click on any of these $x_{0}$ cells.
For this subtask, $R\cdot C <= 30$. It is easy to observe that the maximum number of connected components is utmost $(R\cdot C) / 2 = 15$. In fact, it is lower than $15$ since we haven't accounted for the existence of a path from start to end. But $15$ is a good enough bound for us to be able to come up with a solution. We can use a bit mask to denote which components have already been visited. At every step, try to click on any cell of any unclicked component. We can try every possible unclicked component in every step. The game ends when we choose to click on any of the $x_{0}$ cells (component containing the start and end cells). Pseudo code: // There are (n+1) components totally => x0, x1, ... xn for (i = 0 to 2^(n+1)1) { dp[mask] = 1 } double E(mask) { if (dp[mask] > 0) return dp[mask]; sum = 0, ans = 0; for (i = 0 to n) { if ((1<<i) & mask) continue; sum += x[i]; } for (i = 0 to n) { if ((1<<i) & mask) continue; if (i == 0) ans += (x[i] / sum) * (1); else ans += (x[i] / sum) * (1 + E(mask ^ (1<<i))); } return dp[mask] = ans; } In the above code, calling $$E(10010) = \left(\frac{x_{0}}{x_{0} + x_{2} + x_{3}}\right) \cdot (1) + \left(\frac{x_{2}}{x_{0} + x_{2} + x_{3}}\right) \cdot (1 + E(10110)) + \left(\frac{x_{3}}{x_{0} + x_{2} + x_{3}}\right) \cdot (1 + E(11010))$$ This gives us an $\mathcal{O}(n \cdot 2^n)$ solution, where $n = \frac{R\cdot C}{2}$. This is enough to pass the first subtask.
For this subtask, $R\cdot C <= 50000$, The bit mask method used for subtask 1 is way too inefficient for this. We need to do something much smarter. Continuing from where we left in the previous subtask, let's define $E_{n}(x[0..n])$ as the expected number of clicks to finish the game when there are $(n+1)$ components of sizes $x_{0}, x_{1}, ..., x_{n}$. Let us also define $E_{n1}(x[0..n]\setminus x[i])$ to be the same as above, but containing only $n$ components, with the component $x_{i}$ removed. We can write the expected value as: $$\begin{align}E_{n}(x[0..n]) &= \frac{x_{0}}{\sum_{j=0}^{n} x_{j}} + \sum_{i=1}^{n} \frac{x_{i}}{\sum_{j=0}^{n} x_{j}} \cdot (1 + E_{n1}(x[0..n]\setminus x[i])) \\ & = 1 + \sum_{i=1}^{n} \frac{x_{i}}{\sum_{j=0}^{n} x_{j}} \cdot E_{n1}(x[0..n]\setminus x[i]) \end{align}$$ This indicates that the expected value should have some closed form. Let's try to find the expected values for small values of $n$. It is obvious that $E_{0} = 1$. $$E_{1}(x[0..1]) = 1 + \left(\frac{x_{1}}{x_{0}+x_{1}}\right) \cdot E_{0} = 1 + \left(\frac{x_{1}}{x_{0}+x_{1}}\right)$$ $$\begin{align} E_{2}(x[0..2]) &= 1 + \left(\frac{x_{1}}{x_{0}+x_{1}+x_{2}}\right) E_{1}(x[0..2]\setminus x[1]) + \left(\frac{x_{2}}{x_{0}+x_{1}+x_{2}}\right) E_{1}(x[0..2]\setminus x[2]) \\ & = 1 + \left(\frac{1}{x_{0}+x_{1}+x_{2}}\right) (x_{1} \cdot E_{1}(x[0..2]\setminus x[1]) + x_{2} \cdot E_{1}(x[0..2]\setminus x[2])) \\ & = 1 + \left(\frac{1}{x_{0}+x_{1}+x_{2}}\right) \left(x_{1} \left(1 + \left(\frac{x_{2}}{x_{0}+x_{2}}\right)\right) + x_{2} \left(1 + \left(\frac{x_{1}}{x_{0}+x_{1}}\right)\right) \right)\\ & = 1 + \left(\frac{x_{1}}{x_{0}+x_{1}}\right) + \left(\frac{x_{2}}{x_{0}+x_{2}}\right) \end{align} $$ You can use a pen and paper to do the above simplification and see that it is straight forward to get to the above derivation. Looking at the pattern, you might be tempted to generalize the following: $$ E_{n}(x[0..n]) = 1 + \sum_{i=1}^{n} \left(\frac{x_{i}}{x_{0}+x_{i}}\right) $$ Turns out that this is indeed the solution to the problem. :) However, we still need to prove this. Let us try to prove this by induction. Let us assume the following: $$ E_{i}(x[0..i]) = 1 + \sum_{j=1}^{i} \left(\frac{x_{j}}{x_{0}+x_{j}}\right) \\ \text{Hence, } E_{i1}(x[0..i]\setminus x[k]) = 1 \left(\frac{x_{k}}{x_{0}+x_{k}}\right) + \sum_{j=1}^{i} \left(\frac{x_{j}}{x_{0}+x_{j}}\right), (1<= k <=i) $$ We can write $E_{i+1}$ as follows: $$\begin{align}E_{i+1}(x[0..i+1]) &= 1 + \sum_{j=1}^{i+1} \frac{x_{j}}{\sum_{k=0}^{i+1} x_{k}} \cdot E_{i1}(x[0..i]\setminus x[j]) \\ & = 1 + \sum_{j=1}^{i+1} \frac{x_{j}}{\sum_{k=0}^{i+1} x_{k}} \cdot \left(1 \left(\frac{x_{j}}{x_{0}+x_{j}}\right) + \sum_{m=1}^{i+1} \left(\frac{x_{m}}{x_{0}+x_{m}}\right)\right) \\ & = 1 + \frac{1}{\sum_{k=0}^{i+1} x_{k}} \cdot \sum_{j=1}^{i+1} \left(\frac{x_{0} \cdot x_{j}}{x_{0}+x_{j}} + \sum_{m=1}^{i+1} \left(\frac{x_{m} \cdot x_{j}}{x_{0}+x_{m}}\right)\right) \\ & = 1 + \frac{1}{\sum_{k=0}^{i+1} x_{k}} \cdot \sum_{j=1}^{i+1} \left(\frac{x_{0} \cdot x_{j}}{x_{0}+x_{j}}\right) + \frac{1}{\sum_{k=0}^{i+1} x_{k}} \cdot \sum_{j=1}^{i+1} \sum_{m=1}^{i+1} \left(\frac{x_{m} \cdot x_{j}}{x_{0}+x_{m}}\right) \end{align}$$ In the last double summation, note that the order of summation doesn't matter. Hence, we can write the above equation as follows: $$\begin{align}E_{i+1}(x[0..i+1]) &= 1 + \frac{1}{\sum_{k=0}^{i+1} x_{k}} \cdot \sum_{j=1}^{i+1} \left(\frac{x_{0} \cdot x_{j}}{x_{0}+x_{j}}\right) + \frac{1}{\sum_{k=0}^{i+1} x_{k}} \cdot \sum_{m=1}^{i+1} \left(\frac{x_{m} \cdot \sum_{j=1}^{i+1} x_{j}}{x_{0}+x_{m}}\right) \\ & = 1 + \frac{1}{\sum_{k=0}^{i+1} x_{k}} \cdot \sum_{j=1}^{i+1} \left(\frac{x_{0} \cdot x_{j}}{x_{0}+x_{j}}\right) + \frac{1}{\sum_{k=0}^{i+1} x_{k}} \cdot \sum_{m=1}^{i+1} \left(\frac{x_{m} \cdot \sum_{j=0}^{i+1} x_{j}  x_{m}\cdot x_{0}}{x_{0}+x_{m}}\right) \\ & = 1 + \frac{1}{\sum_{k=0}^{i+1} x_{k}} \cdot \sum_{j=1}^{i+1} \left(\frac{x_{0} \cdot x_{j}}{x_{0}+x_{j}}\right) + \sum_{m=1}^{i+1} \left(\frac{x_{m}}{x_{0}+x_{m}}\right)  \frac{1}{\sum_{k=0}^{i+1} x_{k}} \cdot \sum_{m=1}^{i+1} \left(\frac{x_{0} \cdot x_{m}}{x_{0}+x_{m}}\right) \\ & = 1 + \sum_{m=1}^{i+1} \left(\frac{x_{m}}{x_{0}+x_{m}}\right) \end{align}$$ Hence, we have proved the above formula by induction. The time complexity to perform the BFS/DFS is $\mathcal{O}(R\cdot C)$ and the expected value can be found in linear time in the number of components. We already showed above that $\frac{R\cdot C}{2}$ is a loose upper bound for the maximum number of components. Hence, the problem can be solved in $\mathcal{O}(R\cdot C)$ time. COMPLEXITY:$\mathcal{O}(R\cdot C)$ per test case. SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 03 Sep '15, 19:29

By the way, did someone try filling the given maze? If you didn't, you should. answered 14 Sep '15, 15:24

Isn't the formaula for E(10010) would be this ?? Why Additional 1s are there in Original formula given above E(10010)=(x0/x0+x2+x3)⋅(1)+(x2/x0+x2+x3)⋅E(10110)+(x3/x0+x2+x3)⋅E(11010) answered 17 Sep '15, 15:46

For the first subtask, for every component, we can either choose than component or leave it. But we have to select the component containing the starting and ending point and apart from that component, we can choose the other components in any order, so I multiplied the value with the factorial of the number of components chosen, not including that component. Can someone help me figure out what is wrong with the logic or the implementation since I got WA. answered 14 Sep '15, 15:21
@additya1998 be very careful, as you aren't accounting for the number of cells in each connected component! Now if each connected component has exactly 1 element, then using factorials to count the total number of possible click orderings would work for the first subtask, but this isn't necessarily the case :/
(14 Sep '15, 15:24)
@Amlesh I am storing the number of cells in each component. Can you provide any case where my solution won't work?
(14 Sep '15, 15:27)

can any1 tell me in which case i am failing https://www.codechef.com/viewsolution/8170945 answered 15 Sep '15, 02:52

@amit2602 : Your solution fails the test case
answered 16 Sep '15, 15:27
