Расколоть «орешки» компьютером

Кто может решать задачи на деревьях (а есть такой тип задач, обычно в учебниках выделяемый в отдельную главу: «Решение задач на деревьях и с помощью деревьев»)? И кто при этом спорит, каким алгоритмом решать — Крускала или Прима? Кто вспоминает алгоритм Форда-Фалкерсона, когда слышит о потоке в транспортной сети? Кто не боится разбирать «гробы» (гробом называется почти не решаемая задача)? Не знаете? Конечно, студенты-программисты, которые совсем недавно имели возможность всем этим позаниматься на оочень престижном турнире.

Из истории
Международный командный чемпионат по программированию впервые был проведён в Техасском университете в 1970. Свой нынешний облик чемпионат принял в 1977, когда первый финал прошёл в рамках научной конференции ACM и с тех пор проводится ежегодно. Российские представители успешно выступали на нём, и в 1998 году, когда красноярская команда КГТУ заняла 3-е место среди вузов Сибирско-Дальневосточной группы, на базе нашего города стал проводиться четвертьфинальный этап. В соревнованиях участвуют студенты-программисты, представляющие города Красноярского края, Иркутской области, Республик Хакасии и Бурятии.

10 ноября на базе ИКИТ состоялись четвертьфинальные соревнования чемпионата мира по программированию. О том, как это было, нам рассказали члены оргкомитета братья Денис и Андрей ЦВЕТЦИХ.

Денис: Формат соревнований не меняется с момента основания: в команде три участника и один компьютер. Задача считается успешно решённой, если она проходит все тесты. За неполное решение баллы не зачисляются. Каждая программа тестируется как чёрный ящик, есть входной и выходной файл, есть решение жюри. Алгоритм решения может отличаться, но итоговые данные должны совпадать.

Андрей: Вчера был прецедент, когда сложную задачу решили новым способом, который отличался от решения жюри. Это здорово, что студенты находят другие решения, особенно сложных задач. Придумывает задания авторский коллектив из числа бывших участников. Потом мы отбираем 10 лучших, которые войдут в итоговый вариант. Студенты решают их в течение 5 часов. Подбираем так, чтобы участники, не обладая глубокими знаниями в какой-то конкретной области, могли решить несколько задач.

Особенностью олимпиадных задач является «художественность» их условия. В условиях редко ведётся речь о структурах данных и алгоритмах, приводящих к решению. Чаще условие задачи представляет собой короткий рассказ со своим сюжетом, героями и конфликтом. Таким образом, чтобы решить олимпиадную задачу, нужно предварительно составить математическую модель событий, и уже по ней подобрать или построить подходящий алгоритм. Алгоритм может быть как одним из уже известных алгоритмов, так и абсолютно новым, непохожим на другие. Решение таких неформализованных задач даёт олимпиадникам весомое преимущество перед одногруппниками. Такие люди на рынке труда очень ценятся.

В четвертьфинале соревновались 30 команд, десять из них поедут на полуфинал

В четвертьфинале соревновались 30 команд, десять из них поедут на полуфинал

Полуфинал для участников Сибирско-Дальневосточной группы состоится 1 декабря в Барнауле. Одновременно задачи будут решать в Санкт-Петербурге, Ташкенте и Тбилиси — этот этап олимпиады распределённый с синхронизацией через Интернет. На финале в Екатеринбурге встретятся около 150 команд.

Денис: До недавнего времени команды четвертьфинального региона выступали не очень хорошо и за путёвки в финал не боролись. Но несколько лет назад появилась команда «Бизоны» Института математики и фундаментальной информатики, которая в нашем округе побеждает третий год. Они тренируются ещё со школы, во многом на энтузиазме и личной инициативе, сейчас их наставник Михаил КОРМЫШОВ, сам бывший участник. Теперь и у Красноярска появился шанс попасть в финал. Отмечу, что наша полуфинальная группа очень сильная, конкуренция в ней даже выше, чем на финале. Например, в прошлом году команды из Новосибирска и Алтая вышли в финал с 20 и 35 места по России. В финале они стали 13-ми и 20-ми соответственно. Российские же команды выступают на финале очень хорошо: не менее трёх команд из нашей страны борются за звание чемпионов мира. На протяжении двух последних лет звание абсолютных чемпионов выигрывают студенты из Санкт-Петербурга. Это одно из массовых студенческих мероприятий, которое неизменно вызывает интерес, количество участников по всему миру уже исчисляется десятками тысяч.

Виталий ДЕМИДЕНКО, участник команды-победителя «Бизоны»:

— Для меня программирование — это главное хобби. Мы тренируемся много лет и командно, и лично. Я участвую, в первую очередь, чтобы попасть в финал, до которого из нашего края ещё никто не доходил. Решаем задачи командно, стараемся распределять на всех, знаем, кто какие темы лучше прорабатывает. Каждый обычно сидит за своей задачей, но если есть проблемы, то подключаемся к ней все. Ссоримся? Нет, мы слишком давно друг друга знаем, чтобы поссориться, но любим друг друга подкалывать. Во время соревнований есть свой особый адреналин, когда отправляешь задачу за одну-две минуты до окончания времени, и её решение оказывается верным. Это невероятный калейдоскоп эмоций!

Григорий ОХОТНИКОВ, участник команды SFU ISIT 5:

— Каждая олимпиада по программированию несёт в себе соревновательный дух, интеллектуальное состязание в гибкости ума и быстроте мышления. Для меня решение олимпиадных задач — это раскалывание орешков компьютером. Причём, иногда очень твёрдых орешков, над которыми можно раздумывать месяцами. Мне трудно описать то смешанное с восторгом и детской радостью чувство, которое возникает внутри при виде зелёной надписи «Accepted» на экране (это означает, что твоё решение прошло все тесты, и задача считается решённой). Такое своеобразное моральное вознаграждение подталкивает браться за новые и новые задачи, искать решение, биться с коварными тестами и радоваться каждому маленькому успеху.

Я не скажу, что мы довольны своими результатами. Каждый из нас совершенно точно осознаёт, что результат выступления на 90% зависит от подготовки. А осознание собственного несовершенства и есть лучший двигатель к саморазвитию. Настоящий победитель должен бороться до последней секунды и не бояться смелых решений. Ему присущи пытливый ум, нешаблонное мышление и малая толика настоящей изобретательности. Он умеет признавать собственные ошибки, но что ещё важнее — он работает над ними, улучшает и совершенствует свои методы. Некоторые считают, что успешному олимпиаднику просто необходимо уметь набирать слепым десятипальцевым методом. Может быть, в этом и есть доля правды: тогда не придётся отвлекаться на технические мелочи.

Анастасия АНДРОНОВА
Благодарим за помощь в подготовке материала Сергея ВИДЕНИНА
Средняя оценка: 4.6 (проголосовало: 14)