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

6 proposed problems (1st problem solved is worth 35%, 2nd one 30%, 3rd one 20% and 4th one 15% - see evaluation for details)

Submit on Virtual Judge

• [UVA 12532] - Interval Product
  Hints

  segment tree - range queries + single update, with a clasic merge

  
  
• [UVA 11235] - Frequent values
  Hints

  segment tree - just range queries, but with less standard "merge" operation

  
  
• [UVA 11297] - Census
  Hints

  2D segment tree

  
  
• [SPOJ KQUERY] - K-query
  Hints

  segment tree - can you think on to take advantage of offline querying?

  
  
• [SPOJ LITE] - Light Switching
  Hints

  segment tree + range updates with lazy propagation

  
  
• [SPOJ RACETIME] - Race Against Time
  Hints

  can be done with sqrt decomposition, range queries + single update

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: