USACO 2020 US Open Contest, Silver Problem 1. Social Distancing

USACO 2020 US Open Contest, Silver Problem 1. Social Distancing

Farmer John is worried for the health of his cows after an outbreak of the highly contagious bovine disease COWVID-19.

In order to limit transmission of the disease, Farmer John's NN cows (2N1052≤N≤105) have decided to practice "social distancing" and spread themselves out across the farm. The farm is shaped like a 1D number line, with MM mutually-disjoint intervals (1M1051≤M≤105) in which there is grass for grazing. The cows want to locate themselves at distinct integer points, each covered in grass, so as to maximize the value of DD, where DD represents the distance between the closest pair of cows. Please help the cows determine the largest possible value of DD.

 

INPUT FORMAT (file socdist.in):

The first line of input contains NN and MM. The next MM lines each describe an interval in terms of two integers aa and bb, where 0ab10180≤a≤b≤1018. No two intervals overlap or touch at their endpoints. A cow standing on the endpoint of an interval counts as standing on grass.

 

OUTPUT FORMAT (file socdist.out):

Print the largest possible value of DD such that all pairs of cows are DD units apart. A solution with D>0D>0 is guaranteed to exist.

 

SAMPLE INPUT:

5 3
0 2
4 7
9 9

SAMPLE OUTPUT:

2

One way to achieve D=2D=2 is to have cows at positions 00224466 and 99.

 

SCORING:

 

  • Test cases 2-3 satisfy b105.b≤105.
  • Test cases 4-10 satisfy no additional constraints.

Problem credits: Brian Dean

USACO 2020 US Open Contest, Silver Problem 1. Social Distancing 题解(翰林国际教育提供,仅供参考)

题解请注册登录查看

[/hide]

(Analysis by Benjamin Qi)

Sort the intervals from left to right and binary search on the separating distance DD. For a fixed DD we want to check whether we can place at least NN cows. This can be done with a greedy strategy; just place each cow at the leftmost position possible. Once the number of cows placed reaches NN we can break, so a single DD can be checked in O(N+M)O(N+M) time. Thus, the entire solution runs in O((N+M)log(max dist))O((N+M)log⁡(max dist)) time.

Mark Chen's code:

 

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
#define INF 2000000000
#define FF first
#define SS second

int n, m;
 
vector<pair<LL,LL>> intervals;
 
bool ok(LL d) {
    LL prev = -1LL * INF * INF;
    
    int cnt = 0;
    for (auto& i : intervals) {
        while (max(prev + d, i.FF) <= i.SS) {
            prev = max(prev + d, i.FF);
            cnt++;
            if (cnt >= n) break;
        }
        if (cnt >= n) break;
    }
 
    return (cnt >= n);
}
 
int main() {
    freopen("socdist.in","r",stdin);
    freopen("socdist.out","w",stdout);
    cin >> n >> m;

    intervals.resize(m);
    for (int i = 0; i < m; ++i) 
        cin >> intervals[i].FF >> intervals[i].SS;
 
    sort(intervals.begin(), intervals.end());
 
    LL lo = 1;
    LL hi = 1LL * INF * INF;
    LL res = -1;
 
    while (lo <= hi) {
        LL mid = (lo + hi) / 2;
 
        if (ok(mid)) {
            res = mid;
            lo = mid + 1;
        }
        else {
            hi = mid - 1;
        }
    }
 
    cout << res << "\n";
}

[/hide]

翰林国际教育资讯二维码