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

Обсуждение задачи 1092. Трансверсаль

Possibly to solve with greedy algo even now
Послано Vedernikoff Sergey 6 май 2008 20:02
Even after anti-greedy tests were added, it is possibly to solve the problem with greedy algo. Just randomize directions in which you make "greedy walk" of the incidence matrix. The best thing is that it is impossible to kill such an algo with any anti-greesy tests! =)
Re: Possibly to solve with greedy algo even now
Послано Denis Koshman 19 авг 2008 02:48
I have proven greedy solution (with O(N^3) output size)