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

## Обсуждение задачи 1280. Topological Sorting

Why this problem has so high complexity estimation?
Послано breezemaster 25 дек 2013 20:23
It is very easy problem, i think complexity estimation 192 is overestimation.
Very simple search was accepted:

static bool Solve(IEnumerable<Tuple<int, int>> limitations, int[] proposedOrder)
{
foreach (Tuple<int, int> limitation in limitations)
{
int less = limitation.Item1;
int greater = limitation.Item2;
if (less == greater)
return false; // wrong rule

foreach (int currentSubj in proposedOrder)
{
if (currentSubj == greater)
return false; // first is greater, so rule is contradicted
if (currentSubj == less)
break; // first is smaller, so rule is satisfied, go to next one
}
}
return true; // all rules was satisfied
}
Re: Why this problem has so high complexity estimation?
Послано Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 25 дек 2013 23:59
1. Some time ago ML for it was 1MB. Try to solve within this limitation.
2. Average difficulty of a problem on Timus is ~1300, so 192 means that it is very simple problem (~15% of average difficulty), how did you get it is overestimation?