7 PM – USACO Bronze – Darin

What We Did Today:

1. Went over the Balancing Bacteria optimal solution over greedy search

Homework:

1. Code up the optimal solution(s) for Balancing Bacteria, and submit your answer to the webpage and google drive when you are finished
   problem: https://usaco.org/index.php?page=viewproblem2&cpid=1372

   Note on the optimal solution:
   In class we talked about how to derive the accumulation by analyzing the solution, and estimating the remainder needed.

   Note that I did not account for the remainder properly because the remainder is computed one step ahead in time (meaning after the first update we assume no remainder), but this makes it hard to compute the remainder as we need more variables to keep track for proper remainder counting

   Instead, on every update, it suffices for us to increment the accumulation by the netSprayValue (everytime we do a target spray, what is the net target spray value) + currentSprayValue

   However I recommend practicing with deriving the update rule for the accumulation, analyzing the numbers shown by hand accounting the needed accumulation then seeing if you can come up with a pattern for the accumulation shown. This is important especially during competitions where you will be asked to come up with a formula you may have not seen before but is in similar spirit.

Notes:

You can reach out to me at ddjapri@ayclogic.com if you have any questions!

You can find class notes here (Tues7PM_IntroToCompProgramming is our excel sheet for visuals).