- This event has passed.
7 PM – USACO Bronze – Darin
October 23 @ 7:00 pm - 8:00 pm
What We Did Today:
- Went through the Farmer John Actually Farms problem for the optimal solution
Homework:
- Code up the optimal solution for Farm John Actually Farms, and submit your answer to the webpage when you are finished here https://usaco.org/index.php?page=viewproblem2&cpid=1371:
Optimal Solution (Implementation Level) | ||
| 1 | Sort Your Plants | <- Use a Plant class to represent the plants details |
You want a mapping for the desired ordering to point to each index of the Plant array | ||
| 2 | Find the day of intersection between each pair in the sorted array | note: if the two pairs never intersect, and the initial ordering between the two is wrong, leave the algorithm |
use the y=mx+c and setting y’s equal to each other | ||
round up OR increment to the next day if the intersection is not a decimal | ||
| 3 | Check each pairs value at the interesting day and see if it matches one being greater than the other | |
| 4 | If all pairs pass, you take the highest day |
Also code up the brute force method for the problem (code and logic should be similar:
| Brute Force: | ||
| 1) | Find all the interesting days | |
Creating pairs for all the plants (double for loop) | ||
Computing the interesting days between all pairs and store in a list | ||
| 2) | For loop over all the interesting days | |
| 3) | Compute all heights | |
# Check if the ordering of the trees at this day matches the desired ordering | ||
| For p in plants: | ||
Compare p to every other plant, and count how many are bigger than itself | ||
| 4) | Check if this count matches the index at T |
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).