задачка

[109]

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

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

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

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

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

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

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

Comments

[http://users.livejournal.com/_dyn/]

Я эту задачку у нас на студии на кухне вывешивал с полгода назад.
Хорошая задачка, да :))

[avoider.livejournal.com]

Надо залезть в учебник по дискретке и почитать теорию графов.
Проблема в том, что вот эту оценку сложности (О большое от N) я никогда толком не понимал :)

[ashalynd.livejournal.com]

Найти сумму для каждого ряда и каждой колонки, попутно запоминая максимальную сумму ряда.

Если эта сумма = N-1, он соответствует тому, кого знают все. В этом случае проверить, стоит ли в сумме его колонки 0. Если это так, то решение найдено. Если это не так, то знаменитости не было.

[analizer.livejournal.com]

отношение рефлексивно? т.е. по диагонали нули или единицы?

[vogre.livejournal.com]

Таблица - T
Пусть Ai = sum(2^T(i,j)){j=1..N} - число, образованное рядом i
Bi = sum(2^T(j,i)){j=1..N} - число, образованное колонкой номер i

Тогда Если Ai - степень двойки, а Bi = (2^N)-1, то i - знаменитость.

[yakov-sirotkin.livejournal.com]

По результатам любого запроса к таблице один перестаёт быть кандидатом на лидерство. Через N-1 операцию останется один кандидат, за O(N) это проверяется.

[http://users.livejournal.com/__d503__/]

а как насчет клеток (i,i) для знаменитостей? там 0 или 1?

[singalen]

Нужно найти номер i, где i-й столбец содержит только нули, а i-я строка - только единицы. Исключая главную диагональ, конечно.
Сначала линейно пройтись по списку всех "кандидатов". Если первый и второй друг друга знают или не знают - исключить обоих. Если 1-й несимметрично знает 2-го или наоборот - исключить одного.
Повторять, пока не останется только один.
Проверить, что в его строке нули, а столбце единицы.

[duke-igthorn.livejournal.com]

Знаменитость хотя бы себя-то знает?;)

[piggymouse.livejournal.com]

За украинскую Википедию ЗАЧОТ!!!

[ashalynd.livejournal.com]

Немного подумав, я поняла, что все несколько сложнее.

Во-первых, в процессе нахождения суммы для ряда можно прекращать суммирование, если обнаружен хотя бы один 0 (хотя бы один человек не знает i, значит, сумма точно меньше N-1).

Во-вторых, для ряда с суммой N-1 (меня знают все) можно сразу проверить, равна ли сумма в соответствующей колонке 0 (я не знаю никого); если это так, то решение найдено, если не так, то знаменитости на вечеринке нет, потому что все остальные знают как минимум одного человека, и на этом поиск прекращается.

И, кажется, я рядами называла колонки и наоборот, хотя сути это не меняет.

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

[ivanvr.livejournal.com]

А что если мы просто сделаем сумму по строкам и столбцам для 1-N. Если мы встечаем K, такое что sum_row(K)==0 && sum_col(K)==N-1 то это знаменитость.

Или это не проходит из-за O(N) ?

[filpp.livejournal.com]

Пардон мою неграмотность. А что такое O{N}? Время выполнения пропорционально N?
Считаем сумму по каждой строке и каждому столбцу.
Если сумма по n-й строке 0, а по n-ному столбцу N-1, то это оно и есть. Только я не знаю что такое O(N) ;).

[arrt.livejournal.com]

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

[cvetkov.livejournal.com]

очевидно это невозможно.
так как надо просмотреть O(N^2) данных из таблички

[astaff.livejournal.com]

//
// We assume that party[i,i] == 1
//
int solve(bool[,] party)
{
   int k = 0;

   while (j < N)
   {
      if (party[i, j] == 0)
      {
         j++;
         k = i;
      }
      if (party[i, j] == 1)
         i++;
      if (i == N - 1)
         return ((k-th row is all 0s except j-th element) && (j-th column is all 1s)) ? j : -1;

   }
   return -1;
}

Я не компилировал ;)) Иными словами просто змейкой спускаемся из(0,0). если (i,j)=0, то сдвигаемся вправо, если 1, то спускаемся вниз. Если достигли последней строчки, проверяемем, что это звезда (знаменитость?): стоблец из единиц, и предыдущая и строчка с которой мы начали спускаться по этой колонке состоит из нулей.
О задачке узнал от piggymouse

[ralan.livejournal.com]

Графы.
int starIndex = -1;
for(int i=0; i< N; i++){
if(NA[i, i+1] == 1){
continue;
}else{
int j = i+2;
while(NA[i,j] == 0 & j

[Error: Irreparable invalid markup ('<n){>') in entry. Owner must fix manually. Raw contents below.]

Графы.
int starIndex = -1;
for(int i=0; i< N; i++){
if(NA[i, i+1] == 1){
continue;
}else{
int j = i+2;
while(NA[i,j] == 0 & j <N){
j++;
}
if(j == N){
Console.Write("Possible star");
starIndex = i;
break;
}else{
i = j;
}
}
}

Где N - длина таблицы (нужно учитывать, что таблица квадратная), а NA массив NxN с данными 1 или 0. проверка звезды занимает O(N) -> так что сложность O(2N) т.е. O(N).

[sab123.livejournal.com]

Гм, начинаем с первой строчки, и идем вдоль строчки, ищем 1. Если не нашли 1 вообще - значит, это потенциальная знаменитость, ее пропускаем, смотрим аналогично следующую строчку сначала. Если нашли 1, то смотрим, есть ли "обратное знание" (т.е. m[i,j]==1, проверяем m[j,i]). Если есть (m[j,i]==1), то продолжаем поиск в этой строчке. Иначе запоминаем колонку, и переходим к просмотру следующей строчки с этой колонки (кроме случая, когда номер следующей строчки равен номеру колонки - тогда опять потенциальная знаменитость, и эту строчку мы пропускаем).

Когда кончатся строчки - продолжаем опять с первой строчки по тому же принципу, сохраняя текущую колонку, пока или не выйдем за число колонок, или же не просмотрим с положительным результатом одну колонку во всех строчках. В первом случае знаменитости нет, во втором случае номер колонки указывает на знаменитость. Вроде как, максимальное количество просмотренных ячеек получается 8*N.

[sasha-gil.livejournal.com]

Та же фигня - услышал задачу накануне вечером, а в среду за ланчем немного пообсуждал с друзьями и понял, как решается. Но это тизер, всё-таки.

[109.livejournal.com]

найти сумму каждого ряда - это уже O(N^2).

[109.livejournal.com]

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

[109.livejournal.com]

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

[109.livejournal.com]

суммирование каждого ряда или даже "пробегание" по каждому ряду - это O(N^2).

[109.livejournal.com]

не проходит из-за O(N) :)

[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 раза.

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