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 second optimal solution using difference arrays 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 
2. Note on the optimal solution(s) presented in class

   Optimal Solution 1 (Optimized naive solution):

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

   This resulted in the formula net_accumulation[i] = net_accumulation[i-1] + cur_sprays + net_sprays.

   The purpose of the net_accumulation is to iteratively adjust the target patch without adjusting every patch that comes after it. This value can be thought of as individual accumulations from every patch before it, but every patch before it also has a position multiplier.

   I recommend re-deriving the formula above, seeing how to go from an understanding of the problem to the solution mentioned above.

   The easiest way to derive the formula above is through analyzing the operations done and how those operations increment/decrement the values of the next target patches.

   Optimized Solution 2 (Difference Arrays):
   We derived this solution by realizing we can transform the problem space S and the operation O on the space into another form that is meaningful.

   Diff(A) means you transform the array A by subtracting each position in the array with the previous position value.

   So Diff(A): [    A[0],    A[1] – A[0],   A[2] – A[1], …, A[last_index] – A[last_index – 1]]

   We start with the original space S, with an example as shown:
   –1  0 –1 0

   where the operation to balance patch 1 causes an accumulation shown as:
   +1, +2, +3, +4

   Transforming the original operation O with Diff(O) changes the operations to:
   +1, +1, +1, +1

   Transforming it one more time to Diff(Diff((O)) leads the operation to become:
   +1, 0, 0, 0

   Which means that the operation Diff(Diff(O)) on a patch does not affect the other patches.

   However this Diff(Diff(O)) operation has to be done on the Diff(Diff(S)) space instead of the original.

   So in implementing the second optimal solution, define a Diff() function which transforms an array, and then equalize the Diff(Diff(S)) space instead to figure out the number of operations needed to set everything to 0.

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).