Editing 2014 Jan Silver Problem 2 Cross Country Skiing (section)

== Solution ==

<div class="mw-collapsible mw-collapsed">
    <h2 class="mw-collapsible-toggle" >Show Solution</h2><br><br><br>
    <div class="mw-collapsible-content">
To approach this question, you can use a binary search algorithm to find the minimum difficulty rating D that allows a cow to reach any waypoint from any other waypoint by repeatedly skiing from a cell to an adjacent cell with an absolute elevation difference at most D.

First, you need to read the input values and store the elevations and the waypoint designations in an appropriate data structure. You can use a two-dimensional vector to store the elevations and another two-dimensional vector to store the waypoint designations.

Next, you can perform a binary search over the range of possible values for D. You can start with a range of [0, max_elevation], where max_elevation is the maximum elevation in the grid. At each step of the binary search, you check if all the waypoints are mutually reachable using the current value of D. You can do this by performing a depth-first search (DFS) or breadth-first search (BFS) on the waypoint cells and checking if all the waypoints are visited. If all the waypoints are visited, you can update the upper bound of the range of possible values for D. Otherwise, you update the lower bound.

Repeat the binary search until the upper and lower bounds converge to a single value. This value is the minimum difficulty rating D that allows a cow to reach any waypoint from any other waypoint by repeatedly skiing from a cell to an adjacent cell with an absolute elevation difference at most D. Finally, output the value of D.

Note that in the DFS or BFS, you need to check if a cell is adjacent to another cell with an elevation difference at most D. You can use a two-dimensional array to store the visited status of each cell during the search.

Overall, the time complexity of this approach is O(MN log W), where W is the range of possible values for D (i.e., max_elevation - 0).

    </div>
</div>