Weekly Problems #02
	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: 08/10/2024
• Date of delivery (deadline): 23h59m of 28/10/2024 (-2% for each extra day)
• Topics: Sorting, binary search, ternary search, bisection

6 proposed problems:

• [Mooshak PC006] - Special Sort
  Hints

  Simply use a custom sort 😉

  
  
• [Mooshak PC007] - Factory Machines
  Hints

  If the correct answer is s, then the factory cannot make the products in s-1 seconds or in any number of seconds smaller than s. Similarly, it can certainly produce them in s+1 seconds or in any number of seconds bigger than s.
  
  This is a no no ... no yes yes ... yes search space and you can binary search the answer!
  
  Checking if a certain number of seconds is feasible is easy right (you can do it in a greedy fashion with linear time in n)? 😉

  
  
• [Mooshak PC008] - Pie
  Hints

  Again an optimization problem (find the largest volume). If a certain volume is possible, than certainly all smaller volumes are also possible, right (even if it leads to more spoiled pie)?
  
  How can we use this to binary search on the volume? And when should we stop our search?

  
  
• [Mooshak PC009] - Building Construction
  Hints

  Think about the correct answer k. What happens to the cost when k is lower? And when k is bigger? You can even make a program to check these costs. What is the shape of the cost function cost(k)? How can you use this?

  
  
• [CodeForces 713B] - Searching Rectangles
  Hints

  Welcome to an interactive problem 😁 Searching all positions is too much, right? Can you think on how some kind of binary search can be applied?

  
  
• [CodeForces 818F] - Level Generation
  Hints

  What about making a problem withouth hints? 😃

  
  

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: