https://www.codechef.com/SEPT18A/problems/STCFOTT
Please explain to me the third condition in the problem statement.
Each Selina only changes her direction (from bouncing to falling or vice versa) when she cannot keep moving in the current direction without leaving the tree or hitting another Selina, that is, when one of the following happens:
- reaching a leaf when falling
- reaching the root when bouncing
- meeting another Selina that's moving in the opposite direction
I understand that this is a problem for live contest and hence, I am not asking you to tell me the solution. I just would like to understand what it means.
Thanks
I'm sure it's like, if you have a Selina going from node u to a child v, you cannot have a Selina from that child v going up to node u (opposite direction). Also, if you have it going to the parent of u, then you can't have a Selina going from the parent of u down to u.
** if you have a Selina going from node u to a child v, you cannot have a Selina from that child v going up to node u (opposite direction)**
So what should happen in this case? the selina at node u which was going towards v, should it go to the parent of u or remain at u and same for selina at child v.
Also, what happens in the case of the two selinas going towards the node v from opposite directions. i.e., one selina from parent u to v & other from child w to v.
I had the same doubt. I asked it through the comment feature on the question page, but I am yet to get a response. :/
let me know if you get any response. Thanks
According to Teja349, in the case where one selina is going from u to v, other from v to u, they wouldn't make these moves. Instead they will change direction.
In the case where one selina is going from parent of u to u, and other selina from some child of u to u, both will change direction and will be at node u.
Also, initially all the m selinas are at root?
Yes, I believe each Selina starts from the root at the time given.
Suppose there are 3 nodes. 1 is parent of 2, and 2 is parent of 3. 1 is moving down and 3 is moving up currently. So how does 2 move now? Can any of the nodes move?
I think that there will be 2 selinas at node 2 moving in opposite directions and 1 at node in which the selina at 2 was moving to, according to what annesh told above.