Find the "Initial Patient" of a disease using code.

Can anyone help with this problem? It's a last in a set of challenge problems I've finished the other problems for, and I really don't know where to even begin for this problem. If anyone has an idea for an algorithm or a program to do it, I would highly appreciate it if you could share it with me.

Farmer John is worried for the health of his cows (conveniently numbered 1…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.

The first line of the input file contains N (2≤N≤100) and T (1≤T≤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≤250) and x and y are distinct integers in the range 1…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.
4 3
7 1 2
5 2 3
6 2 4
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.
Last edited on
Like all problems, you start with the simplest one you can imagine and work your way up from there one cow and/or hoof shake at a time until you figure out the problem.

1 cow
2 cows, no hoof
2 cows, 1 hoof
3 cows, 1 hoof
etc etc etc.

Just copy/pasting/mooing the problem from one website to another does nothing for you.
I've already tried multiple scenarios, but I can't seem to deduce any pattern. Do you have any ideas on a solution?
I've only thought of throwing out the cases where two healthy cows interact, but I don't know how to proceed with the health/sick cow and sick/sick cow interactions. But I still can't get my mind around what I knowledge I can gain from these interactions.
Last edited on
Topic archived. No new replies allowed.