Форум

Сергей Чистович: А почему среди алгоритмических задач // 16 ноября 2007, 12:07

Нет моей задачи про знаменитости? Там же, рядом с гномами. Или условие слишком "математическое"?..

Сергей Чистович: И ещё - поясните задачу про знакомства супругов // 16 ноября 2007, 12:16

По-моему, там не хватает чего-то очень важного в условии. Я вообще не понимаю, как из имеющихся данных можно делать какие-то выводы.

В. В. Зельченко: [без темы] // 16 ноября 2007, 16:58

А у меня получилось.

Я думал про Вашу задачу, Сережа! Она, конечно, самая "алгоритмическая" из всех. Но трудно объяснить гимназистам, что такое O(N), если даже г-н Симин (далеко уже не гимназист!) попал впросак.
И еще. Знакомства в задаче про супругов - симметрические (в отличие от Вашей задачи). Если Вы считаете, что этого условия не хватает, то - вот, пожалуйста!
Приходите сами на заседание, а то я что-то давно Вас не видел!...

Софья Александрова: Эх // 18 ноября 2007, 00:49

А я вот никак не успеваю, увы увы.
Расскажешь мне потом, как все решается?

С удовольствием рассказал бы, но тебя я тоже давно не видел!
(Говорят, ты была на зачетах? Приходи и ко мне: 27 ноября на 3-м и 4-м уроках.)

Софья Александрова: [без темы] // 20 ноября 2007, 23:59

Я, кажется, не могу. (А хочу.)
Но могу постараться
Или просто так зайти как-нибудь.

Григорий Ярославцев: Можно по простому // 19 ноября 2007, 00:04

В задаче про знаменитость можно просить не решение за O(N) времени, а решение, использующее не более K * N обращений к элементам матрицы в худшем случае (например 3 * N - я за столько умею). Это вполне понятно.

Сергей Чистович: Ага, вариант. // 21 ноября 2007, 15:11

Только зачем три? Хватит и двух, кажется.

Григорий Ярославцев: [без темы] // 21 ноября 2007, 23:11

Я не искал меньшую константу из идеологических соображений: пусть нам предложили ответ - тогда на его проверку необходимо 2 * (N - 1) операций, а успеть найти кандидата в ответы быстрее, чем за O(N) в худшем случае довольно странно. При этом эти две задачи скорее всего не перекрываются, так что 3 показалось мне похожим на нижнюю оценку для константы. В общем, интересно было бы в пятницу услышать решение за 2 * N

Сергей Чистович: Да, этого мне не хватало // 21 ноября 2007, 15:09

С симметричностью действительно вроде получается.

Рад бы, но я сейчас в Москве работаю, дома только по выходным, и то не всегда. Но надеюсь весной вернуться, если получится.

Дмитрий Кобак: хаха! // 20 ноября 2007, 21:47

Признай, Серёга, что ты сел в лужу. Задача про супругов - просто отличная! Спасибо, Андрей Юрьевич. Несложная, но доставила мне несколько очень приятных минут.

Сергей Чистович: Хе-хе // 21 ноября 2007, 15:15

Да, когда мне сказали, что она решается, и что знакомства, конечно, симметричные, то сразу стало понятно, как её решать.