USACO 2018 February Contest Bronze Division - Hoofball

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Sort the positions and either do some dp or do some casework based on where each cow will pass the ball to. There are easier solutions too.

Source codes

The source codes in C++ and Python can be seen below.

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

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

    int n;
    cin >> n;

    vector<int> v(n+2);
    v[0] = -1000000000; v[n+1] = 1000000000;
    for(int i = 1; i <= n; i++)
        cin >> v[i];
    sort(v.begin() + 1, v.begin() + n + 1);

    vector<int> dp(n+1, (1<<30));
    dp[0] = 0;

    for(int i = 1; i <= n; i++)
    {
        int mini = i;
        int maxi = i;
        int poz = i;
        for(int j = 1; j <= 1000; j++)
        {
            if(abs(v[poz-1] - v[poz]) <= abs(v[poz+1] - v[poz]))
                poz--;
            else
                poz++;
            mini = min(mini, poz);
            maxi = max(maxi, poz);
        }
        for(int j = mini; j <= maxi; j++)
            dp[j] = min(dp[j], dp[mini-1] + 1);
    }

    cout << dp[n];
    return 0;
}

with open("hoofball.in", "r") as fin:
    n = int(fin.readline().strip())
    v = [0] * (n + 2)
    v[0] = -1000000000
    v[n+1] = 1000000000
    tokens = fin.read().split()
    for i in range(1, n+1):
        v[i] = int(tokens[i-1])
    v[1:n+1] = sorted(v[1:n+1])

INF = 1 << 30
dp = [INF] * (n + 1)
dp[0] = 0

for i in range(1, n+1):
    mini = i
    maxi = i
    poz = i
    for j in range(1, 1001):
        if abs(v[poz-1] - v[poz]) <= abs(v[poz+1] - v[poz]):
            poz -= 1
        else:
            poz += 1
        mini = min(mini, poz)
        maxi = max(maxi, poz)
    for j in range(mini, maxi+1):
        dp[j] = min(dp[j], dp[mini-1] + 1)

with open("hoofball.out", "w") as fout:
    fout.write(str(dp[n]))