Weights Distributing

Source: Codeforces 1343E

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

Let’s try the problem with a (over-)simplifying assumption.

2. Suppose the least cost path a → b → c is guaranteed to use each edge at most once. Which edges do we need to assign costs for, and how should we assign those costs?
   • Hint: think about the number of edges involved.

Let’s reconsider our assumption more carefully.

3. Is it possible for the least cost path a → b → c to repeat an edge?
   • The answer is yes. Construct a counterexample to the earlier assumption.
   • How can you decompose the structure of the path into disjoint parts?
     • Hint: can a vertex appear more than once?

4. For a particular case of the above structure, which edges do we need to assign costs for, and how should we assign these costs?

5. How many such cases are there? How long does the assignment of edge costs take? Is there a data structure that can improve upon the brute force approach?

6. Design an algorithm to solve the problem.

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

8. 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.
9. Submit your program for judging!
   • Debug as required.