This is one of 10 weekly problem sets. Each one is worth 10% of the grade of the "Submitted Implementation" evaluation criteria.
- Date of publication: 22/09/2026
- Date of delivery (deadline): 23h59m of 05/10/2026 (-4% for each extra day)
- Topics: Sublinear complexity data structures (map, set, priority_queue)
5 proposed problems:
- [Mooshak PC005] - Conformity
(tested in C++, Java and Python)
Hints
Use a map to store course combinations and then sum the frequency of all those with a maximum frequency.
What type should be a course combination? (careful with the order of the elements within the combination)
- [Mooshak PC006] - Playlist
(tested in C++, Java and Python)
Hints
Use a map to store the last position each element was seen and try to keep record of the largest sequence of unique songs ending on the current position ;)
- [Mooshak PC007] - Lemmings Battle
(tested in C++, Java and Python)
Hints
Simulate the battle using two (multi)sets/priority_queues
- [Mooshak PC008] - Traffic Lights
(tested in C++ and Java)
Hints
Initially there is a single segment withouth lights. Each time a traffic light is added, it will break an existing segment in two smaller ones. Can you keep track of all segments without lights?
- [Mooshak PC009] - Sliding Window Cost
(tested in C++ and Java)
Hints
How can we know the median as we traverse all the windows? Knowing the median can we compute the cost?
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 others 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).
- At the end of the semester you may have to present and dissuss any problem you submitted
Pedro Ribeiro - DCC/FCUP | Last update:
