2014 Jan Silver Problem 2 Cross Country Skiing

Problem

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.

Solution

Show Solution

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).

Code

C++

Show Code

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> elevation;
vector<vector<int>> destination;
int totalPoints, current;
int startX = -1, startY = -1;
int numRows, numCols;
int maxHeight = 0, minHeight = 1e9;

void bfs(int x, int y, int& maxDiff, vector<vector<bool>>& visited) {
    visited[x][y] = true;
    current += destination[x][y];

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};

    for (int i = 0; i < 4; i++) {
        int newX = x + dx[i];
        int newY = y + dy[i];

        if (newX >= 0 && newX < numRows && newY >= 0 && newY < numCols &&
            !visited[newX][newY] && abs(elevation[newX][newY] - elevation[x][y]) <= maxDiff) {
            bfs(newX, newY, maxDiff, visited);
        }
    }
}

bool isReachable(int maxDiff) {
    current = 0;
    vector<vector<bool>> visited(numRows, vector<bool>(numCols, false));
    bfs(startX, startY, maxDiff, visited);
    return current >= totalPoints;
}

int main() {
    freopen("ccski.in", "r", stdin);
    freopen("ccski.out", "w", stdout);

    cin >> numRows >> numCols;
    totalPoints = 0;

    elevation.resize(numRows, vector<int>(numCols, 0));
    destination.resize(numRows, vector<int>(numCols, 0));

    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < numCols; j++) {
            cin >> elevation[i][j];
            maxHeight = max(maxHeight, elevation[i][j]);
            minHeight = min(minHeight, elevation[i][j]);
        }
    }

    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < numCols; j++) {
            cin >> destination[i][j];
            totalPoints += destination[i][j];
            if (startX < 0 && destination[i][j] == 1) {
                startX = i;
                startY = j;
            }
        }
    }

    int high = maxHeight - minHeight + 1;
    int low = 0;

    while (low < high) {
        int mid = (low + high) / 2;
        if (isReachable(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    cout << high << endl;
}

C++ (BFS)

Show Code

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> elevation;
vector<vector<int>> destination;
int totalPoints, current;
int startX = -1, startY = -1;
int numRows, numCols;
int maxHeight = 0, minHeight = 1e9;

void bfs(int x, int y, int maxDiff) {
    queue<pair<int, int>> q;
    vector<vector<bool>> visited(numRows, vector<bool>(numCols, false));
    q.push({x, y});
    visited[x][y] = true;

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        current += destination[x][y];

        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            if (newX >= 0 && newX < numRows && newY >= 0 && newY < numCols &&
                !visited[newX][newY] && abs(elevation[newX][newY] - elevation[x][y]) <= maxDiff) {
                q.push({newX, newY});
                visited[newX][newY] = true;
            }
        }
    }
}

bool isReachable(int maxDiff) {
    current = 0;
    bfs(startX, startY, maxDiff);
    return current >= totalPoints;
}

int main() {
    freopen("ccski.in", "r", stdin);
    freopen("ccski.out", "w", stdout);

    cin >> numRows >> numCols;
    totalPoints = 0;

    elevation.resize(numRows, vector<int>(numCols, 0));
    destination.resize(numRows, vector<int>(numCols, 0));

    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < numCols; j++) {
            cin >> elevation[i][j];
            maxHeight = max(maxHeight, elevation[i][j]);
            minHeight = min(minHeight, elevation[i][j]);
        }
    }

    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < numCols; j++) {
            cin >> destination[i][j];
            totalPoints += destination[i][j];
            if (startX < 0 && destination[i][j] == 1) {
                startX = i;
                startY = j;
            }
        }
    }

    int high = maxHeight - minHeight + 1;
    int low = 0;

    while (low < high) {
        int mid = (low + high) / 2;
        if (isReachable(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    cout << high << endl;
}

Java

Show Code

import java.util.*;
import java.io.*;

public class Main {
    static int[][] elevation;
    static int[][] destination;
    static int totalPoints, current;
    static int startX = -1, startY = -1;
    static int numRows, numCols;
    static int maxHeight = 0, minHeight = 1000000000;

    static void bfs(int x, int y, int maxDiff, boolean[][] visited) {
        visited[x][y] = true;
        current += destination[x][y];

        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            if (newX >= 0 && newX < numRows && newY >= 0 && newY < numCols &&
                !visited[newX][newY] && Math.abs(elevation[newX][newY] - elevation[x][y]) <= maxDiff) {
                bfs(newX, newY, maxDiff, visited);
            }
        }
    }

    static boolean isReachable(int maxDiff) {
        current = 0;
        boolean[][] visited = new boolean[numRows][numCols];
        bfs(startX, startY, maxDiff, visited);
        return current >= totalPoints;
    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream("ccski.in"));
        System.setOut(new PrintStream(new FileOutputStream("ccski.out")));

        Scanner sc = new Scanner(System.in);

        numRows = sc.nextInt();
        numCols = sc.nextInt();
        totalPoints = 0;

        elevation = new int[numRows][numCols];
        destination = new int[numRows][numCols];

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                elevation[i][j] = sc.nextInt();
                maxHeight = Math.max(maxHeight, elevation[i][j]);
                minHeight = Math.min(minHeight, elevation[i][j]);
            }
        }

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                destination[i][j] = sc.nextInt();
                totalPoints += destination[i][j];
                if (startX < 0 && destination[i][j] == 1) {
                    startX = i;
                    startY = j;
                }
            }
        }

        int high = maxHeight - minHeight + 1;
        int low = 0;

        while (low < high) {
            int mid = (low + high) / 2;
            if (isReachable(mid)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        System.out.println(high);

        sc.close();
    }
}

Python

Show Code

import sys
from typing import List

def bfs(x: int, y: int, max_diff: int, visited: List[List[bool]]) -> None:
    visited[x][y] = True
    global current
    current += destination[x][y]

    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    for i in range(4):
        new_x = x + dx[i]
        new_y = y + dy[i]

        if (0 <= new_x < num_rows and 0 <= new_y < num_cols and
            not visited[new_x][new_y] and abs(elevation[new_x][new_y] - elevation[x][y]) <= max_diff):
            bfs(new_x, new_y, max_diff, visited)

def is_reachable(max_diff: int) -> bool:
    global current
    current = 0
    visited = [[False] * num_cols for _ in range(num_rows)]
    bfs(start_x, start_y, max_diff, visited)
    return current >= total_points

sys.stdin = open('ccski.in', 'r')
sys.stdout = open('ccski.out', 'w')

num_rows, num_cols = map(int, input().split())
total_points = 0

elevation = [list(map(int, input().split())) for _ in range(num_rows)]
destination = [list(map(int, input().split())) for _ in range(num_rows)]

max_height = max(max(row) for row in elevation)
min_height = min(min(row) for row in elevation)

start_x, start_y = -1, -1
for i in range(num_rows):
    for j in range(num_cols):
        if destination[i][j] == 1:
            start_x, start_y = i, j
            break
    if start_x != -1:
        break

high = max_height - min_height + 1
low = 0

while low < high:
    mid = (low + high) // 2
    if is_reachable(mid):
        high = mid
    else:
        low = mid + 1

print(high)