ritik_patel05's blog

AtCoder Beginner Contest 148, Problem F
By ritik_patel05, history, 5 years ago, In English

Problem : https://atcoder.jp/contests/abc148/tasks/abc148_f

How did you solved this problem? It would be better if you can give your intuition along with your approach.

Thank you.

  • Vote: I like it
  • +14
  • Vote: I do not like it

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

This might help a bit.

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Let A be Aoki's initial position and T be Takahashi's initial position.

We root the tree at A. Then for Takahashi, the optimal strategy will be running to some parent of T (we call that parent P, P can be just T), and then from there run to the furthest leaf in the subtree rooted in P.

The three phases are:

  1. Takahashi runs to P and Aoki just runs towards P as well
  2. Takahashi runs to the furthest leaf, Aoki chases (note this doesn't change the decrease the distance between both of them)
  3. Takahashi is now trapped at a leaf. The number of turns needed to end the game is (The distance between them - 1)

We should only consider all P in which Takahashi can reach P before Aoki can reach P.

We can find the distance to the furthest leaf for all nodes using dp on tree. Then for each P, the total time taken is:

(The time needed to travel to P) + (The distance to the furthest leaf) + (The distance between Takahashi and Aoki after Takahashi reaches P - 1).

We just take the maximum value for all valid P.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +7 Vote: I do not like it

    You can simplify it by observing that for each leaf k which Takahashi arrives earlier, that formula always reduces to (Distance between v and k) — 1. Since this value always has its maximum at a leaf, we can just write

    Max{ for any node k with dist[u to k] < dist[v to k] } ( dist[v to k] - 1 )

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

My solution

→ Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

You can solve this problem with dfs!

First make "Takahashi" as a root and write all vertices distance to root let call that disx[i](for vertex number i) and then make "Aoki" as a root and write all vertices distance to root let call that disy[i](for vertex number i) you should find:

maximum disy[i] such that disy[i] > disx[i] and the answer is (disy[i] — 1)

my solution

→ Reply