USACO 2016 February Contest Silver Division - Circular Barn#

Problem link: here

Problem Solution#

Given that the constraints are very small, we can simply fix the position where we will finish placing the cows at. Now, for a given position, we will want to fill it using the closest available cow and add up the answers. Therefore, the lowest such answer will be optimal.

For some more advanced insights, as you will see in the gold version of this problem, it is actually optimal to start placing the cow in the segment with the smallest subarray sum if we subtract \(1\) from every position as these positions are in the biggest need of placing cows there. This is obviously with respect to the idea of doubling the array by appending it once.

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]\).

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 + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    int ans = n * n * n;

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