Old Gold - The Cow Run

Official Analysis (C++)

Explanation

When we go from one point to another, it's optimal to pick up every cow along the way, so the list of cows that we visit will always form a subarray in the sorted list of all the cows.

So, we'll sort the cows by their position.

However, the optimal solution might involve going from one side to another as well. To account for this, let's use range DP.

States

We have to keep track of the cows that we've already picked up. Since this'll always be a range, we'll represent it as $i$ and $j$ (the endpoints of the interval).

We also have to keep track of which side we're on ($k$).

$\texttt{dp}[i][j][k] = \hspace{0.1cm}$minimum cost to visit all of these cows.

The answer will be the minimum of each side when considering the entire range.

Base Cases

If we only visit cow $i$, then it'll cost us $\texttt{pos}[i] \cdot n$ because every other cow will keep costing us money while we go to halt that cow.

Transitions

There are four possible cases. Here, $k=0$ means that Farmer John is on the left of the interval, and $k=1$ means Farmer John is on the right.

$\texttt{dp}[i][j][0] = \min(\texttt{dp}[i + 1][j][0] + |x[i + 1] - x[i]| \cdot \texttt{remaining}, \texttt{dp}[i + 1][j][1] + |x[i] - x[j]| \cdot \texttt{remaining})$

$\texttt{dp}[i][j][1] = \min(\texttt{dp}[i][j - 1][1] + |x[j - 1] - x[j]| \cdot \texttt{remaining}, \texttt{dp}[i][j - 1][0] + |x[i] - x[j]| \cdot \texttt{remaining})$

For each side, we have to consider whether to continue going the same way or to visit the next cow on the opposite end.

Implementation

Time Complexity: $\mathcal{O}(N^2)$

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

int main() {
	freopen("cowrun.in", "r", stdin);
	freopen("cowrun.out", "w", stdout);

	int n;
	cin >> n;

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

public class CowRun {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("cowrun.in"));
		int n = Integer.parseInt(br.readLine());

		int[] pos = new int[n];
		for (int i = 0; i < n; i++) { pos[i] = Integer.parseInt(br.readLine()); }