PROBLEM LINK:Setter: Bogdan Ciobanu DIFFICULTY:MediumHard PREREQUISITES:Probability, Expectation, Dynamic Programming and Combinatorics. PROBLEM:Given a tree with $N$ nodes numbered through $1$ to $N$, each having a color, initially colored white. Find the expected number of steps the following process will last. In each step, choose an unordered pair $(a, b)$ of vertices at random, if there's any node colored black on the path between $a$ and $b$, terminate the process immediately. Otherwise, color all vertices on the path between $a$ and $b$ black and move to the next step. SUPER QUICK EXPLANATION
EXPLANATIONSo, Time for another combinatorics problem. First of all, If $X$ is a random variable, Expection is calculated as $1*P(X==1)+2*P(X==2)+3*P(X==3) \dots N*P(X==N)$. But, we can also rewrite it as $E(X) = P(X \geq 1)+P(X \geq 2) +P(X \geq 3) \dots +P(X \geq N)$. Now, see what $P(X \geq K)$ means. It means The number of ways to select at least K nonintersecting paths, in a given order. Now, since Order of selecting path is irrelevant as all paths do not intersect, We can write it as $K!*NumWays$ where $NumWays$ is the number of ways to select at least $K$ paths. Total number of possible paths selected (including intersecting ones) is $((N*(N+1)/2)^K$, Hence, $P(X \geq K) = NumWays*K!/(N*(N+1)/2)^K$. The problems get reduced to calculate NumWays, and for that, we resort to Dynamic Programming. First thing, We can have at most $sub[u]$ nonintersecting paths in the subtree of u, where $sub[u]$ is the number of nodes in the subtree of u. The reason is, that suppose, each path cover exactly one node. Even then, the number of Nonintersecting paths is $sub[u]$ and it can be seen, that we can only decrease Number of nonintersecting paths. Now, we will calculate for each node u, Number of Ways to select $X$ nodes for $1 \leq X \leq SZ[u]$. To calculate this, we also need information whether we can connect the current node with its parent in a path. There are two types of paths in the subtree of node u which include u.
See, that special type can also be extended toward the parent of u, thus, needs to be handled separately. Also note that the path of the second type may choose to end at the current node, hence, will always be included automatically in paths of type 1. Now, suppose we have it calculated for every child v of u, the number of ways to select at least $k$ paths in the subtree of v for $1 \leq k \leq sub[v]$. We need to compute the same for the current node. For computing this, we can use another DP for each node, call it dp2[childUsed][NumPaths][0/1/2] which calculate the number of ways we can select NumPaths in children of first childNodes children. The last state represents the number of special paths. We can assume Path of type 1 to be 2 special paths, to simplify our implementation. We can see, that in no case can a node have move than 2 special paths, since Any path is the shortest distance between two nodes, and such path cannot visit more than 2 subtrees of any node. Basically, we can fill the whole table using the recurrence. $dp2[child+1][mxPaths+curPaths][st1+st2] += dp2[childUsed][mxPaths][st1]*dp[child][curPaths][st2]$ if $st1+st2 \leq 2$ Let us try all combinations of $(st1, st2)$ for understanding.
Combination $(2,1)$ cannot be considered because we cannot have more than 2 special paths coming to a node. Also, For any child, only 1 special path can be extended to its parent. Because if there are two special paths which are extended to parent, it cannot be the part of any shortest path between two vertices. The reason is, that if two special paths are there, The only shortest path, the current node can be a part of, it the one starting somewhere in the subtree of one child of the current node and ending in a different child's subtree. Hence, Only above five combinations need to be considered. Now, we can see, that by the Fundamental principle of Counting, these are dependent events, and hence, are multiplied. This way, we will obtain, after computing internal DP, the number of ways to select $K$ paths out of all children of the current node such that the number of special paths up to children level is T ($T \in [0,2]$). Now, we need to consider cases as to update the original DP using the values of this internal DP. The thing is, that we cannot have two special paths extend toward its parent. So, we need to carefully count Number of ways to select paths for each count of special paths which can move forward. We can see, that we can choose not to extend any path, extend one path to parent as well as make a path at the current node. You need to handle these cases to get Required Number of ways for the current node. For implementation, please refer the tester's solution below. Related Problem A very recent problem Standard Tree Task from August CookOff which uses the precisely same type of Dynamic Programming, which you may refer here. Time ComplexityTime complexity is $O(N^2)$ per test. Seemingly, Each DFS takes $O(N^2)$ time, but due to Number of nodes being bound to $N$, Overall Time Complexity is amortized to $O(N^2)$. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 08 Nov '18, 16:50

in SUPER QUICK EXPLANATION your E[X] is false. answered 15 Nov '18, 22:30
