AtCoder ABC 237 E Skiing

This is my solution and the regarding ways of thinking about the ABC 237 E Skiing problem. The original problem can be found here.

First Observation

I thought this problem can be described by using a graph, where nodes are the open spaces, edges are the slopes, and edge weights are the happiness changes. To find out the path from Space 1 to any other spaces with maximum (or minimum) cost, we can use Dijkstra’s algorithm. However, Dijkstra only works on the graph that doesn’t contain negative weights. In this problem, if directly connected spaces are in different heights, the edge from higher to lower has a positive weight but the weight of the edge from lower to higher must be a negative value. So, simply applying Dijkstra to this problem is impossible.

Exploring

For any pair of a starting point $u$ and a destination $v$ where $u$ located higher than $v$ ($H_u > H_v$), the maximum possible happiness is $(H_u – H_v)$. This is achieved when the path from $u$ and $v$ consists of only downhills. When this path exists, any other paths containing uphills result in happiness strictly less than $(H_u – H_v)$. It doesn’t mean we should not choose to go up a hill. There may be a space that locates quite lower than the other spaces but is only achievable from the starting point by accepting the cost of climbing up. This trait makes this problem difficult to solve.

My crucial observation came up when I was thinking about a variety of paths from fixed $u$ and $v$. As I stated, the best possible path contains only downhills. Let $h$ be $(H_u – H_v)$. This can be the maximum happiness from $u$ to $v$. Think about what if I climb up by 1 somewhere in the path. The happiness becomes $h – 1$ because climbing up costs 2 while additional happiness from climbing up is only 1. Similarly, if I climb up by 2 in the path, the happiness will be $h – 2$, and climbing up by 3 results in $h – 3$ of happiness. Namely, given $H_u$ and $H_v$, we can compute the happiness of a path from $u$ to $v$ if we know how many we climb up along the way. Therefore, to obtain the maximum happiness, we need to know the minimum climb-ups from $u$ to $v$.

Restating the Problem

With the observation above, what we need to do has become simple.
1. Create a graph by adjacency list representation where the weight of $u \to v$ is $2 \times (H_v – H_u)$ if $H_u < H_v$ and $0$ otherwise. (Note that I doubled the climb-ups to show the actual happiness decrease.)
2. Run Dijkstra’s algorithm to compute the minimum cost from Space 1 to other spaces.
3. For each space, compute the best happiness using the observation.

Sample Code in C++

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main() {
 
    int n, m;
    cin >> n >> m;
    vector<ll> height(n);
    for (int i = 0; i < n; i++) {
        cin >> height[i];
    }
 
    vector<vector<pair<ll, int>>> adj(n, vector<pair<ll, int>>());
    int u, v;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        u--; v--;
        if (height[u] > height[v]) {
            adj[u].push_back(make_pair(0ll, v));
            adj[v].push_back(make_pair(2 * (height[u] - height[v]), u));
        }
        else if (height[v] > height[u]) {
            adj[u].push_back(make_pair(2 * (height[v] - height[u]), v));
            adj[v].push_back(make_pair(0ll, u));
        }
        else {
            adj[u].push_back(make_pair(0ll, v));
            adj[v].push_back(make_pair(0ll, u));
        }
    }
 
    vector<ll> dij(n, 1e12);
    dij[0] = 0ll;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    pq.push(make_pair(0ll, 0));
 
    while (!pq.empty()) {
        pair<ll, int> curr = pq.top();
        pq.pop();
        if (dij[curr.second] == curr.first) {
            for (auto & edge : adj[curr.second]) {
                if (dij[edge.second] > curr.first + edge.first) {
                    dij[edge.second] = curr.first + edge.first;
                    pq.push(make_pair(dij[edge.second], edge.second));
                }
            }
        }
    }
 
    ll best = 0ll;
    for (int i = 0; i < n; i++) {
        ll pleasure = dij[i] / 2 + (height[0] - height[i]) - dij[i];
        if (pleasure > best) {
            best = pleasure;
        }
    }
 
    cout << best << endl;
 
    return 0;
}