polytheme: вспомнил простую, но милую задачу из КЛР

вспомнил простую, но милую задачу из КЛР
есть n микросхем, которые умеют тестировать друг друга. некоторые микросхемы бракованные. в парном тесте две микросхемы тестируют друг друга. небракованная микросхема говорит про другую из пары правильно, бракованная она или нет. бракованная может говорить что угодно.
тогда
а) если больше половины микросхем бракованные, установить, какие из них какие, парными тестами нельзя
б) если меньше половины микросхем бракованные, то можно установить, какие из них какие, за O(n) парных тестов.

(Добавить комментарий)

lenkasm
2015-02-24 04:40 (ссылка)

пусть бракованных k, рабочих тогда n-k

а) разделим k бракованных на группу А из n-k бракованных и группу Б из остальных бракованных. Назовем группой С рабочие микросхемы (группы С и А одинаковы по количеству микросхем)
Микросхемы группы А будут называть рабочей любую микросхему из группы А и бракованной все остальные микросхемы. Группа Б будет голосовать "против всех" микросхем, т.е. любую опознавая как брак.
Если группу А и С поменять местами, то есть в А все сделать рабочими, а в С все бракованными, то результаты всех тестов останутся прежними. Следовательно, определить, где рабочии микросхемы - в группе А или в С невозможно.

(Ответить) (Ветвь дискуссии)

	polytheme 2015-02-24 12:12 (ссылка)
	ага, right (Ответить) (Уровень выше)

lenkasm
2015-02-26 01:04 (ссылка)

b) найдем одну правильную микросхему за O(n), и тогда ею за O(n) проверим все остальные:

поделим множество микросхем произвольно на пары,

если будет лишняя микросхема, то ее отложим;
заставим каждую пару проверить друг друга

если в какой-то паре хотя бы один результат "брак", то в этой паре хотя бы одна микросхема бракованная
поэтому отбросим все такие пары с браком, и получим множество пар, которые друг о друге отзываются хорошо
если это множество пар пусто, то отложенная микросхема - рабочая, иначе бы кол-во хороших было бы меньше кол-ва плохих

в каждой из оставшихся пар либо обе микросхемы рабочие, либо обе бракованные
наберем по одной микросхеме из каждой пары в новое множество микросхем

если в новом множестве нечетное кол-во микросхем, то хороших там снова больше, чем плохих,
иначе бракованных пар было бы больше и соответственно бракованных микросхем тоже больше

если в новом множестве четное кол-во микросхем, добавим туда отложенную микросхему
если до добавления там было одинаковое кол-во хороших и плохих, то отложенная микросхема была хорошая и после ее добавления стало больше хороших, чем плохих
если до добавления отложенной микросхемы хороших было больше, то и после добавления их останется больше, даже если отложенная микросхема была плохой
мы возвращаемся в начало и делаем по новой, пока не останется одна микросхема, она будет хорошей

кол-во итераций
2n + 2n/2 + ... + 2n/i^2 + ... 2n/k^2 = 2n*(1 + 1/2 + ... + 1/k^2) < 2n * 2

(Ответить)