I second Bhavesh.
If A knows B, then B is not a spy; else A is not a spy.
Thus we can hold an elimination races:
for each pair A,B in a match, ask if A knows B, and eliminate as
above.
In total N-1 matches are needed to decide the final winner.
If there is a spy, then the spy is the winner.
Otherwise, Another 2N-2 queries are needed to check if the winner is a spy.
(or 2N-2-logN, making use of the results of previous matches)
On 2010-12-21 22:39, janak wrote:
O(N) if everybody knows everybody.
O(N^2) if there is no such condition. (i.e. Ask for each person to
everybody.)
On Mon, Dec 20, 2010 at 9:43 PM, Bhavesh Chauhan
<[email protected] <mailto:[email protected]>> wrote:
Every question can eliminate 1 person so you can identify the spy
in N-1 questions.
Bhavesh
On 19 December 2010 23:46, Dave <[email protected]
<mailto:[email protected]>> wrote:
Here is an algorithm:
spy = 1
for i = 2 to N do
if person[spy] knows person[i]
then person[i] is not the spy.
else if person[i] knows person[spy]
then person[spy] is not the spy, set spy = i
end if
end for
for i = 1 to spy-1 do
if (person[spy] does not know person[i]) or (person[i] knows
person[spy])
then there is no spy, set spy = undefined, break
end if
end for
If there is a spy, you find him in at least 2*N - 2 questions
and at
most 4*N - 4 questions.
Dave
On Dec 19, 8:01 am, snehal jain <[email protected]
<mailto:[email protected]>> wrote:
> There is a city of N people. The government learnt that some
> unfriendly nation planted a spy there. A spy possesses unique
> characteristics: he knows everybody in the city, but nobody
knows him.
>
> You are a counteragent sent by the government to catch the
spy. You
> may ask the people in the city only one question: "Do you
know the
> person X?" You may ask as many people as you wish, and one
person may
> be asked as many times as you wish. All the people,
including the spy,
> always answer honestly.
>
> How many questions you need to find out who is the spy?
--
You received this message because you are subscribed to the
Google Groups "Algorithm Geeks" group.
To post to this group, send email to
[email protected] <mailto:[email protected]>.
To unsubscribe from this group, send email to
[email protected]
<mailto:algogeeks%[email protected]>.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected]
<mailto:[email protected]>.
To unsubscribe from this group, send email to
[email protected]
<mailto:algogeeks%[email protected]>.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
