Tubby and Tom – DE Shaw OA

From now onwards, Tubby = D and Tom = C. So D has to catch C and the first turn is of D. So, the very first thing is to create a tree from the given edge list. Here we create an adjacency list.

int min_time(int G_nodes, vector<int> G_from, vector<int> G_to
, int D, int C){

    vector<int> adj[G_nodes+1];
    for(int i=0;i<G_nodes-1;i++){
        adj[G_from[i]].push_back(G_to[i]);
        //Edges are undirected
        adj[G_to[i]].push_back(G_from[i]);
    }
}

Now, we will apply DFS and create distance_d and distance_c arrays which denotes the distance of ith node from initial position of D and C respectively. This means, now we know the time D and C will take to reach any particular node from it’s starting position.

void dfs(int node, int p, int depth, vector<int> adj[], int dist[]){
    dist[node] = depth;
    for(int i:adj[node]){
        if (i == p) continue;
        dfs(i,node,depth+1,adj,dist);
    }
}

int min_time(int G_nodes, vector<int> G_from, vector<int> G_to
, int D, int C){

    vector<int> adj[G_nodes+1];
    for(int i=0;i<G_nodes-1;i++){
        adj[G_from[i]].push_back(G_to[i]);
        //Edges are undirected
        adj[G_to[i]].push_back(G_from[i]);
    }

    int distance_d[G_nodes+1], distance_c[G_nodes+1];
    dfs(D,D,0,adj,distance_d);
    dfs(C,C,0,adj,distance_c);

}

If at a node, D reaches first, i.e., distance_d[node] <= distance_c[node]+1, than C will never go to such node (not optimal). Thus, when distance_d[node] > distance_c[node]+1, C can be pruned and the ans will be updated as ans = max(ans, distance_d[node] + distance_d[node] -1). Because when C is caught, it has made one step less than what D has made.

Note : Answer always exist, as tree does not contain cycles. For detail explanation, I will include a link to my youtube video below!

Complete Code :

void dfs(int node, int p, int depth, vector<int> adj[], int dist[]){
    dist[node] = depth;
    for(int i:adj[node]){
        if (i == p) continue;
        dfs(i,node,depth+1,adj,dist);
    }
}

int min_time(int G_nodes, vector<int> G_from, vector<int> G_to
, int D, int C){

    vector<int> adj[G_nodes+1];
    for(int i=0;i<G_nodes-1;i++){
        adj[G_from[i]].push_back(G_to[i]);
        //Edges are undirected
        adj[G_to[i]].push_back(G_from[i]);
    }

    int distance_d[G_nodes+1], distance_c[G_nodes+1];
    dfs(D,D,0,adj,distance_d);
    dfs(C,C,0,adj,distance_c);
    int ans = 1;
    for(int i=1;i<=G_nodes;i++){
        if (distance_d[i] > distance_c[i]+1){
            ans = max(ans, distance_d[i]*2 -1);
        }
    }
    return ans;
}