USACO 2020 US Open Contest, Bronze Problem 2. Social Distancing II

USACO 2020 US Open Contest, Bronze Problem 2. Social Distancing II

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

Despite his best attempt at making his NN cows (1≤N≤10001≤N≤1000) practice "social distancing", many of them still unfortunately contracted the disease. The cows, conveniently numbered 1…N1…N, are each standing at distinct points along a long path (essentially a one-dimensional number line), with cow ii standing at position xixi. Farmer John knows that there is a radius RR such that any cow standing up to and including RR units away from an infected cow will also become infected (and will then pass the infection along to additional cows within RR units away, and so on).

Unfortunately, Farmer John doesn't know RR exactly. He does however know which of his cows are infected. Given this data, please determine the minimum possible number of cows that were initially infected with the disease.

 

 

 

SAMPLE INPUT:

6
7 1
1 1
15 1
3 1
10 0
6 1

SAMPLE OUTPUT:

3

In this example, we know that R<3R<3 since otherwise the cow at position 7 would have infected the cow at position 10. Therefore, at least 3 cows must have started out infected -- one of the two cows at positions 1 and 3, one of the two cows at positions 6 and 7, and the cow at position 15.

 

Problem credits: Brian Dean

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

题解请注册或登录查看

[/hide]

(Analysis by Jonathan Paulson and Brian Dean)

We should assume that RR is as large as possible so as to minimize the number of initial infections required. The largest RR could be is one less than the smallest gap between a healthy cow and an infected cow (if RR were any larger, the healthy cow would've been infected). Assume this is the true value of RR. (If there are no healthy cows, assume R=∞R=∞). By considering all pairs of cows, we can find RR in O(N2)O(N2) time. Alternatively, as in the code below, we can mark the locations of all cows and look at all the gaps between adjacent cows, with one being health and the other sick (another similar approach would involve sorting the cows by position first, then looking at the same gaps).

Having determined RR, we next need to figure out the number of initially sick cows. Any block of sick cows within which neighboring cows are at most RR apart could have arisen from just a single sick cow. Hence, we count the number of "blocks" of sick cows (contiguous groups of sick cows delineated by a healthy cow) and then break up these blocks whenever we find a pair of adjacent sick cows within a block at distance RR or larger. This leaves groups of cows that could have each been infected from a single initial cow.

Here is Brian Dean's solution:

#include <iostream>
#include <fstream>
using namespace std;
 
int N, A[1000001]; // 1=healthy, -1=sick, 0=no cow
 
// Returns size of largest gap between a health and a sick cow
int find_smallest_01_gap(void)
{
  int smallest_gap = 2000000, current_start = -1;
  for (int i=0; i<=1000000; i++) 
    if (A[i] != 0) {
      if (current_start!=-1 && A[current_start]!=A[i] && i-current_start<smallest_gap) 
	smallest_gap = i-current_start;
      current_start = i;
    }
  return smallest_gap;
}
 
// Number of blocks of sick cows, delineated by healthy cows
int num_sick_clusters(void)
{
  int last_state = 0, answer = 0;
  for (int i=0; i<=1000000; i++) 
    if (A[i] != 0) {
      if (A[i] != last_state && A[i] == 1) answer++;
      last_state = A[i];
    }
  return answer;
}
 
// Number of gaps of size r or larger within blocks of sick cows
int num_sick_gaps(int r)
{
  int answer = 0, current_start = 0;
  for (int i=0; i<=1000000; i++) 
    if (A[i] != 0) {
      if (current_start!=0 && A[current_start]==1 && A[i]==1 && i-current_start>=r) 
	answer++;
      current_start = i;
    }
  return answer;
}
 
int main(void)
{
  ifstream fin ("socdist2.in");
  int x, s;
  fin >> N;
  for (int i=0; i<N; i++) {
    fin >> x >> s;
    if (s==1) { A[x] = 1; }
    if (s==0) { A[x] = -1; }
  }
  ofstream fout ("socdist2.out");
  int r = find_smallest_01_gap();
  fout << num_sick_clusters() + num_sick_gaps(r) << "\n";
  return 0;
}

[/hide]