1,048
edits
2014 Jan Silver Problem 2 Cross Country Skiing: Difference between revisions
Jump to navigation
Jump to search
→Solution
(→Code) |
|||
| Line 3: | Line 3: | ||
The problem describes a cross-country skiing course represented by an M x N grid of elevations, some of which are designated as waypoints. The difficulty rating of the course is the minimum value of D such that all waypoints are mutually reachable by repeatedly skiing from one cell to an adjacent cell with an absolute elevation difference of at most D. The difficulty rating is calculated based on the elevations and the waypoint designations provided in the input. The task is to calculate and output the difficulty rating of the course. | The problem describes a cross-country skiing course represented by an M x N grid of elevations, some of which are designated as waypoints. The difficulty rating of the course is the minimum value of D such that all waypoints are mutually reachable by repeatedly skiing from one cell to an adjacent cell with an absolute elevation difference of at most D. The difficulty rating is calculated based on the elevations and the waypoint designations provided in the input. The task is to calculate and output the difficulty rating of the course. | ||
<div class="mw-collapsible mw-collapsed"> | |||
<h2 class="mw-collapsible-toggle">Solution</h2> | |||
<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. | 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. | ||
| Line 16: | Line 18: | ||
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). | 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> | |||
== Code == | == Code == | ||