![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
школа | учеба | люди | партнеры | досуг | фотобанк | форум |
новое сообщение | поиск | статистика | правила | регистрация
По-моему, там не хватает чего-то очень важного в условии. Я вообще не понимаю, как из имеющихся данных можно делать какие-то выводы.
Комментировать | Вся дискуссия
Я думал про Вашу задачу, Сережа! Она, конечно, самая "алгоритмическая" из всех. Но трудно объяснить гимназистам, что такое O(N), если даже г-н Симин (далеко уже не гимназист!) попал впросак.
И еще. Знакомства в задаче про супругов - симметрические (в отличие от Вашей задачи). Если Вы считаете, что этого условия не хватает, то - вот, пожалуйста!
Приходите сами на заседание, а то я что-то давно Вас не видел!...
А я вот никак не успеваю, увы увы.
Расскажешь мне потом, как все решается?
С удовольствием рассказал бы, но тебя я тоже давно не видел!
(Говорят, ты была на зачетах? Приходи и ко мне: 27 ноября на 3-м и 4-м уроках.)
Я, кажется, не могу. (А хочу.)
Но могу постараться
Или просто так зайти как-нибудь.
В задаче про знаменитость можно просить не решение за O(N) времени, а решение, использующее не более K * N обращений к элементам матрицы в худшем случае (например 3 * N - я за столько умею). Это вполне понятно.
КомментироватьТолько зачем три? Хватит и двух, кажется.
Комментировать
Я не искал меньшую константу из идеологических соображений: пусть нам предложили ответ - тогда на его проверку необходимо 2 * (N - 1) операций, а успеть найти кандидата в ответы быстрее, чем за O(N) в худшем случае довольно странно. При этом эти две задачи скорее всего не перекрываются, так что 3 показалось мне похожим на нижнюю оценку для константы. В общем, интересно было бы в пятницу услышать решение за 2 * N
С симметричностью действительно вроде получается.
Рад бы, но я сейчас в Москве работаю, дома только по выходным, и то не всегда. Но надеюсь весной вернуться, если получится.
Признай, Серёга, что ты сел в лужу. Задача про супругов - просто отличная! Спасибо, Андрей Юрьевич. Несложная, но доставила мне несколько очень приятных минут.
КомментироватьДа, когда мне сказали, что она решается, и что знакомства, конечно, симметричные, то сразу стало понятно, как её решать.
Комментировать