Форум

Григорий Ярославцев: Можно по простому // 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