задачка

[109]

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

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

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

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

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

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

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

Comments

[ralan.livejournal.com]

пример с картинками :

1001 1010
0100 еще один пример 0110
0011 0010 - звезда
0011 - возможно звезда 0101

где i,i - всегда 1 потому как сам себя то человек должен знать. Теперь, мы пилим по первой строке начиная от второго числа (т.к. сам себя он знает, поэтому в рассчет его не берем). Пилим до первой единицы - т.е. понятно, что данный человек не является звездой и переходим к тому, кого он знает (т.е. по нашей картинке, если он не знает ни 2, ни 3 - значит они не звезды - значит они сразу отпадают. А последний - четвертый , единственный возможный вариант звезды. Теперь - цикл не двойной, достаточно внимательно в него посмотреть, т.к. изменение Ай зависит не только от итератора Ай , но и от Итератора Джей. Поэтому этот цикл О(Н)).
Ступенчатое продвижение.

[109.livejournal.com]

изменение Ай производится только в одном месте, i++, поэтому изменение Ай никак от Джей не зависит. изменение Джей во вложенном цикле производится от i+2 до N, так что из кода следует O(N^2), как ни крути. если каким-то волшебным образом у вас есть шорткат, то это надо объяснить словами. слова у вас такие: "Пилим до первой единицы - т.е. понятно, что данный человек не является звездой и переходим к тому, кого он знает" - до этого места понятно. перешли к тому, кого он знает. то есть поменяли номер строки. что мы делаем с новой строкой?

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