Editorial for VPEX P4 - Etopika


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Subtask 1

Calculate the distance between 2 nodes using BFS or DFS. Calculate the distance travelled for every order of visiting the nodes and find the minimum.

Key Concepts Required: Graph Theory, Brute Force

Time Complexity: \mathcal{O}(N \cdot 2^D)

Subtask 2

Precompute the distance between any two nodes by doing a DFS or BFS from each node.

If nodes a_1 and b_1 had bananas yesterday and nodes a_2 and b_2 had bananas today, you have four options today:

  • a_1 to a_2 to b_2
  • a_1 to b_2 to a_2
  • b_1 to a_2 to b_2
  • b_1 to b_2 to a_2

If dp[d][0] = distance travelled up to day d and ending on node a_2, and dp[d][1] ending on node b_2,

\displaystyle \begin{align*}
dp[d][0] &= \min(dp[d-1][0] + dist[a_{d-1}][b_d], dp[d-1][1] + dist[b_d-1][b_d]) + dist[b_d][a_d] \\
dp[d][1] &= \min(dp[d-1][0] + dist[a_{d-1}][a_d], dp[d-1][1] + dist[b_d-1][a_d]) + dist[a_d][b_d]
\end{align*}

And the answer is \min(dp[D][0], dp[D][1]).

Because the monkey starts at node 1, dp[1][0] = dist[0][a_1], dp[1][1] = dist[0][b_1].

Key Concepts Required: Graph Theory, Dynamic Programming

Time Complexity: \mathcal{O}(N^2 + D)

Subtask 3

This solution is similar to the solution to subtask 2. Instead of precomputing the distance between all pairs of nodes, we can find the distance between any two nodes by using their lowest common ancestor (LCA).

Key Concepts Required: Graph Theory, Dynamic Programming, Sparse Table

Time Complexity: \mathcal{O}(N + D)


Comments

There are no comments at the moment.