Home » 国际竞赛 » Details

USACO 2020 US Open Contest, Bronze Problem 3. Cowntact Tracing

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月6日下午5:37

USACO 2020 US Open Contest, Bronze Problem 3. Cowntact Tracing

Farmer John is worried for the health of his cows (conveniently numbered $1 \dots N$ as always) after an outbreak of the highly contagious bovine disease COWVID-19.

Recently, Farmer John tested all of his cows and found some of them to be positive for the disease. Using video footage from inside his barn, he is able to review recent interactions between pairs of cows --- it turns out that when cows greet each-other, they shake hooves, a gesture that can unfortunately spread the infection from one cow to another. Farmer John assembles a time-stamped list of interacting pairs of cows, with entries of the form $(t, x, y)$ , meaning that at time $t$ , cow $x$ shook hooves with cow $y$ . Farmer John also knows the following:

(i) Exactly one cow on his farm could have started out carrying the disease (we'll call this cow "patient zero").

(ii) Once a cow is infected, she passes the infection along with her next $K$ hoof shakes (possibly including the same partner cow several times). After shaking hooves $K$ times, she no longer passes the infection along with subsequent hoof shakes (since at this point she realizes she is spreading the infection and washes her hooves carefully).

(iii) Once a cow is infected, she stays infected.

Unfortunately, Farmer John doesn't know which of his $N$ cows is patient zero, nor does he know the value of $K$ ! Please help him narrow down the possibilities for these unknowns based on his data. It is guaranteed that at least one possibility is valid.

INPUT FORMAT (file tracing.in):

The first line of the input file contains $N$ ( $2 \leq N \leq 100$ ) and $T$ ( $1 \leq T \leq 250$ ). The next line contains a string of length $N$ whose entries are 0s and 1s, describing the current state of Farmer John's $N$ cows --- 0 represents a healthy cow and 1 represents a cow presently with the disease. Each of the next $T$ lines describes a record in Farmer John's list of interactions and consists of three integers $t$ , $x$ , and $y$ , where $t$ is a positive integer time of the interaction ( $t \leq 250$ ) and $x$ and $y$ are distinct integers in the range $1 \dots N$ , indicating which cows shook hands at time $t$ . At most one interaction happens at each point in time.

OUTPUT FORMAT (file tracing.out):

Print a single line with three integers $x$ , $y$ , and $z$ , where $x$ is the number of possible cows who could have been patient zero, $y$ is the smallest possible value of $K$ consistent with the data, and $z$ is the largest possible value of $K$ consistent with the data (if there is no upper bound on $K$ that can be deduced from the data, print "Infinity" for $z$ ). Note that it might be possible to have $K = 0$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

1 1 Infinity

The only candidate for patient zero is cow 1. For all $K > 0$ , cow 1 infects cow 2 at time 7, while cows 3 and 4 remain uninfected.

Problem credits: Brian Dean

USACO 2020 US Open Contest, Bronze Problem 3. Cowntact Tracing 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Jonathan Paulson)

This problem can be solved by brute force - just try all possible combinations of which cow is patient zero and the value of $K$ . There are $N$ choices for patient zero, and $K$ can be from $0$ up to $T$ ( $K$ > $T$ behaves the same as $K = T$ ). Simulating the course of the infection for each possible combination takes $O (T)$ time. So the total runtime is $O (N T^{2})$ - approximately 6.25M steps - which is fine.

See the solution code for how to simulate the infection given the choice of patient zero and $K$ . Surprisingly short! For each simulated infection, we need to check if the cows that get infected during the simulation are the same cows that are actually infected; if so, those choices of patient zero and $K$ are valid possibilities.

Once you find all the possibilities, we just need to report the number of cows that could've been patient zero and the minimum and maximum possible values of $K$ ("infinity" if $K = T$ is possible). Notice that different patient zeros might give different possible ranges of $K$ ; in particular, the minimum and maximum values might only be possible for different choices of patient zero.

Brian Dean's solution:

#include <iostream>
#include <fstream>
using namespace std;
 
bool cow_ends_infected[101];
int N, cowx[251], cowy[251]; // handshake data (0 if no handshake at time t)
 
// Simulate handshakes over time to see if data agrees with this choice of patient_zero and K...
bool consistent_with_data(int patient_zero, int K)
{
  bool infected[101] = {false};
  int num_handshakes[101] = {0};
  infected[patient_zero] = true;
  for (int t=0; t<=250; t++) {
    int x = cowx[t], y = cowy[t];
    if (x>0) {
      if (infected[x]) num_handshakes[x]++;
      if (infected[y]) num_handshakes[y]++;
      if (num_handshakes[x] <= K && infected[x]) infected[y] = true;
      if (num_handshakes[y] <= K && infected[y]) infected[x] = true;
    }
  }
  for (int i=1; i<=N; i++)
    if (infected[i] != cow_ends_infected[i]) return false;
  return true;
}
 
int main(void)
{
  int T, t, x, y;
  string s;
 
  ifstream fin ("tracing.in");
  fin >> N >> T >> s;
  for (int i=1; i<=N; i++)
    cow_ends_infected[i] = s[i-1]=='1';
  for (int i=0; i<T; i++) {
    fin >> t >> x >> y;
    cowx[t] = x;
    cowy[t] = y;
  }
 
  bool possible_i[101] = {false};
  bool possible_K[252] = {false};
  for (int i=1; i<=N; i++)
    for (int K=0; K<=251; K++)
      if (consistent_with_data(i, K)) 
	possible_i[i] = true; possible_K[K] = true;
 
  int lower_K=251, upper_K=0, num_patient_zero=0;
  for (int K=0; K<=251; K++) if (possible_K[K]) upper_K = K;
  for (int K=251; K>=0; K--) if (possible_K[K]) lower_K = K;
  for (int i=1; i<=N; i++) if (possible_i[i]) num_patient_zero++;
 
  ofstream fout ("tracing.out");
  fout << num_patient_zero << " " << lower_K << " ";
  if (upper_K==251) fout << "Infinity\n";
  else fout << upper_K << "\n";
 
  return 0;
}

[/hide]