Weekly Problems #08
	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: 25/11/2025
• Date of delivery (deadline): 23h59m of 15/12/2025 (-2% for each extra day)
• Topics: Graphs I (DFS, BFS, topological sorting, articulation points, bridges, euler paths, ssc)

6 proposed problems:

• [Mooshak PC038] - Rank the Languages
  (tested in C++, Java and Python)
  Hints

  - Do a flood fill to find connected components of letters
  
  - Sort according to the given criteria

  
  
• [Mooshak PC039] - Rare Order
  (tested in C++, Java and Python)
  Hints

  - Build a graph where nodes are letters and edges represent that you know a letter should appear before another one
  
  - Your desired order corresponds to a topological sorting, that is guaranteed to exist and be unique

  
  
• [Mooshak PC040] - Ash Cloud
  (tested in C++, Java and Python)
  Hints

  - Do a BFS with multiple sources (e.g. from all clouds)

  
  
• [Mooshak PC041] - Magic Squares
  (tested in C++, Java and Python)
  Hints

  - This is DP on a game, right?
  
  - BFS on an implicit graph where a state is a possible board position

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

  - Can you build/navigate a graph based on the input? - After having the graph, the problem becomes easy, right?

  
  
• [Mooshak PC043] - Coin Collector
  (tested in C++, Java and Python)
  Hints

  - Build a DAG where each node is ons strongly connected component of the original graph
  
  - Apply DP to the DAG

  
  

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: