Feb, Problem 2 | Why Did the Cow Cross the Road II

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 [email protected] so that we can fix any inaccuracies.