Версия для печати темы

Автор: passat 17.03.2009 14:14

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

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

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

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

Автор: maksimla 17.03.2009 14:35

если я правильно понял по строчкам

Считается, что спортсмен A сильнее спортсмена B в случае, если A занял во всех попытках места выше, чем B. А является лучшим среди всех, если нет никого лучше его.
Найти и вывести в выходной файл количество лучших спортсменов.


что самый большой результат нужна всего только а вывести лучший результат то делаем так
все три результата складываем в один результат сразу и в массив записываем а потом сортировку по уменьшению делаем и все и выводим результат

может правильно а может нет не знаю я думай сам

Автор: Lapp 17.03.2009 15:27

Извиняюсь, но не вполне врубился в условие. Можешь привести пример?

Автор: passat 17.03.2009 16:32

Тот, что есть, не помогает:

1 2 3
2 3 1
3 1 2

Ответ : 3


Если бы нужно было всего лишь просуммировать места, то было бы слишком просто. Единственная засада - переполнение - решается на полсчета.

Единственный пример данных не отвечает на вопрос, заданный предыдущим оратором.

Автор: Lapp 18.03.2009 8:09

Ну, положим, это был не вопрос, а просьба..)) И кое-что этот пример "поясняет". Поясняет, что я, оказывается, понимаю еще меньше, чем думал)). По моему разумению, ответ к этим данным должен быть 0 - ибо каждый в какой-то попытке хуже других. Например, 1 лучше всех в первой попытке, но хуже всех во второй и всего средний в третьей. И так про каждого можно сказать. Откуда 3?
Давненько я не чувствовал себя так тупо..

Автор: maksimla 18.03.2009 14:28

мне тогда кажется надо все серавно слапить три результата ну все результаты и потом смотреть наилутший результат тоесть наименьший и потом подсчитать сколько наименьших результатов и записать

Автор: passat 18.03.2009 16:25

Это было бы слишком просто. Непонятно, в чем смысл задачи.
Выбор минимального (и подсчет) - тривиальная задача, выполняемая за линейное время. Единственный подводный камешек - опасность переполнения - обходится легким заведением дополнительного поля.


Это уже вопрос вкуса.
Как в том анекдоте: из двух спорсменов один обязательно будет вторым, а другой - предпоследним.

Говорю, что не объясняет, т.к. единственный пример допускает толкование условия задачи как банального суммирования мест.

Автор: Lapp 18.03.2009 17:06

А прояснить условие негде?

Автор: passat 18.03.2009 18:13

К сожалению, нет.
Давайте исходить из того, что правильно мое. Т.к. для суммы мест решение я знаю. Если надо, логику могу написать, но вроде она банальна. Единственный подводный камень описал: возможно переполнение. Т.е. надо иметь дополнительный байт/два байта для подсчета переполнений. Или увеличить размерность поля суммы, но тогда непроизводительно может расходоваться память.

Кстати, пока писал и пытался сформулировать задачу пришел к интересной идее: у победителя/ей худшее место должно быть лучше, чем у остальных лучшее. Нодо подумать, можно ли вытянуть из этого что-нибудь.

Автор: TarasBer 18.03.2009 19:37

У Частично Упорядоченного Множества (а мы имеем дело именно с ним) есть понятия "максимального элемента" и "наибольшего". "Максимальный" - это того, для которого нет элемента больше него. "Наибольший" - это тот, который больше всех других. В данном случает нужны максимальные элементы, в данно случае их три - для любого спортсмена нет того, который был бы лучше него, просто потому, что их в данном случае нельзя сравнивать.


Добавлено через 3 мин.


Если я правильно понял, что вы имеете в виду, то боюсь, что это плохой вариант. Если один спортсмен занял 1, 2, 3 места, а другой - 2, 3, 4, то явно первый лучше второго, но при этом соответствующие им отрезки пересекаются.

Автор: Lapp 19.03.2009 7:20

Щаз завою.. жалко, луны нет..
TarasBer, правильно я понимаю, что ты имел в виду нестрогое (>=) и строгое (>) неравенства для определений максимального и наибольшего элемента соответственно? Я не против, хотя мне представляется несколько неуместной такая дискриминация русского языка по отношению к латыни (максимальный получается как бы главнее - шутка, конечно )). Но при чем тут это? Я как не понимал, так и не понимаю, как в примере получилось 3. Честно, я не рисуюсь, поверьте, аж самому обидно.. Объясните для идиотов, плз. И вообще, пожалуйста, подкрепляйте ваши рассуждения примерами.

Я понимаю условие буквально (а как еще?). Вот пример, когда 2 лучше 1:

3 4 2 1
2 3 4 1
2 1 4 3

Если хоть в одной попытке порядок обратный - все, лучшего среди них нет:

3 4 2 1
2 3 4 1
1 2 4 3

И вообще, понятие "лучший" определено только относительно кого-то еще. Абсолютно лучший (лучше всех остальных) может быть только один. Я готов принять без лишних разговоров, что в условии (в вопросе) идет речь о тех, кто лучше хоть кого-то. Но в примере passat'а таких нет совсем. Следовательно, ответ должен быть 0.
Вот мое понимание. Жду вашего..
Или, на худой конец, приведите пример, где ответ 0 (не в моем понимании). Или хотя бы 1. Ну, 2.. Но только не ВСЕ участники, как в этом примере.

Автор: TarasBer 19.03.2009 17:05

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

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

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

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

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


Эскизы прикрепленных изображений

Автор: volvo 19.03.2009 17:38

В таком случае, зачем проводятся соревнования? Попытки, в которых спортсмены соревнуются друг с другом - это что, так, для галочки, а совсем не сравнения, да? Всем троим выдать золото, ибо, оказывается, никого ни с кем нельзя сравнивать? Это теперь так делается?

Спортсмен №1 проиграл всем во второй попытке. Но все-таки, он ЛУЧШИЙ??? При каких условиях он будет ХУДШИМ, интересно?

Добавлено через 1 мин.
Чего ты привел? Рисунок этот? Ты таблицу приведи...

Автор: TarasBer 19.03.2009 17:48

Упырьте мел. В рамках задачи это именно так делается. Спортсменов можно сравнивать, только если один прогирал другому ВО ВСЕХ состязаниях.


А он и худший тоже. И лучший, и худший. Каждый. Что вас удивляет?
Вы не верите, что он лучший - тогда назовите того, кто лучше него. Нет таких? Нету. Значит он лучший.
Господи, 1 курс, теория множеств.

Автор: Lapp 19.03.2009 18:12

O'kay, согласен. Возникла некоторая путаница в терминах "лучший" и "лучший среди всех". Если есть многословные термины ("А является лучшим среди всех, если нет никого лучше его"), то надо их употреблять аккуратнее. А в вопросе стоит: "Найти и вывести в выходной файл количество лучших спортсменов". И разбирайся, какой именно термин имелся в виду..

- это как? не понимаю..

Господи тут ни при чем. Условие писать нужно четче.

Автор: TarasBer 19.03.2009 18:55

Тогда да - слово "среди всех" тут лишнее. Но пример призван был прояснить эту неточность.

Это такая шуточная перестановка фразы "умерьте пыл".

Автор: passat 28.03.2009 0:17

Поняли, видимо, правильно.
В Вашем примере Вы отбросили третьего и четвертого спорсменов, убдь они неладны. А этого делать нельзя.
Т.е. введя данные для этих неучтенных, Вы получите, что первый не будет лучше второго, т.к. появится хотя бы один третий (в Вашем примере еще и четветый), который будет лучше первого хоят бы в одной попытке.

А тогда моя идея сработает правильно? Проблема, что тесты писать для разных ситуаций, да еще и не зная направления - долго.

Господа, места не могут повторяться.

Автор: TarasBer 30.03.2009 3:36

А ну и что? Первый спортсмен - один из лучших, просто потому, что хотя б в одном состязании занял первое место. Но я пример к чему привёл-то. К тому, что по вашей системе непонятно, как второго учитывать, вот к чему. Отрезки-то пересекаются со всеми другими спортсменами, но лучшим он не является.

Автор: passat 1.04.2009 19:48

Я не настаиваю на правильности своего алгоритма. Наоборот, прошу, чтобы меня разубедили.

Теперь касательно Вашего замечания. В том и дело, что худшими (если брать критерий от противного) будут те спортсмены, у которых лучшее место будет хуже, чем у остальных. Иначе говоря, лучшие по условию задачи спортсмены должны образовать замкнутую группу. Т.е. группу связанных отрезков. Отношения между отрезками в этой группе нам по условию не интересны. Или в терминах спортсменов: пусть даже первый будет хоть трижды лучше второго. Но найдется хотя бы одна попытка, в которой некто четвертый или пятый будет лучше первого, проиграв первому (и даже второму) в остальных. Это единственное лучшее место четвертого включает его в число победителей.
Таким образом, победителями становятся: первый, второй и четвертый.

Ну и т.д.

Хотелось бы критики решения. Т.к. готовых тестов (и решения задачи) у меня нет. А пойти неверным путем не хочется.

Автор: Archon 2.04.2009 12:30

Интересная задачка, правда явно олимпиадная, поэтому место ей в другом разделе. Вот как я понял:

Рассмотрим пример Lapp'а.
3 4 2 1
2 3 4 1
2 1 4 3
Для первого и второго спортсменов нет никого, кто был бы "лучше" их. Поэтому они добавляются в число "лучших среди всех". Для третьего спортсмена есть другой спортсмен (четвёртый), который "лучше", потому что четвертый лучше третьего во всех попытках. Для 4-ого опять нет никого, кто был бы лучше. Ответ 3.

Другой пример Lapp'а.
3 4 2 1
2 3 4 1
1 2 4 3
Тут из числа лучших выбывают спортсмены 2 и 3. Так как есть первый, который во всех попытках лучше второго и четвёртый, который во всех попытках лучше третьего. Ответ 2.

То есть если спортсмена описать так:

Sportsman = record
	c1, c2, c3: Integer;
end;

То функция определения, лучше ли один спортсмен другого, будет выглядеть так:

function Better(s1, s2: Sportsman): Boolean;
begin
	result := (s1.c1 < s2.c1) and (s1.c2 < s2.c2) and (s1.c3 < s2.c3)
end;

Решать, думаю, надо так:
Введём массив "лучших" переменной длины. Изначально этот массив пустой. Добавим туда первого спортсмена. Далее, перебираем всех спортсменов начиная со второго и сравниваем их со всеми из массива "лучших". Если текущий спортсмен оказывается "лучше", чем какой-нибудь из массива, то ставим текущего спортсмена в массив на это место (то есть заменяем того, кто "хуже" на того, кто "лучше"). Если мы не нашли в массиве элемент, для которого текущий спортсмен был бы "лучше", добавляем текущего спортсмена как новый элемент.

Автор: passat 3.04.2009 21:39

Интересная трактовка задачи. В такой постановке, Вы , возможно, правы.

Похоже, способа проверить, кроме как сдать, не существует. Т.к. возможны разные трактовки условия.

Интересно, а задача уже где-то встречалась? Есть живые тесты, чтобы разобраться?