Weekly Problems #04
	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: 07/10/2025
• Date of delivery (deadline): 23h59m of 03/11/2025 (-2% for each extra day)
• Topics: Sqrt decomposition, segment trees and variants

6 proposed problems:

• [Mooshak PC015] - The Strongest Warriors
  (tested in C++ and Java)
  Hints

  - This is an almost direct problem that you can solve with static segment trees or sqrt decomposition
  
  - You just need to take care to save on each range both the maximum and its number of occurrences
  
  - Merging two ranges is easy, right?

  
  
• [Mooshak PC016] - Frequent Values
  (tested in C++ and Java)
  Hints

  - Dynamic range queries with less standard "merge" operation
  
  - What values do you need to store to make the merge of two ranges?

  
  
• [Mooshak PC017] - Hotel Queries
  (tested in C++ and Java)
  Hints

  - How to quickly find the hotel to put the next group of tourists?
  
  - Can you binary search the answer, combined with range querying?

  
  
• [Mooshak PC018] - K-Query
  (tested in C++ and Java)
  Hints

  Can you think on how to take advantage of offline range querying?

  
  
• [Mooshak PC019] - Census
  (tested in C++ and Java)
  Hints

  - Your chance to implement direct 2D dynamic range queries
  
  - Can you make a 2D segment tree with a seg tree inside a seg tree? 🙃

  
  
• [Mooshak PC020] - Light Switching
  (tested in C++ and Java)
  Hints

  - Use a segment tree + range updates with lazy propagation

  
  

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: