We should assume that $R$ is as large as possible so as to minimize the number of initial infections required. The largest $R$ could be is one less than the smallest gap between a healthy cow and an infected cow (if $R$ were any larger, the healthy cow would've been infected). Assume this is the true value of $R$. (If there are no healthy cows, assume $R=\infty$). By considering all pairs of cows, we can find $R$ in $O(N^2)$ 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 $R$, we next need to figure out the number of initially sick cows. Any block of sick cows within which neighboring cows are at most $R$ 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 $R$ 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; }