PROBLEM LINK:Setter DOlaBMOon DIFFICULTY:MEDIUMHARD PREREQUISITES:Matrix Exponentiation, Recurrences, Finding Inverses. Some people solved it via simulation as well. PROBLEM:Given there are $M$ Selinas walking in a tree of $N$ nodes, going either up or down until a collision with other selina/root/leaf, we need to find, for all nodes, sum of expected number of Selina which passed through that node so far. QUICKEXPLANATION:Key to AC Collisions do not matter. We can find the answer for each Selina individually and add it to final answer. Lets first see how we can find relations or recurrences. One of the ways to decompose it into a system of linear equations is, for every (internal) node, have $2$ variables, one for when Selina at the node is going down to its children, and other when its going up. (Root and leaves will only have $1$ variable). Now, we know that "Expected" Selina coming down to this children from its parent = $\frac{1}{K} *$ Expected Selina coming down at its parent. "Expected" Selina going up to parent of current node= Expected Selina going up at current node. Use this to construct the matrix and we are done with the question. EXPLANATION:The editorial will be divided roughly into $3$ sections.
1.Collisions, Variables and Recurrences First lets talk about collisions. Take these few examples.
Notice that, if we dont care about which Selina is going up or not, the final result is just as if the Selina's pass through each other without collisions. This is the basic intuition that collisions are useless, we can calculate the answer for each selina individually. Hence, lets not try to find answer considering only $1$ selina in the tree, and later on sum the Now lets see what can be our recurrence. Suppose we know the expected number of selinas for all nodes at time $t$. How can we find for time $t+1$? Remember that we have separate states for direction. In formal words, knowing $dp[i][direction][time]$ can we find $dp[i][direction][time+1]$? The answer is given in tab in case you want to work it out first. Dont worry about corner cases right now, find the general recurrence. Now, from above we have found out the recurrence. The only case is that, root and leaves will have only $1$ direction, either $up$ or $down$. Now, lets make it easier for us to frame a solution in Matrix exponentiation. It will be better if we define "Going up at node $i$" and "Going Down from node $i$" as separate variables. Let me call $D_i$ as "going down from node $i$" and define $U_i$ on similar grounds. What many people did is, they mapped the variables to "numbers", egStarting from $1$ or $0$, assign $U_i=i$ and $D_i=(i+1)$ to going up and down from a node, then move to next node and do the same. For leaves and root assign only a single variable, i.e. $U_i=D_i=i$. While not necessary, it makes understanding the next part easier. The reason was that, we can use this mapped number as index of variable in matrix. Lets get to this in next part! Construction of Matrix Now, we have roughly $\approx 2n$ variables. But wait, theres a problem! Matrix exponentiation usually gives us the $N'th$ term of the series, but what we need is the sum upto $N'th$ term! This will be solved later by adding extra $N$ variables ($X_i$), $1$ for each node, where these variables will store $X_i=\sum U_i+\sum D_i$. Basically $X_i$ stores the sum of expected values till now for node $i$. First, lets find how to construct our usual matrix to find $N'th$ term, and then what changes we need to do in it to get the sum. Refer to the recurrences we made till now. Define matrix $A[i][j]$ as "coming at variable $i$ from variable $j$" where variable $i$ can be $U_i$ or $D_i$ and $j$ can be downwards from parent $(D_{par[i]})$ or upwards from child $(U_{child[i]})$ etc. depending on what exactly is $i$. Now, you might have to do a lot of visualization in below steps. But if we mapped variables, then that makes our life easier. First, define what does your previous case (with which you multiple the matrix to get next term's values) represent. Lets take it $[U_1,D_1, U_2, D_2, U_3.....]$ for now. Now, for case of going from parent to child $dp[i][down][time+1]=\frac{1}{K}dp[parent[i]][down][time]$. We have $dp[parent[i]][down][time]$ in our base case, so we simply store $K^{1}$ at $A[D_i][D_{parent[i]}]$ where $K$ is number of children of $parent[i]$. This was all we needed to find next term of this recurrence. What about leaves? What direction will we assign to selina at leaf? Bouncing upwards or going downwards? Note that we assigned $U_i=D_i=i$ for leaf and root, so we can use either of them as per our convenience. For next case? For this case, expand the summation $dp[i][up][time+1]=\sum dp[child[i]][up][time]=1*dp[C_{i1}][up][time]+1*dp[C_{i2}][up][time]...$ where $C_{ij}$ represents $j'th$ child of node $i$. We have all of these in our base case, so we simply assign a $1$ at all valid palces. These valid places are nothing but $A[U_i][U_{C_{ij}}]$. We made the matrix! Now only $1$ thing is left, incorporating sum. For this, we add $N$ extra variables to base case $X_1,X_2,...,X_n$ where $X_i=\sum U_i+\sum D_i$. Now, if we know $X_{i1}$, how will we find $X_i$? Simple! $X_i=X_{i1}+U_i+D_i$. This means, we assign a $1$ at places of $X_{i1}$, $A[i][U_i]$ and $A[i][D_i]$. My position for $X_{i1}$ doesnt seem very clear. Why? Because it depends on where you put $X_{i1}$ in your base case. The tester formed a base case of $[X_1,X_2,....X_n,U_1,D_1,....,D_n]$, so for him index $A[i][i]$ corresponded to the position of $X_i$. Note that when I say "position of $X_i$", I mean that position of $i'th$ row which must be made $1$ to make contribution of $X_{i1}$ nonzero. You might have to make use of some paper, the part above is hard to visualize, but that is the only crux in this question, after this its all standard algorithms. Feel free to ask doubts. Concluding Notes What is now left to do is, for each selina, find the contribution. We can say that the contributionis $A^{time}*B$ where $B$ is base case, (Only $1$ selina at root at $t=0$, everything else is $0$. Might vary depending on your definition of matrix.) $time$ is nothing but the time for which this selina contributed, which is $Qt[i]+1$ One optimization we can use in matrix exponentiation part is to, precalculate powers of $A^{2^k}$ instead of calculating them again and again for each selina. Hence, tester used a $3D$ matrix $A[k][i][j]$ where $k$ represents that this matrix is $A^{2^k}$ of the matrix $A$ we described above. Once its done, we are all good to go with the question. All thats left is multiplying the matrix to get the answer. Dont forget to use long longs or take mods! SOLUTIONSetter Editorialist $Time$ $Complexity=O(M\times N^2\times logQ)$ CHEF VIJJU'S CORNER :D1. Go through our recurrence again. Why can we not use it to directly find the answer? Is it memory limit? Can you get a way to overcome that? (Hint: We only need last $12$ rows to calculate next row!) 2. Hall of Fame for Noteworthy Solutions
3. Setter's Notes 4. Tester's notes on collision
This question is marked "community wiki".
asked 19 Sep '18, 18:28

What if 2 Selinas are going down and collide with 1 Selina going up? Still 2 Selina's will go down and 1 would go up. Why is this the case. I would think that after the collisions 2 selinas will go up and 1 will go down. answered 19 Sep '18, 20:14
The reason is conservation of momentum, and that no selina can stop. Its a little difficult to explain since my physics aint that strong either, and there are multiple cases like, what if collisions are inelastic and selinas stick etc. Assuming elastic collision, for conservation of momentum it should follow that $2$ selinas go down and $1$ go up. I will upload tester's note on this.
(19 Sep '18, 20:29)
3
I definitely didnt expect physics to be used in this question, specially when nothing was mentioned in the statement about it. Very vague statement where a lot of assumptions have to be made.
(19 Sep '18, 20:55)
Yes, we accept that thing. The statement could have been a lot better.
(19 Sep '18, 21:14)
Coming back to the collision 2 Selinas are going down and collide with 1 Selina going up. I feel that answer is Still 2 Selina's will go down and 1 would go up. Reason after one collision if 2 are going up then they do have a collision again after 3rd is detached so by going through this logic. After this collision one more will go down. xD
(19 Sep '18, 21:57)
1
understanding the statement is actually harder than solving it :P
(19 Sep '18, 22:07)
But the reverse is true in my case. I understood that
(22 Sep '18, 10:34)
showing 5 of 6
show all

Nice problem. A matrix exponentiation solution has not occurred to me, I solved it using probably what you are calling simulation. However, the problem statement is very unclear about collisions on the tree. It was reported here, and I am sure there were plenty of comments too. I also have two questions: answered 19 Sep '18, 20:30
The thing was, setter's solution took $\approx 15$ seconds to pass if I recall correctly, and he used matrix expo which could work for $Q$ upto $10^{18}$. But sadly he did not set constraints to that which caused this imbalanced. Simulations were not supposed to pass for $Q$ upto $10^{18}$, and hence in intended version of problem.
(19 Sep '18, 20:40)
1
Even for $Q = 10^9$ simulation solutions would fail. Still, nice problem and I will attempt to solve it using matrix expo :)
(19 Sep '18, 20:50)

Wow!! never seen such a misleading problem statement!! answered 08 Nov '18, 00:37
