USACO 2016 February Contest Gold Division - Circular Barn

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem also has a silver version, but solving that problem will only give us a small fraction of the test cases for this version as the constraints here are much higher and only allow for a linear time solution.

In order to solve this version, we will start with doubling the original array and subtracting one from each number. For the given example, the doubled array would look like \([1, 0, 0, 2, 0, 0, 1, 2, 2, 2, 1, 0, 0, 2, 0, 0, 1, 2, 2, 2]\) and with everything subtracted by \(1\), it will be like \([0, -1, -1, 1, -1, -1, 0, 1, 1, 1, 0, -1, -1, 1, -1, -1, 0, 1, 1, 1]\).

After doing some observations either by brute force or by some sort of a mathematical intuition, it turns out that it's optimal to place the cows in such a way that the subarray with the smallest sum is the ending segment of the redistribution of the cows, as these positions are in the biggest need of placing cows there, with respect of doubling the array at first.

Thus, we want to find the smallest subarray sum and use the algorithm described in the silver version only for that ending position in order to solve the problem.

Source code

The source code in C++ can be seen below.

#include <fstream>
#include <vector>
using namespace std;

int main() {
    ifstream cin("cbarn.in");
    ofstream cout("cbarn.out");

    int n;
    cin >> n;

    vector<int> v(n + n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        v[n + i] = v[i];
    }
    int sum = 0, smin = 0, wh = 1;
    for (int i = 1; i <= n + n; i++) {
        sum += (v[i] - 1);
        if (sum < smin) {
            smin = sum;
            wh = i;
            if (i > n) {
                wh -= n;
            }
        }
        if (i >= n) {
            sum -= (v[i - n + 1] - 1);
        }
    }
    long long ans = 1LL * n * n * n;

    int finalpos = wh;
    vector<int> v2 = v;
    int tpos = finalpos;
    int currpos = finalpos;
    long long ans2 = 0;
    do {
        while (v2[currpos] == 0) {
            currpos--;
            if (currpos == 0) {
                currpos = n;
            }
        }
        int dist = tpos - currpos;
        if (dist < 0) {
            dist += n;
        }
        ans2 += 1LL * dist * dist;
        tpos--;
        v2[currpos]--;
        if (tpos == 0) {
            tpos = n;
        }
    } while (tpos != finalpos);
    ans = min(ans, ans2);
    cout << ans;
    return 0;
}