Editorial for Another Contest 2 Problem 1 - Poutine


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.

Let's start by solving the simplest possible case - when a trip must be done in 1 day.

In order to solve queries of this form, we're basically asking for the shortest path in the graph between those two vertices. With Floyd-Warshall, we can precompute answers for all of these queries in O(N^3).

How does this help us when the number of days a trip can take is larger than 1? For a 2-day trip between S and T, there must be some intermediate vertex X that we travel to in one day, and then we travel from X to V. For each of these intermediate trips, we can use the precomputed values from the Floyd-Warshall application earlier. In general, to figure out the optimal path from S to T in d days, for d > 1, we use an optimal path from S to X in d-1 days and then use an optimal path from X to T in one day.

Precomputing all of these values takes O(N^4) time, and we can then answer queries in O(1).


Comments

There are no comments at the moment.