победитель Опции

[passat]

В состязаниях участвуют N (N - до 100000) спортсменов. Каждому даются три попытки. Входной файл содержит 3 строки с положением участников в каждой попытке (ни в одной из попыток невозможно двум и более человекам разделить одно место).
Считается, что спортсмен A сильнее спортсмена B в случае, если A занял во всех попытках места выше, чем B. А является лучшим среди всех, если нет никого лучше его.
Найти и вывести в выходной файл количество лучших спортсменов.

Реализацию напишу сам, но подскажите алгоритм.
Пока просматривается следующее.
Поскольку раздел мест невозможен, то представляя лучшее и худшее место спортсмена во всех попытках как координаты отрезка, задача сводится к определению количества связных областей в начале координатной прямой.
Т.е. реализация в самом общем виде что-то типа такого:
- считать данные в массив, где каждому спортсмену отводится по 2 позиции: на первой лучшее место, на второй худшее место
- с первой позицией связываем +1, со второй - -1 (можно использовать либо пару массивов, либо один, но с несколько более сложной структурой элементов - в принципе, это сейчас не интересует)
- сортируем массив (второй - по результатам первого)
- осталось посчитать сумму первых +/-1 до получения первого нуля.
Количество +1 дает количество победителей.

Особо смущает факт, что сортировка должна быть стабильной. А это сразу увеличивает время, особенно на больших количествах. Это наталкивает на грустную мысль, что само решение неверное.

Подскажите, пожалуйста, правильный ли подход в принципе. Жаль тратить время на неправильное решение.

[TarasBer]

Лучший - это не тот, который лучше всех остальных. Это тот, для которого нет никого лучше него.
Чувствуете разницу?
То есть он лучше всех, с кем его можно сравнавить. А если его сравнивать ни с кем нельзя - значит нет никого лучше него. Значит он лучший.

Что касается определений, то это 1 курс, дискретная математика, теория множеств.

Например, на множестве из 5 элементов введём частичный порядок на графе так - один элемент считаем "больше" другого, если от первого ко второму можно провести путь, при движении по которому мы идём всё время вниз.
На графе, изображённом на рисунке - элементы 1 и 2 максимальные, но не наибольшие.
Элемент 5 - наименьший. И минимальный тоже, соответственно.
В случае с 3 спортсменами мы имеем 3 несвязанных точки. Каждая из них, конечно же, максимальна и минимальна. Но не наибольшая и не наименьшая.

> Или, на худой конец, приведите пример, где ответ 0 (не в моем понимании).
> Или хотя бы 1. Ну, 2.. Но только не ВСЕ участники, как в этом примере.

Ответ бывает 0 - только если спортсменов нет. В любом непустом конечном ЧУМе есть максимальный элемент.
Один лучший спортсмен - это когда во всех состязаниях один и тот же победитель.
Двое лучших - вот как я тут привёл.

Сообщение отредактировано: TarasBer - 19.03.2009 13:17