7 PM – USACO Bronze – Darin

What We Did Today:

1. Went through the Farmer John Actually Farms problem for the brute force

Homework:

Implement the brute force code for the problem: https://usaco.org/index.php?page=viewproblem2&cpid=1349

Brute-Force Approach

When we want to check impossibility, the discussed method in class of comparing pairwise growths only works for whether or not it can stay in the desired positioning forever.

Instead, we can only check impossibility by checking each “point” that is a candidate for a successful ordering.

1. Enumerate “interesting” days
   Collect a finite set of days to test:

   • Day 0 (ordering could be right from the start)

   • For every integer day d≥0 where two plants would be equal height, take the day after it as d+1 (a correct ordering only happens when a switch happens)
     Hint: You can think of each plant’s growth as a line that grows in the xy plane, so what is a formula used to find the point of intersection between two lines (in other words, find the day the plants have the same height) ?

2. Simulate heights on each candidate day
   For each candidate day $d$, compute the heights of every plant (think what formula works for this)

3. Count “strictly taller” and compare to target
   For each plant i, count how many plants have height strictly greater than Hi(d).
   If all counts match the given target array $t$, record the day $d$.

4. Answer
   Output the smallest candidate day that works, or −1 if none do.

Edge cases:

1. Sanity check pairs
   For each pair of plants (i,j), note whether their relative order could ever change: if they grow at the same rate and start equal, they’ll be tied forever (makes a strict ranking impossible).

Notes:

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

You can find class notes here.