Год из года можно видеть в заголовках новостей яркие фразы вроде «Российские программисты снова одержали победу»; да и наш президент не обходит этот вопрос стороной. Слова-то, конечно, приятные, но вот что всё это значит?

Как проходит первенство

Соревнований по программированию в мире много, но среди всех особо выделяется ACM ICPC — Association for Computing Machinery International Collegiate Programming Contest — Международное Межвузовское Первенство по Программированию, которое проводит небезызвестная ACM. Структура контеста проста — Не более двенадцати команд от вуза на четверть-финала, не более четырёх — на полу-финал, и лишь одна — на финал. В течение одного тура соревнования, который, за исключением технических деталей, длится пять часов, каждая команда должна написать наибольшее количество программ, решающих задачи из числа предложенных; а их, как правило, от восьми до шестнадцати. С технической точки зрения программы простейшие: ни тебе GUI, ни работы с базами данных, ни других подобных свистелок: простое консольное приложение — прочитай что-то, обработай и выведи результат вычислений.
Однако всё кажется таким простым лишь на первый взгляд: мало того, что для решения задачи требуются серьёзные математические познания и смекалка, так ещё и критерии оценки крайне строги:

• Корректность: программа должна всегда выводить верный ответ;
• Надёжность: программа не должна «падать»;
• Эффективность по времени: общее время работы программы на всех тестах не должно превышать установленного предела; чаще всего — от доли секунды до нескольких секунд;
• Эффективность по памяти: объём памяти, который программа использует для своей работы, сильно ограничен;

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

Пример олимпиадной задачи

Рассмотрим простой пример: пусть нужно написать программу, которая примет на вход массив чисел, а затем будет выполнять запросы вроде getmax чтобы получить наибольшее число, или modify a b, чтобы заменить a на b? А что, если размер массива — миллион, а нужно выполнить сто тысяч запросов? А что если числа можно удалять? А что если нужно выводить k-е по размеру число? А что если числа заменить на строки? И при этом — на всё есть лишь секунда и какая-то жалкая пара мегабайт памяти. Всё уже не кажется настолько тривиальным, не правда ли? И этот пример — простейший, у олимпиадника такая задача отнимет всего несколько минут.

А я тут причём?

Логично считать, что навыки олимпиадного программирования пригодятся любому специалисту, ведь тогда он начнёт серьёзно следить за эффективностью своих творений. Если это интересует читателей, я буду вполне рад продолжать публикации в этом направлении, а именно: для начала «как стать олимпиадником», «от каких привычек следует отказаться», затем могу пополнять блог «алгоритмы» и рассматривать отдельные особо интересные и примечательные олимпиадные задачи.

P.S. Я тут новичок, поэтому не пойму: а где лучше размещать подобные посты? Разрываюсь между Алгоритмами, Ненормальным Программированием и Учебным Процессом. Как вы думаете? — спасибо khayrov
P.P.S. Разумеется, перенести в соответствующий блог я пока не могу в силу отсутствия кармы. Кстати, в помощи ничего не нашёл про ограничения для новичков на публикацию в коллективных блогах. Я плохо искал, или их действительно нет? — спасибо Mithgol
P.P.P.S Copyright фотографии: David Hill, взята из фотоархива ACM ICPC.

UPD: перенёс в блог спортивное программирование. Спасибо за карму и разъяснения.
UPD2: Пост #2 с нами.