USACO Gold 2016 February - Circular Barn Revisited

Official Analysis (C++)

Explanation

The problem asks for the minimum amount of distance the cows need to travel for a circular barn. However, if we fix the position of the first door, the problem can be reduced to a linear barn $\texttt{rooms}[1..n]$ where we place the first door at the beginning of our linear barn. In such case, we can define $\texttt{dp}[i][j]$ as the sum of distance to fill the rooms $[j, n]$ if we place the $i$-th door at $j$. All values of the $\texttt{dp}$ array are initialized with infinity. We further set $\texttt{dp}[0][n+1] = 0$ because with no doors the only case where the distance is zero is to fill no room. Our transitions would then be

$\texttt{dp}[i][j] = min(\texttt{dp}[i][j], \sum_{p=j+1}^{n+1} (p-j-1) \cdot \texttt{rooms}[p-1] + \texttt{dp}[i-1][p])$,

where $i \in [1,k]$ and $j \in [1,n]$. In other words, $dp[i][j]$ is the minimum of all distances if we put the $i$-th door at $j$ with the last door placed at some place $p$ after $j$. This distance is calculated by adding the distance to fill the rooms $[j, p)$ to the optimal amount of distance to fill rooms $[p, n]$ with $i-1$ doors. $\texttt{dp}[k][0]$ represents the minimum amount of distance needed if we place the first door at the beginning of the current array $\texttt{rooms}$. We then start from the second door by moving the first room $\texttt{rooms}[0]$ to the end of the array and do the DP again.

Our answer would be the minimum distance among all possible positions for the first door.

There are $n$ doors which can be chosen as the first door. In each DP, we add each time one of the $k$ doors and iterate through each of $n$ positions to place it. For each of these positions, we go through all possible $n$ placement of the last door and calculate the optimal result for our current position with the new door. This yields a total time complexity of $\mathcal{O}(k n^3)$, which is fast enough for the given constraints.

Implementation

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

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

	int n, k;
	cin >> n >> k;
	deque<int> rooms(n);