USACO Gold 2016 January - Radio Contact

Official Analysis

Explanation

The key $\texttt{dp}$ observation to make here is already stated in the problem statement: "Farmer John can either stay put at his current location, or take one step forward", and likewise for Bessie. Thus, when constructing our $\texttt{dp}$, we can set $\texttt{dp}[i][j]$ equal to the best distance at Farmer John's move $i$ and Bessie's move $j$.

Notice that it is hard to calculate a cumulative distance if we leave the string unprocessed (meaning that we read from the string directly). To resolve this, we can simply calculate the coordinates $(i,j)$ at every step of Bessie and Farmer John's path. In our implementation, we map each character to their appropriate dx, dy arrays in order to apply the appropriate changes, storing Farmer John's position at move $i$ as $\texttt{jl}[i]$ and Bessie's position at move $j$ at $\texttt{bl}[j]$.

After this is done, we start building our $\texttt{dp}$:

Either one of the following happens:

1. Farmer John takes a step $(i+1)$: $\texttt{dp}[i+1][j] = \min(\texttt{dp}[i+1][j], \texttt{dp}[i][j] + \text{dist}(\texttt{jl}[i+1], \texttt{bl}[j]))$

2. Bessie takes a step $(j+1)$: $\texttt{dp}[i][j+1] = \min(\texttt{dp}[i][j+1], \texttt{dp}[i][j] + \text{dist}(\texttt{jl}[i], \texttt{bl}[j+1]))$

3. Both Farmer John and Bessie take steps $(i+1)$ and $(j+1)$: $\texttt{dp}[i+1][j+1] = \min(\texttt{dp}[i+1][j+1], \texttt{dp}[i][j] + \text{dist}(\texttt{jl}[i+1], \texttt{bl}[j+1]))$

Implementation

Time Complexity: $\mathcal{O}(NM)$

#include <bits/stdc++.h> // see /general/running-code-locally
using namespace std;

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()