zeref_dragoneel's blog

Understanding of a live problem

By zeref_dragoneel, history, 6 years ago, In English

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:

  1. reaching a leaf when falling
  2. reaching the root when bouncing
  3. 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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ** 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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I had the same doubt. I asked it through the comment feature on the question page, but I am yet to get a response. :/

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    let me know if you get any response. Thanks

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply