задачка

[109]

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

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

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

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

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

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

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

Comments

[109.livejournal.com]

ну ты крут, за пять минут. впрочем, я не сомневался, что ты решишь. моя формулировка решения была практически такой же, только чуть короче:

a[i,j] xor a[j,i] = 0: выкидываем обоих, иначе
a[i,j] = 1: выкидываем i, иначе
выкидываем j.