TOMJERGA - Editorial

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Tester: Animesh Fatehpuria
Second Tester: Kevin Atienza
Editorialist: Pawel Kacprzak

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Trees, LCA

PROBLEM:

In this problem, for a given tree of N nodes the task is to handle Q queries. Each query consists of two vertices t and j denoting the initially positions of respectively Tom and Jerry in the tree. In one second, both Tom and Jerry can and have to change their current positions to one of the adjacent nodes to nodes they are currently in, and Jerry makes the move first, which is followed by Tom’s move. The answer for a single query is the minimum number of seconds Tom needs to catch Jerry, i.e. be in the same vertex as he is no matter how Jerry moves.

QUICK EXPLANATION:

For each query, find the middle of the path from t to j. Let’s call this node v. Then find the maximum distance from v to it’s subtree where j is also located. The final answer is the sum of this distance and the distance from t to v.

EXPLANATION:

Notice that if v is the node exactly in the middle of the path from t to j, then Tom can always prevent Jerry from crossing v by just moving greedily towards v. Thus the best Jerry can do is to find the longest path from $v$’s located in the same subtree of v that j is in. This observation is crucial and needed to came up with the solution. Exact solution and its time complexity depends on how does one implement these two parts, i.e. finding the middle vertex and the finding the longest path in one of its subtrees. Various approaches can be used to solve each subtask and they are described below. Last but not least thing to mention is that computing the middle vertex can be sometimes tricky, and when implementing it one should for example remember than in each turn Jerry makes his move first.

Subtask 1

In the first subtask we have bot N, Q \leq 100. This allows us to make a straightforward simulation of the whole process independently for each query. More specifically, for a single query, we can first find the middle vertex v by performing for example dfs from t and after finding it, compute the maximum distance from v into any vertex in v’s subtree where also j is located, which can be also done using dfs.

Subtask 2

In this subtask, in each query, node j is fixed. This allows us to precompute for all nodes u the middle node on path from j to u using a single dfs from j beforehand. Moreover, for each node u, the longest path from u descending into its subtree where j is also located can be computed similarly also beforehand. This allows us to answer each possible query offline using these precomputed informations.

Subtask 3

In this subtask, in each query, node t is fixed, so the problem is very similar to the one in the second subtask and the approach follows also the same idea, but has to be implemented independently of the solution for the second subtask, because slightly different informations have to be precomputed.

Subtask 4

In this subtask we know that N \leq 5000 and besides that all original constraints are preserved. At least a few possible approaches can take advantage of this fact and one of them is to first compute middle nodes for all possible pairs of nodes t and j, which can be computed for example by using dfs from each possible node t in order to compute middle nodes from t to all other nodes, and then use dynamic programming to compute dp[v][u] as the length of the longest path starting from v and descending into subtree of v where u is located. Then, all queries can be answered offline by using both these look-up tables to locate the middle node first, and then computing longest paths from this middle node descending into subtree where j is located. The total time complexity of this method is (N^2 + Q) for a single test case.

Subtask 5

In the last subtask, we can have up to 10^5 nodes and queries, which makes the problem significantly harder than it is in any of the earlier subtasks. However, remember that the same general rule for solving the problem applies, and it just has to be implemented more efficiently. Just to recall, the strategy is to solve each query (t, j) independently, by first finding the middle node v in the path from t to j and then compute the most distant node from v located in the same subtree of v that j is located in.

The first part, finding the middle node, can be solved using [LCA][22222] algorithm. The idea is that finding L = LCA(t, j) allows us to find the length of the path between t and j, which can be used to find the middle node when it’s combine with the function getKthAncestor(u,k) returning the k-th ancestor of u. This function can be implemented using, so-called jumps table which is also used to compute LCA of two nodes. For implementation details please refer to setter and both testers solutions listed below, or this [TopCoder article on how to compute LCA efficiently][11111].

The second part, i.e. the maximum distance from v to any node located in the same subtree of v that j is also located can be computed in a several ways. One possibility is to use to precompute for each edge (v, u) in the tree, the maximum distance from v to its subtree rooted in u. This can be easily done by running dfs with memoization. Notice that there are at most 2 \cdot N possible edges, resulting in the same number of entries in a look-up table they produce. This look-up table can be used to compute the final result as soon as the middle node is found. Exactly this approach was used by one of the testers for the problem. For other implementations you please refer to setter and second tester solutions listed below.

In summary, a single test case for this subtask can be solved in O(N \cdot \log(N) + Q \cdot \log(N)) time, and it is dominated by the time needed to compute LCA.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution can be found here.
Tester’s solution can be found here.
Second Tester’s solution can be found here.

[11111]: https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Another%20easy%20solution%20in%20O(N%20logN,%20O(logN)
[22222]: https://en.wikipedia.org/wiki/Lowest_common_ancestor

3 Likes

its not necessarily true that the optimum node where both meet is in the same subtree as j right? isnt it possible that there exists another subtree where the path will be longer?

4 Likes

While that’s possible there’s another subtree where the path will be longer, Tom will intercept Jerry on the way to that path, so Jerry won’t be able to cross the full path.

Nice Editorial!!Well Explained.Thanks :slight_smile:

What do you mean here by “being in the same subtree as j”? If we consider v to be the middle node in the path from t to j, then it’s clear that Jerry cannot get closer to t than v right? So the best he can do is to run the furthest from v in the same subtree of v he started the game.

Can the answer be in the subtree of some ancestor of v?

Great editorial and well commented, easy to read codes.

1 Like

Exactly, even i am slightly confused by your notion on subtree. Consider this case n=8 and the edges are
1 2,
2 4,
1 3,
1 5,
5 6,
6 7,
7 8.
tom starts at 4 and jerry starts at 3. the optimum node where they meet is 8 which is not in the subtree of J.

1 Like

@bhargav104 to eliminate confusion let u and v be adjacent vertices such that tom comes till u and jerry comes till v. They both come as close as possible and here distance between them is 1. Now jerry starts running from v towards the farthest node that is “not in the subtree of u” if we assume we make v a root.
Like in your example u = 2 and v = 1. Now jerry will start from node 1 in every direction other than node 2 because tom is sitting there. So here optimal would be jerry goes from node 1 to 8 which is farthest and not in the subtree of 2.

@author, can you please add some diagrams to make the editorial more understandable?

So, Gerry can run in any direction other than where tom is in and the distance should be maximum. Can you give any idea how to implement this. I’m not understanding the editorial

Sure, first it is quite intuitive to think that tom will always run towards jerry. Now Jerry instead of just sitting there will also move towards tom. Now there will be a moment when tom is at u and jerry at v such that u,v are adjacent. Now Jerry will run as far from tom. We are doing this because when Jerry goes till tom he will increase the number of vertices he can go to now.
Now we divide problem in 2 parts
a) Finding the u,v as described above i.e mid point of their positions.
b) The max distance jerry can go from v in all directions except u.
My code: https://paste.ubuntu.com/23549424/