USACO 2016 January Contest Bronze Division - Angry Cows

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can simulate the process and be careful about the outcome each explosion has, while also taking in account the potential chain reactions. Thankfully, the ranges are pretty small, so we can use brute force.

Source codes

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

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

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

    int n;
    cin >> n;

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

    int mx = 0;
    for(int i = 1; i <= n; i++)
    {
        int L = i-1, R = i+1;
        bool deadL = 0, deadR = 0;
        for(int range = 1; range <= 100; range++)
        {
            int prv = L+1;
            bool ok = 0;
            if(!deadL)
            {
                while(L >= 1 && v[prv] - v[L] <= range)
                    L--, ok = 1;
                if(ok == 0)
                    deadL = 1;
            }
            ok = 0;
            prv = R-1;
            if(!deadR)
            {
                while(R <= n && v[R] - v[prv] <= range)
                    R++, ok = 1;
                if(ok == 0)
                    deadR = 1;
            }
            if(deadL && deadR)
                break;
        }
        mx = max(mx, R - L - 1);
    }

    cout << mx;
    return 0;
}

with open("angry.in", "r") as fin:
    data = fin.read().split()
n = int(data[0])
v = [int(x) for x in data[1:1+n]]
v.sort()

mx = 0
for i in range(n):
    L = i - 1
    R = i + 1
    deadL = False
    deadR = False
    for blast in range(1, 101):
        if not deadL:
            prv = L + 1
            ok = False
            while L >= 0 and v[prv] - v[L] <= blast:
                L -= 1
                ok = True
            if not ok:
                deadL = True
        if not deadR:
            prv = R - 1
            ok = False
            while R < n and v[R] - v[prv] <= blast:
                R += 1
                ok = True
            if not ok:
                deadR = True
        if deadL and deadR:
            break
    mx = max(mx, R - L - 1)

with open("angry.out", "w") as fout:
    fout.write(str(mx))