7 PM – USACO Bronze – Darin

What We Did Today:

1. Went over the Balancing Bacteria optimal solution 2 implementation using difference arrays

Homework:

1. Code up the optimal solution using sorting + binary search on the difference values Maximizing Productivity, and submit your answer to the webpage and google drive when you are finished
   problem: https://usaco.org/index.php?page=viewproblem2&cpid=1397
2. Note on the optimal solution(s) presented in classOptimal Solution 1 (Optimized naive solution):

   We can rearrange the formula for the brute force:
   S + t_i < c_i,
   into
   c_i – t_i > S

   Then we can sort the differences and perform a binary search on it to reduce the number of checks to perform on the N farms.

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