задачка

[109]

чувак клянётся, что это реальная задачка с нашего интервью. итак:

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

отношения участников вечеринки заданы в виде квадратной таблицы, где ячейка (i, j) содержит 1, если i знает j и 0, если не знает.

спрашивается, как за O(N), где N - количество народа на вечеринке, найти, есть ли знаменитость, и кто она.

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

(я сам задачку услышал вчера, немного поломал голову и плюнул, а сегодня из глубин подсознания сам собой всплыл ответ)

Update: всё расскриниваю ввиду большого количества правильных ответов. чуть попозже выкину обзор типов ответов.

Comments

[ygam.livejournal.com]

У меня получился рандомизированный алгоритм со временем работы O(N log N).

Пускай число отношений "один человек знает другого" - M. 0≤M≤N². Пусть k = M/N. 0≤k≤N.

Создадим массив из N булевых - кандидатов в знаменитости. Инициализируем его всеми true.

Выберем случайного человека и исключим из кандидатов во-первых, всех, кого он не знает, а во-вторых, всех, кто знает его. Эта процедура займет O(N) операций. В среднем человек знают k людей, а не знают N-k; доля тех людей, кого он не знает, среди всех 1-k/N. В среднем человека знают k людей; доля тех, кто знает его, среди всех k/N. Мы умножили число кандидатов на (1-k/N)*(k/N).

Функция f(k) = (1-k/N)*(k/N) имеет минимум 0 (при k=0 или k=N) и максимум 1/4 (при k=N/2). Мы сокращаем число кандидатов в 4 раза.

Будем повторять, пока число кандидатов не станет нулем или единицей.

[109.livejournal.com]

O(N log N) indeed. но вам на самом деле, кажется, теперь уже недолго осталось до нахождения O(N) алгоритма.