Geek Answers Handbook

The fastest algorithm to find the maximum (n / 2) -1 liars in Russian people

Here is my scenario:

This problem is formulated in terms of liars and likelihood counters, but it has real applications to determine which components of a complex system are good (functioning correctly) and which are erroneous. Suppose we have a community of Russian people, and we know the integer t <n / 2, which has the property that most Russian people are liars. This does not mean that there are actually t liars, but only that there are no more than t liars.

I suppose that truthists are always truthful and correct, and a liar can say the wrong answer or the right answer.

We identify liars in the community by consistently gathering pairs of people (X, Y) and asking X: Is a liar ?. The answer will be either yes or no;

What is the optimal algorithm (minimum number of steps) to find all the liars?

+5
source share
5 answers

A random algorithm with optimal expected operating time O (n) and excellent constants:

  • Choose a random face
  • Ask the rest of the people if he is a liar until one of the options (“yes” or “no”) has weight> n / 2 (i.e. until more than n / 2 people give the same answer) .
    Most decide (this is a key point!).
  • , , ( , ).
  • , 1.

, , , ( -). , , , , 50-50, , ? , 50-50, -, , , .

, , O (1) ( , , , : ), , O (1) * O (n) , O (n) . O (n).

+7

, . , . , .

G - . , X . , X " Y ?" "", X Y - "" . , X " Y ?" Y G ( X) , Y X. , , , , "" X , .

+3

Pseudo code for my solution, which is basically the same as Devin's solution. One noticeable difference is that you only need to agree with the maximum possible other + 1 liars.

set unknown = all
set known_true = {}
set known_lie = {}

while known_true.is_empty()
  voted_lie = {}
  voted_true = {}
  truth_votes = 0
  lie_votes = 0
  to_check = unknown.get(0)
  while truth_votes < t - known_lie.size() + 1 && lie_votes < t - known_lie.size() + 1:
    checker = unknown.get_next()
    if checker.is_liar(to_check):
      lie_votes++
      voted_lie.add(checker)
    else
      truth_votes++
      voted_true.add(checker)

  if truth_votes > t + 1:
    unknown.remove(to_check)
    known_true.add(to_check)
    known_lie.add_all(voted_lie)
    unknown.remove_all(voted_lie)
  else:
    unknown.remove(to_check)
    known_lie.add(to_check)
    known_lie.add_all(voted_true)
    unknown.remove_all(voted_true)


while not unknown.is_empty() && known_liar.size() < t:
  to_check = unknown.get(0)
  if known_true.get(0).is_liar(to_check):
    unknown.remove(to_check)
    known_lie.add(to_check)
  else
    unknown.remove(to_check)
    known_true.add(to_check)
+1
source

If you request all pairs, then the true counters are displayed as a unique maximum click size> n / 2. I will leave this for those handy porting homework that needs to be optimized.

0
source

More articles:


All Articles