cppAcademy
FROM LEARNING TO COMPETING

Real problems.
Your next challenge.

Explore the Group C Olympiad archive.
Choose a topic. Find a challenge. Build your solution.

213 tasks across the Municipal, Regional, and National rounds (2009–2026), plus 4 previously featured problems. 146 tasks have independently written English summaries, analyses, and C++17 solutions; the remaining entries link to Arena. Topic tags are from Arena or our reviewed explanations. Difficulty labels are learning estimates, not official ratings.
GROUP C2012 · MediumBinary Search Answer

Gathering Sheep

National Olympiad — National round

Submission name: graze.cpp

Solve in Editor →

Problem summary

Assign every sheep on a number line to a shelter of capacity K. Sheep move simultaneously at unit speed. Minimize the time by which all are sheltered, or report impossible. Sheep and shelters may share coordinates.

Input

N M K; N sheep coordinates; M shelter coordinates.

Output

The minimum integer time, or −1 if no assignment exists.

Constraints

1 ≤ N,M,K ≤ 100,000; coordinates 1…1,000,000. Half the tests have N,M≤1000.

Worked example

An independently prepared example for this explanation.

Input

3 2 2
1 4 8
2 7

Output

2

Solution analysis

  1. If M·K<N no assignment is possible. Otherwise sort both coordinate lists and binary-search the maximum allowed travel distance D.
  2. For each shelter from left to right, assign up to K earliest unassigned sheep within distance D. If the earliest sheep lies left of the shelter minus D, no later shelter can help it.
  3. The feasibility predicate is monotone, so binary search returns the smallest feasible distance.

Why it works

Crossing assignments can be uncrossed without increasing the maximum travel distance on a line. Thus there is a noncrossing optimum, and filling the earliest available shelter with the earliest compatible sheep cannot harm feasibility.

Complexity: O(N log N+M log M+(N+M) log C) time and O(N+M) memory, C=1,000,000.

Watch out. Multiple shelters at the same coordinate have independent capacities. Use 64-bit for M·K.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: Crossing assignments can be uncrossed without increasing the maximum travel distance on a
// line. Thus there is a noncrossing optimum, and filling the earliest available shelter with the
// earliest compatible sheep cannot harm feasibility.
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<iterator>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k;
    cin>>n>>m>>k;
    vector<int>s(n),b(m);
    for(int&x:s){
        cin>>x;
    }
    for(int&x:b){
        cin>>x;
    }
    if(1LL*m*k<n){
        cout<<-1<<'\n';
        return 0;
    }
    sort(s.begin(),s.end());
    sort(b.begin(),b.end());
    auto feasible=[&](int d){
        int i=0;
        for(int x:b){
            if(i<n&&s[i]<x-d){
                return false;
            }
            int used=0;
            while(i<n&&used<k&&s[i]<=x+d){
                i++;
                used++;
            }
        }
        return i==n;
    };
    int lo=0,hi=1000000;
    while(lo<hi){
        int mid=(lo+hi)/2;
        if(feasible(mid)){
            hi=mid;
        }
        else{
            lo=mid+1;
        }
    }
    cout<<lo<<'\n';
}

Source: Arena Olimpiici ↗