USACO 2020 US Open Contest Bronze Division - Social Distancing II

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Sort the cows and find the maximum radius which respects the constraints, then traverse the array values and count the number of possible answers.

Source codes

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

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

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

    int n;
    cin >> n;
    vector<pair<int, int> > cows(n+1);

    int radius = 100000000;

    for(int i = 1; i <= n; i++)
        cin >> cows[i].first >> cows[i].second;

    sort(cows.begin() + 1, cows.begin() + n + 1);

    for(int i = 1; i <= n; i++)
    {
        if(i + 1 <= n && cows[i].second != cows[i+1].second)
            radius = min(radius, cows[i+1].first - cows[i].first);
    }

    int cnt = 0;

    for(int i = 1; i <= n; i++)
    {
        if(cows[i].second == 1 && (i == 1 || cows[i].first - cows[i-1].first >= radius))
            cnt++;
    }

    cout << cnt;
    return 0;
}

with open("socdist2.in", "r") as fin:
    n = int(fin.readline().strip())
    cows = []
    for _ in range(n):
        a, b = map(int, fin.readline().split())
        cows.append((a, b))
cows.sort(key=lambda x: x[0])
radius = 100000000
for i in range(n - 1):
    if cows[i][1] != cows[i+1][1]:
        radius = min(radius, cows[i+1][0] - cows[i][0])
cnt = 0
for i in range(n):
    if cows[i][1] == 1 and (i == 0 or cows[i][0] - cows[i-1][0] >= radius):
        cnt += 1
with open("socdist2.out", "w") as fout:
    fout.write(str(cnt))