Weekly Problems #01
	Pedro Ribeiro - DCC/FCUP

This is one of 10 weekly problem sets. Each one is worth 12% of the grade of the "Submitted Implementation" evaluation criteria.

• Date of publication: 01/10/2024
• Date of delivery (deadline): 23h59m of 21/10/2024 (-2% for each extra day)
• Topics: sublinear complexity data structures (map, set, priority_queue)

6 proposed problems:

• [Mooshak PC002] - Cool Sequences
  Hints

  Use a map to associate each value to its frequency. At the end, knowing that a certain value x has frequency f_x, what is the minimum number of removals we need to do to make it part of a cool sequence?

  
  
• [UVA 11286] - Conformity
  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)

  
  
• [CSES 1141] - Playlist | also available as [Mooshak PC003] - Playlist (to allow a less strict time limit for Java)
  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 ;)

  
  
• [UVA 978] - Lemmings Battle
  Hints

  Simulate the battle using two (multi)sets/priority_queues

  
  
• [CSES 1163] - Traffic Lights | also available as [Mooshak PC004] - Traffic Lights (to allow a less strict time limit for 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?

  
  
• [CSES 1077] - Sliding Window Cost | also available as [Mooshak PC005] - Sliding Window Cost (to allow a less strict time limit for 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 Virtual Judge, which is the "official" submission method counting towards evaluation
  (I will however also try to catch submissions on UVA and CodeForces for listing purposes, but not on SPOJ and CSES, which do not have an API for extracting submissions).
• You should put your submitted code on your shared folder (I will send you an invite for this).
• You can chat and discuss the problems among yourselves, but you should do your own implementation (simply copying code is considered a severe break of the code of conduct),
• The code 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 links to any websites you have consulted).

Pedro Ribeiro - DCC/FCUP | Last update: