Weekly Problems #07
	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: 18/11/2025
• Date of delivery (deadline): 23h59m of 08/12/2025 (-2% for each extra day)
• Topics: Dynamic Programming II (partitions, games, dags, counting, search)

6 proposed problems:

• [Mooshak PC032] - Car Rallying
  (tested in C++, Java and Python)
  Hints

  - This is in its essence a DAG
  
  - A DP state could simply be (current_position, current_velocity)

  
  
• [Mooshak PC033] - Football Teams
  (tested in C++, Java and Python)
  Hints

  - We need to use DP to count
  
  - A DP state needs to know where we are. What variables do we need to obey the restrictions of the problem?

  
  
• [Mooshak PC034] - Bridge Building
  (tested in C++, Java and Python)
  Hints

  - First use BFS or DFS to find out what cells belong to each bank
  
  - Then calculate for each column what would the bridge length be to connect north and south
  
  - At this point the problems becomes an almost "direct" partition DP problem :)
  
  - The DP state could be something like (column_last_bridge, number_bridges_left)

  
  
• [Mooshak PC035] - Chomp
  (tested in C++, Java and Python)
  Hints

  - This is DP on a game, right?
  
  - We can win if there is at least a move that goes to a losing position
  
  - We lose if all our moves go to losing positions
  
  - How can the board be represented in an efficient way to save both memory and runtime?

  
  
• [Mooshak PC036] - Rock-Me-Not
  (tested in C++, Java and Python)
  Hints

  - Bitmasks, anyone?

  
  
• [Mooshak PC037] - This is the way
  (tested in C++, Java and Python)
  Hints

  - Are you up for a digit DP? :)
  
  

  
  

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: