Обсуждение @ 1273. Шпалы @ Timus Online Judge

Online Judge	Задачи	Авторы	Соревнования
О системе Часто задаваемые вопросы Новости сайта Форум Ссылки	Архив задач Отправить на проверку Состояние проверки Руководство	Регистрация Исправить данные Рейтинг авторов	Текущее соревнование Расписание Прошедшие соревнования Правила

Обсуждение задачи 1273. Шпалы

How did you do it in O(n^2). I only know n^3 =(

Послано hey, dude! 4 апр 2005 14:56

Re: How did you do it in O(n^2). I only know n^3 =(

Послано Cybernetics Team 4 апр 2005 16:55

It also can be done in O(K * logK). O(N^2) is with DP, a classic problem (longest increasing subset)