Feb, Problem 2 | Why Did the Cow Cross the Road II
A writeup of Feb number 2 from the USACO platinum problem set
Why Did the Cow Cross the Road II
Solution
This is a classic RMQ problem. For every cow, we maintain a running maximum of the number of crosswalks that can be drawn, using the cows from 0 to j. Note that only 8 * N updates ever occur because every cow has a maximum of 8 other cows they can draw a crosswalk to.
Code
My solution can be found here
Written by Robert Chen
Notice any mistakes? Please email us at learn@teamscode.com so that we can fix any inaccuracies.