Detecting lies from clues

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.
Last edited on
Given that N<=1000 I think that a O(n^2) solution would suffice.

Each query has O(n) because you perform a linear search, at most N queries may be made, so O(n^2), good.

The update would depend on the sizes of the lists being merged. Because you also need to update each member list, the total time for an update is O(L*M), so it would perform better if L<<M and worst if L=M.
Considering the worst case, you'll make n/2 operations on sets of size 1, n/4 on size 2, n/8 on size 4, n/16 on size 8... adding all it gives O(n^2)

Perhaps I made a mistake in the analysis, but it seems that your solution should work.


As an improvement
1
2
3
4
5
6
7
struct animal
{
std::bitset<1000>
	dom_list,	// Animal Y is in Animal X's dom list if X eats Y
	same_list,	// Animal Y is in Animal X's same list if X and Y are the same kind
	sub_list;	// Animal Y is in Animal X's sub list if Y eats X
}A[1000];
that way you may have O(1) query time, and no reallocations.
The merging may be done with an bit_or operation, that may be optimized.
Thank you very much :)
Topic archived. No new replies allowed.