USACO Gold 2020 January - Time is Mooney

Official Analysis (C++)

Explanation

We define $\texttt{dp}[t][i]$ as the maximum moonies Bessie can have at city $i$ on day $t$. Starting with $\texttt{dp}[0][0] = 0$, we iterate over each day up to $T_{\text{max}}$, the maximum number of days, and over each city, updating $\texttt{dp}[t + 1][j]$ for all cities $j$ reachable from city $i$ via a directed road.

We compare the current value of $\texttt{dp}[t + 1][j]$ with the value of coming from an adjacent city on the previous day, $\texttt{dp}[t][i] + \text{moonies}[j]$, and take the maximum. After processing each day, we calculate the profit as $\texttt{dp}[t][0] - C \cdot t^2$, representing the total moonies minus the travel cost for $t$ days, and track the maximum profit.

Note that the maximum amount of money Bessie makes is $1000t - t^2$ in the case where she makes $1000$ moonies per city and the cost is $1$ mooney. This is also because the edge weights $m_i$ are bounded by $1000$ moonies. Her earnings become negative when $t > 1000$, so we only have to check her movement across the cities for at most $1000$ days.

Implementation

Time Complexity: $\mathcal{O}(T_{\text{max}} \cdot (N + M))$

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

const int MAX_DAYS = 1000;  // Maximum number of days Bessie can travel

int main() {
	ifstream read("time.in");

	int n, m, c;
	read >> n >> m >> c;

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

public class Main {
	static final int MAX_DAYS = 1000;  // Maximum number of days Bessie can travel

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

Copy
with open("time.in", "r") as fin:
	n, m, c = map(int, fin.readline().split())
	moonies = list(map(int, fin.readline().split()))

	adj = [[] for _ in range(n)]
	for _ in range(m):
		a, b = map(int, fin.readline().split())
		adj[a - 1].append(b - 1)  # Convert 1-indexed input to 0-indexed

MAX_DAYS = 1000  # Maximum number of days Bessie can travel