Hi guys,
I came across this problem from a Bloomberg Codecon coding contest.
Truths of Predation
Memory Limit: 1024MB Runtime Limit: 5s Score: 300
On planet Dorne in galaxy Harrenhal, there exist three types of animals: Wampa, Nexu and Tribble. Wampa can eat Nexu, Nexu can eat Tribble, and Tribble can eat Wampa.
Dorne has N animals, numbered from 1 to N, which are each one of the 3 types.
A troll named Horda will tell you K clues about these animals. Each piece of information has one of the two forms below:
1 X Y : this tells you that x and y are of the same type
2 X Y : this tells you that x can eat y
Being a troll, some of the clues given are false. The clue is false if it satisfies any of the three conditions below, otherwise it's true:
X or Y is larger than N
The clue states X can eat X
The clue conflicts with a true clue before
Your task is to process all clues and detect the number of false clues.
Input Specifications
The first line will contain a number N ( 1 <= N <= 1000 ) denoting the number of animals on Dorne and K (1 <= K <= 1000 )
denoting the number of clues Harda will provide. This will be followed by K lines, each with three positive integers. The first number C (1 <= C <= 2) will tell you which type of clue this is, followed by X and Y (1 <= X,Y <= N).
Output Specifications
Your program will output a single integer denoting the number of false clues provided by the troll.
Sample Input/Output
INPUT
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
OUTPUT
3
EXPLANATION
The 1st, 4th and 5th clues are false.
So what I did here was to create a structure animal that has three lists, namely dom, sub and same. If X eats Y, X's dom list gets Y, and Y's sub list gets X. And if X and Y are of the same kind, their same lists get each other. Also, depending on whether X ate Y or X and Y were of the same kind, the animals in each of their lists had their own lists updated as well.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
|
struct animal
{
vector<int> dom_list; // Animal Y is in Animal X's dom list if X eats Y
vector<int> same_list; // Animal Y is in Animal X's same list if X and Y are the same kind
vector<int> sub_list; // Animal Y is in Animal X's sub list if Y eats X
}A[1000]; // struct containing three lists - dom, sub and same
void acopy(animal &A1, animal &A2, char ch); // copies the contents of A1 to A2 with the ch parameter determining the source list and destination list
void duplicate(vector<int> &dup); // removes duplicate elements from vector
int search(vector<int> list, int val); // searches for a value in the vector (linear search)
int main()
{
int N, K, clue[1000][3], i, j, lie = 0;
cin >> N >> K;
for (i = 0; i < K; ++i) // Input clues in a K x 3 matrix
for (j = 0; j < 3; ++j)
cin >> clue[i][j];
//Animals are stored in the array A[1000] numbered from 1 to 1000.
//However since the indices of an array go from 0 to 999, 1 is subtracted from the animal's number where necessary.
//If animal 40 eats animal 80, then A[39] has the number 80 in its dom_list, and A[79] has the number 40 in its sub_list.
cout << "\n";
//Parsing
for (i = 0; i < K; ++i)
if ((clue[i][1] > N) || (clue[i][2] > N))
cout << ++lie << ". Clue #" << i + 1 << "\n";
else if ((clue[i][0] == 2) && clue[i][1] == clue[i][2])
cout << ++lie << ". Clue #" << i + 1 <<"\n";
else
{
if (clue[i][0] == 1) // To be of the same type
{
if (search(A[clue[i][1] - 1].dom_list, clue[i][2]) || search(A[clue[i][1] - 1].sub_list, clue[i][2])) // Lie if in dom_list or sub_list
cout << ++lie << ". Clue #" << i + 1 << "\n";
else
{
A[clue[i][1] - 1].same_list.push_back(clue[i][2]); //A1's same list
A[clue[i][2] - 1].same_list.push_back(clue[i][1]); //A2's same list
acopy(A[clue[i][1] - 1], A[clue[i][2] - 1], 'g'); //copy A1's dom to A2's dom
for (j = 0; j < A[clue[i][2] - 1].dom_list.size(); ++j) //copy to same list of all members of A2's dom list
acopy(A[clue[i][1] - 1], A[A[clue[i][2] - 1].dom_list[j] - 1], 'e');
for (j = 0; j < A[clue[i][2] - 1].sub_list.size(); ++j) //copy to sub list of all members of A2's sub list
acopy(A[clue[i][1] - 1], A[A[clue[i][2] - 1].sub_list[j] - 1], 'c');
for (j = 0; j < A[clue[i][2] - 1].same_list.size(); ++j) //copy to dom list of all members of A2's same list
acopy(A[clue[i][1] - 1], A[A[clue[i][2] - 1].same_list[j] - 1], 'g');
//copy A1's sub to A2's sub
//copy to dom list of all members of A2's dom list
//copy to same list of all members of A2's sub list
//copy to sub list of all members of A2's same list
//copy A1's same to A2's same
//copy to sub list of all members of A2's dom list
//copy to dom list of all members of A2's sub list
//copy to same list of all members of A2's same list
//for A1
//copy A2's dom to A1's dom
//copy to same list of all members of A1's dom list
//copy to sub list of all members of A1's sub list
//copy to dom list of all members of A1's same list
//copy A2's sub to A1's sub
//copy to dom list of all members of A1's dom list
//copy to same list of all members of A1's sub list
//copy to sub list of all members of A1's same list
//copy A2's same to A1's same
//copy to sub list of all members of A1's dom list
//copy to dom list of all members of A1's sub list
//copy to same list of all members of A1's same list
}
}
else if (clue[i][0] == 2) // To eat
{
if (search(A[clue[i][1] - 1].same_list, clue[i][2]) || search(A[clue[i][1] - 1].sub_list, clue[i][2])) // Lie if present in same list or sub list
cout << ++lie << ". Clue #" << i + 1 << "\n";
else
{
// code to copy to respective lists similar to above
}
}
else
cout << "Error\n";
}
cout << "\n\nLie count: " << lie << "\n";
system("pause");
}
|
To detect lies, say I had X ate Y, Y ate Z, and X ate Z, I could easily do a linear search of Y in X's same and sub lists to find Z, thus rendering the third clue false. Similarly, for X and Y to be of the same kind, I'd do a linear search of Y in X's dom and sub lists.
The entire code is a bit too long to fit in one post, and hence I've just included the comments since the code is very similar to the loops shown.
Also, I feel that this solution is too time-consuming for a coding contest, so suggestions for alternate approaches are appreciated.