задачка

[109]

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

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

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

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

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

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

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

Comments

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

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

[avoider.livejournal.com]

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

[109.livejournal.com]

там у меня ссылка есть на википедию :)

[ashalynd.livejournal.com]

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

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

[109.livejournal.com]

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

[analizer.livejournal.com]

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

[109.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 - знаменитость.

[109.livejournal.com]

гм... неправильно, несмотря даже на то, что не O(N)

[yakov-sirotkin.livejournal.com]

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

[109.livejournal.com]

правильно :)

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

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

[109.livejournal.com]

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

[singalen]

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

[109.livejournal.com]

правильно!

[duke-igthorn.livejournal.com]

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

[109.livejournal.com]

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

[piggymouse.livejournal.com]

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

[109.livejournal.com]

it is called "attention to the details" :)

[ashalynd.livejournal.com]

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

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

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

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

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

[109.livejournal.com]

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

[ivanvr.livejournal.com]

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

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

[109.livejournal.com]

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

[filpp.livejournal.com]

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

[109.livejournal.com]

если украинская википедия не устраивает, то там есть ссылки на русскую и английскую :)

но грубо - да, асимптотическая скорость алгоритма.

а решение твоё правильное, но не O(N), а O(N^2), поэтому не подходит.

[arrt.livejournal.com]

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

[109.livejournal.com]

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

задача состоавлена корректно.

no hire.

[cvetkov.livejournal.com]

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

[109.livejournal.com]

мы рождены, чтоб сказку сделать былью :)

уже трое нашли решение.

[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

[astaff.livejournal.com]

Как я уже писал в апдейте (ветка почему-то не сохранилась) первый return должен звучать как
return ((j-th row is all 0s except j-th element) && (j-th column is all 1s)) ? j : -1;

Дык в итоге правильное решение? Я так и не понял почему оно должно завалиться, если встретит столбец из единиц не доходящий до верха.

[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).

[109.livejournal.com]

я вижу два вложенных цикла, длина обоих пропорциональна N. и вообще, словами надо уметь объяснять решение :)

[sab123.livejournal.com]

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

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

[109.livejournal.com]

я не могу понять объяснение работы алгоритма. нельзя ли попонятнее переформулировать? (особенно поражает множитель 8).

[sasha-gil.livejournal.com]

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

[109.livejournal.com]

Но это тизер, всё-таки.

"всё-таки" - это всё-таки что значит? :)

[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) алгоритма.

[astaff.livejournal.com]

А какой кейз оно не покроет???

[regento.livejournal.com]

начинать нужно с нижней левой ячейки, т.е. изначально i,j=(n-1).
существуют 4 ситуации и 3 возможных направления движения:

1. a(i,j)=1 и a(j,i)=0: i знает j, но j не знает i. Потенциальная знаменитость - j, двигаться
вверх.
2. a(i,j)=0 и a(j,i)=1: i знает j, но j не знает i. Потенциальная знаменитость - i, двигаться вправо.
3,4. Оба знают или не знаю друг-друга. Оба вылетают и движение по диагонали вверх-вправо.

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

[aivar.livejournal.com]

?
1 2 3 4
1. 0 1 1 1 & 1000 = 1000
2. 1 1 0 1 & 1000 = 1000
3. 0 1 1 1 & 1000 = 0000 & 0100 = 0100
4. 0 0 0 1 & 1000 = 0000 & 0100 = 0000 4.

[109.livejournal.com]

гм... я несколько теряюсь, что означает этот пост. не могли бы вы пояснить?

[selfmade.livejournal.com]

В порядке бреда.
0. Начинаем из левой верхней клетки. Диагональные клетки пропускаем.
1. Запоминаем позицию. Идём вправо до первой единички. Если упёрлись в стенку, то переходим на первый элемент этой же строки и продолжаем идти вправо до исходной позиции. Если упёрлись в исходную позицию, то идём на п.3.

2. Если встретили единичку, то начинаем идти вниз до первого нуля. Если упёрлись в пол, то нету знаменитостей. Если встретили ноль, то идём на п.1.

3. Бля, я никого не знаю, кто все эти люди? Идём вниз в поисках нуля. Если встретили 0, то идём на п.1, иначе если упёрлись в пол, то переходим на первый элемент столбца и продолжаем идти вниз. Если упёрлись в исходную позицию, то знаменитость найдена, если встретили 0, то знаменитостей нет.

[faceted-jacinth.livejournal.com]

Вроде же просто, я за пять минут придумал.

Рассмотрим двух чуваков, i и j, и рёбра между ними. Есть четыре варианта:
a[i, j] = 0 && a[j, i] = 0 : оба не могут быть знаменитостью
a[i, j] = 0 && a[j, i] = 1 : j не может быть знаменитостью
a[i, j] = 1 && a[j, i] = 0 : i не может быть знаменитостью
a[i, j] = 1 && a[j, i] = 1 : оба не могут быть знаменитостью.

А дальше дело техники: заводим списог потенциальных знаменитостей и производим вышеописанное рассмотрение для его элементов. На каждом шаге из списка вылетает хотя бы один чуваг, так что через O(n) шагов у нас либо кончатся варианты вообще, либо останется ровно один кандидат. Для которого мы уже можем тупо проверить строчку и столбец.

[109.livejournal.com]

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

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