Weekly Problems #05
	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: 14/10/2025
• Date of delivery (deadline): 23h59m of 10/11/2025 (-2% for each extra day)
• Topics: Cumulative sums and fenwick trees (BITs)

6 proposed problems:

• [Mooshak PC021] - Maximum Sum
  (tested in C++, Java and Python)
  Hints

  - Use cumulative sums
  
  - Can you see how to use Kadane algorithm on one dimension to reduce the runtime complexity to \(\mathcal{O}(n^3)\)?
  
  

  
  
• [Mooshak PC022] - Japan
  (tested in C++, Java and Python)
  Hints

  - Can you see how the number of crossing is equal to the number of "inversions"?
  
  - Can you use a fenwick tree (with single queries and single updates) to compute?

  
  
• [CodeForces 276C] - Little Girl and Maximum Sum
  (tested in C++, Java and Python)
  Hints

  - Which position should have the highest value? And the 2nd highest? ...
  
  - How to use fenwick trees to compute frequencies of positions in the queries?
     (perhaps using range updates and single queries?)

  
  
• [Mooshak PC023] - Horrible Queries
  (tested in C++, Java and Python)
  Hints

  - Use a fenwick tree with range update and range queries

  
  
• [Mooshak PC024] - Matrix Summation
  (tested in C++, Java and Python)
  Hints

  - Use a 2D fenwick tree

  
  
• [Mooshak PC025] - Calculate The Cost
  (tested in C++, Java and Python)
  Hints

  - A "naive" fenwick tree approach will not fit on memory...
  
  - Would processing the trees and queries in a different order help you?

  
  

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: