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: 04/11/2025
- Date of delivery (deadline): 23h59m of 24/11/2025 (-2% for each extra day)
- Topics: Dynamic Programming I (classic)
6 proposed problems:
- [Mooshak PC026] - Perfect Harmony
(tested in C++, Java and Python)
Hints
- Can you adapt the Longest Common Subsequence (LCS) DP formulation to this problem?
- [Mooshak PC027] - Mixtures
(tested in C++, Java and Python)
Hints
- Can you adapt the Matrix Chain Formulation (MCM) DP formulation to this problem?
- [Mooshak PC028] - Wavio Sequence
(tested in C++, Java and Python)
Hints
- Can you adapt the Longest Increasing Subsequence (LIS) DP formulation fo this problem?
- Be careful: you need an \(\mathcal{O}(n \log n)\) solution, as \(\mathcal{O}(n^2)\) is not enough...
- [Mooshak PC029] - String to Palindrome
(tested in C++, Java and Python)
Hints
- Can you adapt the Edit Distance DP formulation to this problem?
- [Mooshak PC030] - Making Change
(tested in C++, Java and Python)
Hints
- Can you adapt the Coin Change formulation to this problem?
- [Mooshak PC031] - Book Shop II
(tested in C++, Java and Python)
Hints
- Can you adapt the 0-1 knapsack formulation to this problem?
- How to tackle this bounded version? Can you avoid having to consider each copy of the same element as a "different" element?
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:
