USACO 2018 February Contest Silver Division - Snow Boots

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can run dfs to calculate all possible paths accounting for the boots used and get the minimum boots used at the end of the path when the dfs finishes. Alternatively, as the constraints are small, we can compute all distances using brute force, obtaining the minimum answer.

Source code

The source code in C++ can be seen below.

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

int ans[251];

int main(){
    ifstream cin("snowboots.in");
    ofstream cout("snowboots.out");

    int n, b; cin >> n >> b;
    vector<int> depths(n);
    vector<pair<int, int>> boots(b);

    for (int i = 0; i < n; i++){
        cin >> depths[i];
        ans[i] = INT_MAX;
    }

    for (int i = 0; i < b; i++){
        int a, b; cin >> a >> b;
        boots[i] = {a, b};
    }

    ans[0] = 0;
    for (int a = 0; a < n; a++) {
        // distance, current boot number
        pair<int, int> current = {a, ans[a]};
        if (ans[a] == INT_MAX) continue;
        for (int i = current.second; i < boots.size(); i++){
            pair<int, int> boot = boots[i];
            for (int j = current.first; j <= current.first + boot.second; j++){
                if (boot.first >= depths[current.first] && boot.first >= depths[j]){
                    if (ans[j] > i){
                        ans[j] = i;
                    }
                }
            }
        }
    }
    cout << ans[n - 1];
}