Exploration Plan

Source: Codeforces 852D

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.
2. In this problem, we might care about distances from any of the starting cities to any of the other cities (or each other).
   • What information could be useful to answer such queries?
   • Can we precompute this information within the time limit? How?

The problem asks us to find the shortest time in which the teams can reach K different cities. There’s no obvious way to optimise for time directly. However, this problem features a familiar problem-solving paradigm.

3. How does the number of reachable cities vary with the time allowed?
   • If we can reach at most K cities in time t, could we do better in less time?
4. Design a criterion to test whether K cities can be reached in a given time t.
   • Which cities are reachable from which other cities? Construct graph edges accordingly.

5. Design an algorithm to solve the problem.

6. Analyse the time complexity of your algorithm and estimate its running time.

7. Implement this algorithm in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Write a program which solves the problem.
   • Run your tests and debug if necessary.
8. Submit your program for judging!
   • Debug as required.