Soldier and Traveling

Source: Codeforces 546E

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.

Let’s try simple approaches.

2. Attempt to design a greedy algorithm to solve the problem.
   • Reflector:
     • Design a counterexample to the proposed algorithm.
3. Discuss why your algorithm was not correct.

What can we try when we want to correct mistakes in a greedy assignment?

4. Build a flow network to represent the cities, roads and soldiers.
   • Are the existing cities and roads sufficient? Why or why not?

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.