TopCoder problem "CommunicableDisease" used in SRM 232 (Division I Level Two)



Problem Statement

    

Students in a science class are simulating the spread of communicable disease with a simple experiment. At the start of the experiment, each student receives a vial of liquid, which may or may not be contaminated. (It is not known whether or not it is contaminated.) The vials are numbered 0 through n-1, where n is the number of students participating.

In several successive rounds of contact, each student adds a sample from their vial to that of another student, or chooses to abstain from contact by adding the sample back to his own vial. These rounds of contact are repeated several times, with each round being completed before the next begins. Note that during each round, all contact happens simultaneously (you can think about it as some liquid being taken out of each vial before any is added to any vial). After several rounds of contact, each student's vial is tested for the presence of the contamination, to visually see just how quickly and easily a disease can spread.

You are given a String[], contact, indicating to whom samples were given in each round. The i-th element of contact indicates the vial to whom student i gave a sample in each round. Each element of contact will be a space-delimited list of integers with no leading zeros. Each number represented will be between 0 and n-1, where n is the number of students. You are also given a String, results. Each character of results will be either 'C' or 'N', representing "contaminated" or "not contaminated". The zero-based index of each character corresponds to the number on the vial.

We want to determine, to the best of our ability, which vials were originally contaminated. You are to return a String indicating this information. Each character of the return value should be 'C', 'N', or 'I', indicating vials that were definitely contaminated, definitely not contaminated, or if it is inconclusive. The i-th character of the return value corresponds to the i-th vial. If the value of results is impossible given the data in contact, your method should return "INVALID", to indicate that something must have gone wrong in the experiment.

 

Definition

    
Class:CommunicableDisease
Method:findSource
Parameters:String[], String
Returns:String
Method signature:String findSource(String[] contact, String results)
(be sure your method is public)
    
 

Notes

-An element contact may include the same number more than once. That is, a sample can be given from the a vial to another vial more than once.
 

Constraints

-contact will have between 2 and 50 elements, inclusive.
-Each element of contact will have between 1 and 50 characters, inclusive.
-Each element of contact will be formatted as a space-delimited list of integers (with no leading zeros) between 0 and n-1, inclusive, where n is the number of elements in contact.
-Each element of contact will represent between 1 and 10 integers, inclusive.
-Each element of contact will have the same number of integers represented within.
-The character length of results will be same as the number of elements in contact.
 

Examples

0)
    
{"1", "2", "0"}
"CCN"
Returns: "CNN"
This is a simple example with three people. Each passes to the person next to them. Since the last person is non-contaminated at the end, he couldn't have been contaminated to begin with. Likewise, the middle person who gave them a sample could not have been contaminated. By elimination the first person must have been contaminated.
1)
    
{"1 7", "2 0", "3 1", "4 2", "5 3", "6 4", "7 5", "0 6"}
"CCCNNNNN"
Returns: "NCNNNNNN"
Here, only the second person started out infected, but gave it to both adjacent people.
2)
    
{"1 7", "0 2", "3 1", "4 2", "5 3", "6 4", "7 5", "0 6"}
"CCCNNNNC"
Returns: "IINNNNNN"
This is similar to above, but notice now that we can't be sure of the source.
3)
    
{"1 7 3", "0 2 5", "3 1 6", "4 2 7", "5 3 0", "6 4 1", "7 5 2", "0 6 3"}
"CCCCCCCC"
Returns: "IIIIIIII"
With lots of interaction, it's impossible to know where the infection started.
4)
    
{"1", "0"}
"CN"
Returns: "INVALID"
Here, it's not hard to work out why the results are impossible. If either started infected, both should be after swapping samples. If neither started infected, neither should be at the end.
5)
    
{"0", "2", "1"}
"CNN"
Returns: "CNN"
By only giving samples to his own vial, the first person avoids infecting anyone else.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3924

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6521&pm=3924

Writer:

timmac

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Brute Force, Recursion, Search