USACO Gold 2016 January - Radio Contact

Official Analysis

Video Solution

Note: The video solution might not be the same as other solutions. Code in C++.

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

Copy
 Code Snippet: C++ Short Template (Click to expand)

int N, M;

const int INF = 1e9 + 7;
const int MX = 1e3 + 1;

int sq(int a) { return a * a; }

int dist(pi a, pi b) {  // distance squared between two points

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

public class radio {
	public static int[][] fjLocs;
	public static int[][] bLocs;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("radio.in"));
		PrintWriter pw = new PrintWriter(new FileWriter("radio.out"));