USACO 2023 January Contest Silver Division - Following Directions

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Each cow takes only one path, so work backwards from each path to calc initial cost, and then for each change go forward from changed cow in both original direction and new direction to subtract and add costs, respectively.

Source code

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

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n;
vector<string> arr;
vector<vector<int>> cows;
map<pair<int, int>, int> vat_costs;
void dfs(pair<int, int> start) {
    cows[start.first][start.second] = 1;

    if (start.first - 1 >= 0 && arr[start.first - 1][start.second] == 'D') {
        dfs({start.first - 1, start.second});
        cows[start.first][start.second] += cows[start.first - 1][start.second];
    }
    if (start.second - 1 >= 0 && arr[start.first][start.second - 1] == 'R') {
        dfs({start.first, start.second - 1});
        cows[start.first][start.second] += cows[start.first][start.second - 1];
    }
}

int dfs_change(pair<int, int> start, int cows_delta) {
    cows[start.first][start.second] += cows_delta;

    if (arr[start.first][start.second] == 'D') {
        if (start.first + 1 >= n) {
            return vat_costs[{start.first + 1, start.second}];
        }
        return dfs_change({start.first + 1, start.second}, cows_delta);
    } else if (arr[start.first][start.second] == 'R') {
        if (start.second + 1 >= n) {
            return vat_costs[{start.first, start.second + 1}];
        }
        return dfs_change({start.first, start.second + 1}, cows_delta);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    arr.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        int cost;
        cin >> cost;
        vat_costs[{i, n}] = cost;
    }
    for (int i = 0; i < n; i++) {
        int cost;
        cin >> cost;
        vat_costs[{n, i}] = cost;
    }

    int res = 0;

    cows.resize(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        if (!cows[i][n - 1]) {
            dfs({i, n - 1});
        }
        if (arr[i][n - 1] == 'R') {
            res += cows[i][n - 1] * vat_costs[{i, n}];
        }
    }

    for (int i = 0; i < n; i++) {
        if (!cows[n - 1][i]) {
            dfs({n - 1, i});
        }
        if (arr[n - 1][i] == 'D') {
            res += cows[n - 1][i] * vat_costs[{n, i}];
        }
    }

    cout << res << endl;

    // calculate changes
    int q;
    cin >> q;
    while (q--) {
        int i, j;
        cin >> i >> j;
        i--;
        j--;

        int delta_cows = cows[i][j];
        res -= dfs_change({i, j}, -delta_cows) * (delta_cows);
        if (arr[i][j] == 'D') {
            arr[i][j] = 'R';
        } else {
            arr[i][j] = 'D';
        }
        res += dfs_change({i, j}, delta_cows) * (delta_cows);
        cout << res << endl;
    }

    return 0;
}