Weekly Problems #09
	Pedro Ribeiro - DCC/FCUP

This is one of 11 weekly problem sets. Each one is worth 10% of the grade of the "Submitted Implementation" evaluation criteria.

• Date of publication: 02/12/2025
• Date of delivery (deadline): 23h59m of 22/12/2025 (-2% for each extra day)
• Topics: Graphs II (distances: Dijkstra, Bellman-Ford, Floyd; MST: Prim+Kruskall; max flow)

6 proposed problems:

• [Mooshak PC044] - Number Maze
  (tested in C++, Java and Python)
  Hints

  - Use Dijkstra's algorithm to go from one corner to the other

  
  
• [Mooshak PC045] - Complicated Traffic
  (tested in C++, Java and Python)
  Hints

  - You can adapt Dijkstra for this problem
  
  - Can you think on the solution if K is zero? What is the correct relaxation of an edge?
  
  - You should consider K+1 states for each node (without any renovations made, with 1, with 2, ... , with K)

  
  
• [Mooshak PC046] - High Score
  (tested in C++, Java and Python)
  Hints

  - Can you think on how to use Bellman-Ford here?

  
  
• [Mooshak PC047] - Book Club
  (tested in C++, Java and Python)
  Hints

  - Maximum Bipartite Matching

  
  
• [CodeForces 160D] - Edges in MST
  (tested in C++ and Java)
  Hints

  - Can you think on how to adapt Kruskal algorithm for this task?

  
  
• [CodeForces 567E] - President and Roads
  (tested in C++ and Java)
  Hints

  - One for you to solve alone? :)

About the delivery:

• I will automatically catch your submissions from Codeforces (as well as in Mooshak).
• At the end of the semester you will need to send all your submitted code to me.
• You can chat and discuss the problems among yourselves, but you should do your own implementation (simply copying code from other or from an LLM is considered a severe break of the code of conduct).
• The final code submitted to should include comments with the temporal and spatial complexity, as well as a small explanation of your algorithmic idea. You should also refer any helps you got (including referencing any sources you have consulted).

Pedro Ribeiro - DCC/FCUP | Last update: