Форум

Сергей Чистович: А вот ещё задача // 12 сентября 2007, 20:27

Есть большая группа людей - числом, положим, Эн Большое. Каждый может знать или не знать каждого другого, причём отношение это не симметричное (если я знаю Дарью Дическул, она может меня и не знать ). Эти отношения записаны в матрицу NxN, ноликами и единичками.

Будем считать знаменитостью человека, которого знают все, а сам он не знает никого. Вопрос: можно ли за O(N) (то есть за N*какую-то_константу) операций выяснить, есть ли у нас в обществе знаменитость?

Александр Симин: по-моему можно... // 14 сентября 2007, 12:46

хотя я и не очень уверен, что правильно - можно поочередно убирать из матрицы j-ую строку и j-ый столбец (как называется эта операция??? и считать сумму по оставшимся строкам/столбцам. В зависимости от того, поменялась ли сумма на N (все знают человека j) или не поменялась (человек j не знает никого) - и определяется, есть ли знаменитость.
Примерно так.

Сергей Чистович: Я не совсем понял, что ты предлагаешь, // 14 сентября 2007, 13:26

Но такое впечатление, что количество операций будет примерно N^3, нет? Сумму считать - это тебе не фунт изюму...

Понятно, что за 2N^2 сделать не проблема: пройтись по всей матрицен вдоль и поперек, да поискать ряд, где все единички и строку, где все нули. Но это слишком долго.

Александр Симин: Ну, // 14 сентября 2007, 15:35

я и предлагаю пройтись по всем, например, строчкам и поискать, где все нули. Потом для нулевых строк проверить соответствующие столбцы. Только сумму нужно считать для матрицы без j-й строки и j-го столбца, так как сам себя человек всегда знает... или нет?
Только ты определись с понятием "операция", так как для меня "поискать ряд, где все единички и строку, где все нули" - это непонятно. А сумма элементов любой строки/столбца - это имхо операция, нет? Кроме того, даже сама сумма не нужна, нужно сравнить больше она, равна или меньше нуля или N.

Сергей Чистович: Ты программист или что? // 14 сентября 2007, 17:22

Найти сумму N чисел - это N операций. Ладно, N-1. Проверить N чисел, являются ли они нулём - тоже N. Не очевидно?

Александр Симин: упаси Боже... // 14 сентября 2007, 17:26

неочевидно. Ладно, не буду мешать.

Спасибо, Вам, Сережа, за интересную задачу! Она мне показалась свежей (хотя похожа на вступительные испытания для программистов).
Сегодня я ее решил. Правильный ответ: можно!
Если Вам интересно, могу опубликовать алгоритм.

Сергей Чистович: Я думаю, пока сохраним его в тайне :) // 17 сентября 2007, 11:46

Я тоже решил, мне не нвдо.
Вроде кого-то на собеседовании в гугль спрашивали.

Дмитрий Кобак: Я тоже решил! // 17 сентября 2007, 22:13

Задача отличная. Я её наконец решил, сидя вчера в поезде Франкфурт-Фрайбург.

Сергей Чистович: нас уже трое! // 18 сентября 2007, 13:22

Два преподавателя, два выпускника. Всего трое. Ещё бы хоть одного действующего гимназиста...