You are not logged in. Please login at www.codechef.com to post your questions!

×

STCFOTT - Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- DOlaBMOon
Tester- Teja Vardhan Reddy
Editorialist- Abhishek Pandey

DIFFICULTY:

MEDIUM-HARD

PRE-REQUISITES:

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.

QUICK-EXPLANATION:

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.

  • One of discussing the variables, collisions and the recurrences
  • Other for constructing the Matrix
  • Concluding notes, alternate approaches etc.

1.Collisions, Variables and Recurrences-

First lets talk about collisions. Take these few examples.

  • What happens if $1$ Selina is going down and collides with $1$ selina going up? Ans- Overall we see that still $1$ Selina goes up and other goes down. Since Selina's are indistinguishable, we dont care which goes up or which goes down.
  • 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.

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.

View Content

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", eg-Starting 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_{i-1}$, how will we find $X_i$? Simple!

$X_i=X_{i-1}+U_i+D_i$.

This means, we assign a $1$ at places of $X_{i-1}$, $A[i][U_i]$ and $A[i][D_i]$. My position for $X_{i-1}$ doesnt seem very clear. Why? Because it depends on where you put $X_{i-1}$ 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_{i-1}$ non-zero.

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 $Q-t[i]+1$

One optimization we can use in matrix exponentiation part is to, pre-calculate powers of $A^{2^k}$ instead of calculating them again and again for each selina. Hence, tester used a $3-D$ 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!

SOLUTION

Setter

Tester

View Content

Editorialist

$Time$ $Complexity=O(M\times N^2\times logQ)$
$Space$ $Complexity=O(M+N^3LogN)$

CHEF VIJJU'S CORNER :D

1. 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 $1-2$ rows to calculate next row!)

2. Hall of Fame for Noteworthy Solutions-

3. Setter's Notes

View Content

4. Tester's notes on collision-

View Content
This question is marked "community wiki".

asked 19 Sep, 18:28

vijju123's gravatar image

5★vijju123 ♦
14.9k11856
accept rate: 18%

edited 19 Sep, 22:03


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.

link

answered 19 Sep, 20:14

adhyyan1252's gravatar image

5★adhyyan1252
1125
accept rate: 11%

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, 20:29) vijju123 ♦5★
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, 20:55) adhyyan12525★

Yes, we accept that thing. The statement could have been a lot better.

(19 Sep, 21:14) vijju123 ♦5★

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, 21:57) aryanc4036★
1

understanding the statement is actually harder than solving it :P

(19 Sep, 22:07) adhyyan12525★

But the reverse is true in my case. I understood that Collision is of no use. but still got 0 pts.

(22 Sep, 10:34) aryanc4036★
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:
1. Why an astounding 20 sec time limit?
2. Was it intended for simulation solutions to pass? I'm guessing yes because of the time limit, but why so?

link

answered 19 Sep, 20:30

meooow's gravatar image

6★meooow ♦
6.9k717
accept rate: 48%

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, 20:40) vijju123 ♦5★
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, 20:50) meooow ♦6★

Nice problem!

Should the time complexity be more like O(N^3*log(Q) + M*N^2*log(Q)) = O((N+M)*N^2*log(Q)), where the first term is for calculating 2^k powers of the matrix? Of course when M = N, this is the same as O(M*N^2*log(Q)). For the space complexity, there are log(Q) matrices, so it should be dominated by N^2*log(Q).

There is a small optimization possible in matrix multiplication: since the matrix has a unit block in the top left corner and zero block in the bottom right corner, there is no need to multiply the full matrix:

(I  B)   (I  B)   (I  B+B*C)
(0  C) x (0  C) = (0   C*C )

And finally my two cents on the condition "meeting another Selina that's moving in the opposite direction" that intended to obfuscate the straightforward approach. In the case when two Selinas are moving down and one moving up the natural interpretation is that each of Selinas moving down meets a Selina moving in opposite direction and thus changes the direction (even though they meet the same Selina). The third Selina, moving up, also changes the direction.

Selinas are not billiard balls. They can change their momentum using muscle power :).

link

answered 22 Sep, 10:17

shoom's gravatar image

5★shoom
372
accept rate: 14%

Selinas are not billiard balls. They can change their momentum using muscle power :).

Selina , means some attractive and awesome person (of opposite gender) which you meet. And look what setter did, Selinas moving colliding (and what not!) like marbles. Say this to him coz he was the one treating them like billiard balls XD

(22 Sep, 11:57) vijju123 ♦5★

Wow!! never seen such a misleading problem statement!!

link

answered 08 Nov, 00:37

chinmay0906's gravatar image

6★chinmay0906
814
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,188
×260
×232
×112
×50

question asked: 19 Sep, 18:28

question was seen: 538 times

last updated: 08 Nov, 00:37