Разбор задач с олимпиад.
Этот раздел предназначен для пользователей, начинающих осваивать программирование и служит ознакомительным аспектом с областью олимпиадного программирования. Если Вы пока не знаете что из себя представляют олимпиадные задачи, как они представлены и какие критерии оценки для проверки решения существуют, то этот раздел именно для Вас.
В отличии от обычных программ, создаваемых программистами повседневно, класс олимпиадных задач достаточно узок, но практичен с точки критериев выявления способности участников программировать за короткий срок. Как правило, олимпиадная задача представляет собой некоторую проблему, для решения которой требуется использовать свой IQ почти напределе, однако, сам текст программы может быть совсем незначительным и помещаться на одной странице.
Если человек не занимался программированием, то предположительно можно оценить его способности к этой области в случае ее изучения. Многие полагают, что способности программировать связаны с умением решать математические и комбинаторные задачи. Другими словами, если у Вас в школе твердая пятерка по алгебре, геометрии и иным математическим дисциплинам, а так же умеете хорошо играть в шашки и шахматы, то вполне вероятно, что будете неплохо программировать, если начнете этим заниматься. И наоборот, если в школе у Вас тройка по алгебре, как бы вы не старались, то вряд ли программирование - это то, чем Вам стоит заниматься. Так же следует отметить, что Ваши заслуги в области освоения гуманитарных предметов мало Вам помогут в освоении программирования, которое, как Вы уже поняли, относится к точным наукам.
Приведем условную классификацию олимпиадных задач:
- Арифметика - математические задачи, работа с большими числами (длинная арифметика), такие задачи, как правило, требуют знания формул, умение их применять, а код программ может быть небольшим
- Геометрия - геометрические задачи, здесь может быть описана какая либо ситуация взаимодействия тел на плоскости и в пространстве
- Динамическое программирование - задачи, направленные на выявление рекуррентных соотношений
- Сортировка и последовательности - работа с данными, представленными в виде массива
- Графы - задачи с графами (структурами данных, основаных на вершинах и ребрах)
- Рекурсия - задачи на поиск с рекурсивным перебором вариантов
Конечно же задачи могут сочетать в себе сразу несколько направлений и часто бывает сложно конкретную задачу отнести к тому или иному разделу.
Любая олимпиадная задача подразумевает входные и выходные данные. Т.е. в формулировке задания обязательным образом описан формат входных и выходных данных, а Ваша программа должна считать эти данные, обработать и вывести результат в установленном формате. Чаще всего чтение происходит из некоторого файла INPUT.TXT, а вывод в некоторый файл OUTPUT.TXT . Т.е. для решения олимпиадных задач нужно уметь работать с файлами: читать, создавать и писать в них, а вот знания графических функций вряд ли Вам пригодятся. Стоит заметить, что многие системы, например http://acm.timus.ru , используют консольный режим ввода-вывода и работа с файлами в них не приветствуется. Данный сайт позволяет сдавать задачи как с использованием вышеупомянутых файлов, так и без них. Вариант ввода-вывода Вы выбираете сами. Помимо условия задачи, правил ввода и вывода информации на каждую задачу накладываются ограничения на время выполнения и используемую Вашей программой оперативную память.
Приведем пример формулировки олимпиадной задачи по программированию (Задача №1 в текущей системе из раздела Архив задач):
A+B
(Время: 1 сек. Память: 16 Мб Сложность: 2%)Требуется сложить два целых числа А и В.
Входные данные
В единственной строке входного файла INPUT.TXT записано два натуральных числа через пробел, не превышающих 10 9 .
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число - сумму чисел А и В.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 | 2 3 | 5 |
Эта классическая простая задача используется для ознакомления участников с системой автоматической проверки и соответствует всем критериям правильной постановки олимпиадной задачи. При решении этой задачи необходимо из входного файла input.txt (либо с клавиатуры), расположенного в текущей папке (где и Ваша программа) считать 2 целых числа и вывести их сумму в выходной файл output.txt (либо на экран). Ограничения по памяти в 16Мб и времени 1 сек. весьма условны, так как такая простая задача потребует минимальную память и выполнится за минимальный промежуток времени (операция сложения выполнится мгновенно, современные ЭВМ способны выполнять 10 8 таких операций в секунду). Каждая задача имеет пример входных и выходных данных (часто даже несколько примеров), это позволяет участникам более однозначно понять содержание задачи. В данном примере в разделе "Пример" отражен пример входных данных "2 3" и выходных "5", это означает, что 2+3=5.
В зависимости от правил соревнований или тестирующей системы могут использоваться те или иные языки программирования. Приведем наиболее часто используемые средства создания программ приведены в разделе "Дистрибутивы" , откуда их возможно скачать и установить на свой компьютер.
В мире предпочтение отдается языку С++, но в России по-прежнему классическим языком программирования остается Pascal, а именно, большинство олимпиадных задач в России решается на Delphi. Мы же рекомендуем осваивать язык С++, который со временем станет наиболее популярным и в нашей стране. Далее мы в основном будем использовать язык С++ для рассмотрения примеров решения задач. можно ознакомиться с различными средами разработки программ на С++ на примере решения задачи "А+В".
Теперь Вы можете ознакомившись с работой системы , сдать задачу "A+B" на этом сайте . Другие задачи можно найти в "Архиве задач" и в "Курсах" . Быстрый переход по номеру задачи возможен с главной страницы с помощью раздела "Поиск по сайту", если в поисковой строке ввести "#N" или "№N" (без кавычек), где N - номер задачи.
Демонстрации:
- indy256"s CodeLibrary (GitHub)
- R. Sedgewick and K. Wayne"s Java Algorithms and Clients (GitHub)
Книги
Алгоритмы (классические учебники)
- Introduction to Algorithms / Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. — 3rd ed. — Cambridge, MA: MIT Press, 2009. — 1292 p. (сайт книги)
- Sedgewick R., Wayne K. Algorithms / Robert Sedgewick, Kevin Wayne. — 4th ed. — Boston, MA: Addison-Wesley, 2011. — 976 p. (сайт книги)
- Skiena S. The Algorithm Design Manual / Steven S. Skiena. — 2nd ed. — London: Springer-Verlag, 2008. — 746 p. (сайт книги)
Олимпиадное программирование
- Art of Programming Contest / Ed. by A. S. Arefin. — 2nd ed. — Dhaka: Gyankosh Prokashoni, 2006. — 247 p.
- Halim S. Competitive Programming / Steven Halim, Felix Halim. — Raleigh, NC: Lulu, 2010. — 152 p.
- Долинский М. С. Решение сложных и олимпиадных задач по программированию / М. С. Долинский. — СПб.: Питер, 2006. — 366 с.
- Окулов С. М. Основы программирования / С. М. Окулов. — 4-е изд. — М.: БИНОМ, 2008. — 440 с.
- Окулов С. М. Программирование в алгоритмах / С. М. Окулов. — 3-е изд. — М.: БИНОМ, 2007. — 383 с.
- Порублев И. Н., Ставровский А. Б. Алгоритмы и программы. Решение олимпиадных задач. — М.: Вильямс, 2007. — 480 с.
- Скиена С. С., Ревилла М. А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям / С. С. Скиена, М. А. Ревилла. — М.: КУДИЦ-ОБРАЗ, 2005. — 416 с.
Сборники задач
- Алексеев А. В., Беляев С. Н. Подготовка школьников к олимпиадам по информатике с использованием веб-сайта / А. В. Алексеев, С. Н. Беляев. — Ханты-Мансийск: РИО ИРО, 2008. — 284 с.
- Брудно А. Л., Каплан Л. И. Московские олимпиады по программированию / Под ред. Б. Н. Наумова. — 2-е изд. — М.: Наука, 1990. — 208 с.
- Кирюхин В. М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады / В. М. Кирюхин, С. М. Окулов. — М.: БИНОМ, 2007. — 600 с.
- Московские олимпиады по информатике / Под ред. Е. В. Андреевой, В. М. Гуровица и В. А. Матюхина. — М.: МЦНМО, 2006 — 256 с.
- Московские учебно тренировочные сборы по информатике. Весна–2006 / Под ред. В. М. Гуровица. — М.: МЦНМО, 2007 — 194 с.
- Меньшиков Ф. В. Олимпиадные задачи по программированию / Ф. В. Меньшиков. — СПб: Питер, 2006. — 315 с.
- Особенности национальных задач по информатике / В. И. Беров, А. В. Лапунов, В. А. Матюхин, А. Е. Пономарёв. — Киров: Триада-С, 2000. — 160 с.
- Шень А. Программирование: теоремы и задачи / А. Шень. — 2-е изд. — М.: МЦНМО, 2004 — 296 с.
Литература по темам
Алгоритмы и структуры данных
- Erickson J. Algorithms / Jeff Erickson. — Urbana, IL: University of Illinois at Urbana-Champaign, 2015. — 514 p.
- Sedgewick R., Flajolet P. An Introduction to the Analysis of Algorithms / Robert Sedgewick, Philippe Flajolet. — 2th ed. — Boston, MA: Addison-Wesley, 2013. — 592 p.
- Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. — М.: Мир, 1979. — 536 с.
- Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы / Альфред В. Ахо, Джон Хопкрофт, Джеффри Д. Ульман. — М.: Вильямс, 2000. — 384 с.
- Бабенко М. А., Левин М. В. Введение в теорию алгоритмов и структур данных / М. А. Бабенко, М. В. Левин. — М.: МЦНМО, 2016. — 144 с.
- Вирт Н. Алгоритмы и структуры данных / Н. Вирт. — М.: Мир, 1989. — 360 с.
- Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы / С. Дасгупта, Х. Пападимитриу, У. Вазирани. — М.: МЦНМО, 2014. — 320 с.
- Клейнберг Дж., Тардос Е. Алгоритмы: разработка и применение / Джон Клейнберг, Ева Тардос. — СПб: Питер, 2016. — 800 с. (слайды лекций)
- Левитин А. В. Алгоритмы: введение в разработку и анализ / Ананий В. Левитин. — М.: Вильямс, 2006. — 576 с.
- Макконнелл Дж. Анализ алгоритмов. Вводный курс / Дж. Макконнелл. — М.: Техносфера, 2002. — 304 с.
- Стивенс Р. Алгоритмы. Теория и практическое применение / Род Стивенс. — М.: Э, 2016. — 544 с.
Дискретная математика
- Асанов М. О. Барановский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы / М. О. Асанов, В. А. Барановский, В. В. Расин. — СПб.: Лань, 2010. — 368 с.
- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики / Р. Грэхем, Д. Кнут, О. Паташник. — М.: Мир, 1998. — 703 с.
- Кук Д., Бейз Г. Компьютерная математика / Д. Кук, Г. Бейз. — М.: Наука, 1990. — 384 с.
- Новиков Ф. А. Дискретная математика для программистов / Ф. А. Новиков. — 2-е изд. — СПб.: Питер. 2007. — 364 с.
- Окулов С. М. Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — 2-е изд. — М.: БИНОМ, 2012. — 422 с.
- Хаггарти Р. Дискретная математика для программистов / Р. Хаггарти — М.: Техносфера, 2004. — 320 с.
Вычислительная геометрия
- Computational Geometry: Algorithms and Applications / Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. — 3rd ed. — Berlin: Springer-Verlag, 2008. — 386 p.
- Андреева Е. В., Егоров Ю. Е. Вычислительная геометрия на плоскости / Е. В. Андреева, Ю. Е. Егоров. // Информатика. — 2002. — №39, 40, 43, 44
- Препарата Ф., Шеймос М. Вычислительная геометрия / Ф. Препарата, М. Шеймос. — М.: Мир, 1989. — 478 с.
На четвёртом курсе наша провинциальная команда (Orel STU) пробилась на финал ACM ICPC. Это был, мягко говоря, феерический успех – ведь мы никогда не срывали звёзд с неба, да и отбор был посерьёзнее, чем нынче. К нашей неугомонной радости случилась революция в Египте, которая стала причиной переноса финала из Шарм-Эль-Шейха в город Орландо солнечных штатов Америки.
А там-то и случился тот короткий разговор. Как-то вечером в chill zone мы болтали с Мишей Левиным о танцевальном агрегате, как вдруг подошёл на тот момент мне неизвестный Серёжа Чернышёв и, опознав по футболке участника финала, спросил: «В Яндекс к нам хочешь?» А чего отказываться? =)
Всё получилось как-то удивительно просто. Перекинулись парой писем. Уладили какую-то бюрократию - анкетку заполнить, даты согласовать. У меня оказался один формальный начальник и сразу несколько реальных.
Схема летней стажировки меня устраивала абсолютно: я приезжаю в середине лета, меня обеспечивают едой и жильём, два с половиной месяца стажируюсь и в конце сентября еду обратно в город-птицу, дабы доучиться последний курс и защитить диплом.
Забавно, но первый «рабочий» день совпал с закрытием ШАДа и подведением итогов Яндекс.Алгоритма. Так что я бы приехал в Москву всё равно. =) Рабочий день мне понравился. До четырёх часов вечера я тусил с друзьями-олимпиадниками в Экстрополисе и поедал куриные шашлычки. Не выходя из здания получил бейджик с серьёзной надписью: «Департамент разработки».
Вообще надо отметить, что я серьёзно переживал. Когда, когда мне дадут первое задание? Хватит ли моих скудных олимпиадных знаний, чтобы с ним справиться? Два с половиной месяца – это совсем немного, поэтому я ожидал уж если не галопам-по-европам, то хотя бы в-темпе-вальса mode on.
Однако никто даже не чесался. Ну, наверное, мне так казалось. Лёша Мирзоян с переменным успехом успокаивал меня: «тю, ну ты чего? Первую неделю знакомься с начальством, ребятами, офисом. Не заморачивайся!» В общем, конец дня прошёл попеременно то в бильярде, то в музыкальной комнате. ;)
Самым большим удивлением оказался мой сосед по жилищу. Саша Прудаев, с которым мы пару лет обсуждали по аське олимпиадные задачи, перебрался из далёкой Тюмени в столицу. И вышел на работу на два дня раньше меня. Вот так новость, вот так встреча! Другим моим соседом оказался Даниил Бурдаков, весьма толковый парнишка, с которым мы сейчас часто пересекаемся в ШАДе. Поэтому компашка подобралась что надо. Мы жили в двух минутах ходьбы от Нагорной и, с учётом того, что кольцевая Парка Культуры была закрыта на ремонт, тратили на дорогу порядка сорока минут в одну сторону.
На следующий день в моих руках оказался ноутбук. С виндой. Уже здорово, ибо линуксами я не пользовался в жизни. Задание начальство подобрало с душой. Нужно было каким-то образом научиться сравнивать документы на похожесть, ввести определение похожести и делать это всё достаточно быстро – ну, в предположении, что у нас овер 10^9 документов.
Но давайте обо всём по порядку. Меня записали в практикантский проект Ябракадабра, где занимались новым поисковиком с нуля. На его основе можно уверенно изучать и демонстрировать архитектуру любого поисковика, объяснять принципы информационного поиска и прочая, и прочая.
В теории всё было не очень страшно. Страшно было на практике. На меня обвалилось столько ужасно незнакомых вещей, что даже гитом пользоваться не приходилось – вместе с ребятами я один-единственный раз выкачал репозиторий, а потом всё делал локально. Забегая вперёд, скажу, что в последний день летней стажировки отправил свой код на почту начальнику, а не что-то куда-то внедрил. Наверное, люди с опытом, читающие эти строки, катаются по полу от смеха, держась за животы.
Практически сразу я понял, что в промышленном программировании две беды: ООП и названия переменных. С горем пополам и божьей помощью декомпозировав задачу, я приступил к поиску решения. Ребята советовали разные статьи на практически неизвестном мне тогда английском про simhash и minhash. Но как должен поступить настоящий олимпиадник? Конечно же придумать что-то своё! (Не хватает только комикса со шваброй).
Читал статьи и думал я где-то неделю. Конечно же, не переставая знакомиться с окружением. Трудовые будни скрашивались няшным офисом, посиделками на кофепоинтах с Сашей Прудаевым и другими спортивными программистами. Дальше произошёл переломный момент, которым я горжусь до сих пор: я придумал решение. Это было в поезде метро, как сейчас помню. =) В дальнейшем практика показала, что оно оказалось уж точно не хуже аналогов, которые всё равно пришлось реализовывать для построения графиков и убеждения начальства.
В итоге, на своё первое ревью я «отправил» нечто, состоящее из 300+ строк кода. В свою защиту могу сказать, что эти 300+ строк полностью решали поставленную задачу. =)
Ребята бились в истерике. Артём Бабенко плакал кровавыми слезами и говорил, что больше пяти раз он не станет принимать мой код. Ещё один дико забавный момент был в том, что на распечатке (а ревью было именно таким – я распечатывал код, и мы шли его толпой читать) сверху указан путь вроде “…/cadabra/kpr/hash.cpp”. На соответствующий вопрос я соответствующе ответил, и Артём долго и регулярно мне потом со слезами на глазах вспоминал «Купринхэш». .
В дальнейшем мой код рос и ширился. Это было как-то глупо и странно, учитывая, что функциональность не менялась. Пять раз быстро исчерпались, и со мной существенную часть времени проводил другой начальник Егор Самосват. Несмотря на то, что я чувствовал себя идиотом и выглядел ничуть не умнее, происходящее мне нравилось. Фактически, я учился в одновременно комфортных и боевых условиях.
Приходило время летних петрозаводских сборов, куда я напросился поехать от Яндекса, дабы нести свет и добро (зачёркнуто) дабы рассказать о прелестях летней стажировки. Народ отреагировал не очень охотно, и тогда я вспомнил себя на младших курсах: настоящий олимпиадник будет заниматься олимпиадными задачами бесконечно. Что ж, господа, придёт и ваше время. ;)
Тем временем, мы переехали в другую квартиру, на Белорусской. Станция Парк Культуры всё ещё была закрыта, а к концу второго месяца стажировок у меня окончательно поехал режим. Полтора часа в день на дорогу тратить было просто лень, поэтому я проводил в офисе практически круглые сутки, ночуя в мягких переговорках, гамаках и на пуфах. Это было действительно здорово. Удавалось много времени проводить в музыкальной комнате – ночами напролёт я терзал синтезатор и гитары. Ночные прогулки по офису приводили в недоумение охранников, зато какая атмосфера!
А тем временем работа медленно подходила к концу. «Купринхэш» обрёл новое имя – FirstLetterHash, перерос из одного файла в десяток, у него появились новые возможности и братья, имеющие тот же интерфейс, собралась статистика по запросу “проблемы бытия”, и многое, многое другое.
Как мне кажется, по большому счёту я справился. Пусть и не так здорово, как могло бы быть, но справился. Дабы не терять контакты, меня пообещали взять где-то зимой на удалёнку.
А в родном университете вовсю шли дискуссии и баталии о темах дипломных работ. Договорившись заранее с ребятами из Яндекса, мне удалось убедить дипломного руководителя в бесконечном пафосе и практической применимости FirstLetterHash. Так что в некотором роде диплом у меня был в кармане – осталось налить воды в пояснительую записку, что оказалось вопросом пары недель.
1 февраля я снова «вышел» на работу. Вот тут-то мне понадобился и git, и putty, и многие другие ранее неведомые радости жизни. Задание снова оказалось классным. На этот раз по ключевым словам нужно было построить сниппет – небольшую склейку из кусочков исходного текста, которая бы одновременно содержала много ключевых слов и воспринималась человеком как выдержки из документа, а не нарезка фраз.
Динамическое программирование в помощь! Решение в этот раз оказалось практически на поверхности, вопрос был в ограничениях на время и память. Двухчасовой рабочий день оказался отвратительным форматом, поэтому обычно я выбирал в месяце одну неделю, во время которой плодотворно трудился, а в остальное время занимался своими делами.
По ощущениям я был предоставлен сам себе, и это сильно расслабляло. И, хотя я честно выполнил задачу, оттестировал и закоммитил, мне кажется, что я халявил. Где-то с апреля-мая, когда 90% работы оказалось выполнено, перестали поступать разумные задания, и здесь скорее логика была простая: с новой большой задачей я справиться не успею, а время ещё есть.
После успешной защиты диплома я поступил в магистратуру ВШЭ на программу, совмещённую с ШАДом Яндекса, то есть по сути пошёл учиться сразу в два места. Заботливая ВШЭ поселила будущих магистров в тихом уютном лесном посёлке под названием Дубки, за что спасибо ей большое. Практически сразу я пришёл к выводу, что пять часов на дорогу в сутки можно разменять на рабочий день на полставки и житьё недалеко от офиса.
Очень скоро подвернулась отличная возможность: на выезде ШАДа мой знакомый Паша Шишкин, золотой медалист ACM ICPC, объявил о том, что Яндекс.Картинки ищут разработчика. Ура, вот он, мой шанс!
Скоро состоялось собеседование, на котором я с превеликим трудом отвечал на вопросы теста под названием «pure evil c++ test 2», почему-то лишь со второй попытки верно решил несложную задачку по теорверу, но зато убил наповал скоростью написания алгоритмической задачки в промышленном стиле.
Правда позиции на полставки не было - лишь на полный рабочий день. Но, пожалуй, так даже лучше. В картинках я с 1 октября – как раз прошло ровно пять месяцев. И по внутренним ощущениям всё по-настоящему здорово.
Вот так вот, с одного короткого разговора начался путь олимпиадника в промышленное программирование. И я уверен, что это только начало. Так что, ребят, дерзайте, учитесь, тренируйтесь, - и всё непременно получится!
В России олимпиадным программированием занимаются уже достаточно давно. Школьные олимпиады проводятся с конца 80-х, студенческие с середины 90-х годов XX века. Так что это такое олимпиады по программированию нужны ли они или нет и если да то кому?
Давайте разберемся, что такое олимпиада по программированию?
Как устроена олимпиада?
Студенческая олимпиада организованна следующим образом:
Трое участников команды сидят перед одним компьютером. Им дается набор задач, которые они должны решить. Что значит решить задачу? Это значит написать программу, которая пройдет заранее заготовленный жюри набор тестов. Таким образом, задача решена, если она прошла весь набор, то есть полностью правильна с точки зрения жюри. Для любой программы есть ограничения по ресурсам, она не должна требовать слишком много памяти и работать слишком долго. Продолжительность олимпиады обычно 5 часов. Команды соревнуются между собой. Это значит, что в турнирной таблице выше находится та команда, которая решила больше задач. А из тех, которые решили одинаковое количество задач та, которая это сделала быстрее.
Школьные олимпиады обычно имеют свою особенность:
Чаще всего они не командные, а личные, и ребята не должны на 100% решить задачу, а могут решить только часть задачи и получить за это соответствующие баллы.
Какие задачи дают на олимпиадах?
Обычно это задачи из области программирования, информатики (Computer Science), различных разделов математики. Очень популярны задачи по поиску и обработке текста, задачи по криптографии, геолокации, теории игр, методов оптимизации, оптимального хранения и обработки данных, быстрого доступа к данным и другие.
На самом деле, каждый из нас встречается с решениями олимпиадных задач очень часто. Рассмотрим несколько примеров:
Поиск Маршрутов. Многие из нас пользуются различными приложениями по поиску маршрутов: 2GIS, Яндекс Карты, Google Maps и другие. Эти приложения подбирают для нас кратчайший маршрут с учетом разных факторов: транспорт, пробки, направление движения на дорогах, наличие пешеходного перехода и другие. Так вот, построить такой маршрут - это одна из классических олимпиадных задач: найти кратчайший путь в графе. Для этой ззадачи существуют различные подходы и алгоритмы. В частности, в создании сервиса Яндекс. Пробки активно принимали участие олимпиадники.
Другой пример: поиск сроки в тексте, вы часто пользуетесь поиском? Так вот поиск - тоже олимпиадная задача.
Третий пример уже более специализированный: во многих организациях возникает поток заказов, задач или заданий Есть несколько исполнителей, каждый может выполнять какие-то заказы, но стоимость выполнения разная. Как быстро и с минимальными затратами выполнить все заказы?
Какие навыки развиваются у олимпиадника?
Во-первых, ребята учатся решать не тривиальные задачи, часто из разных областей математики и программирования. Это позволяет с одной стороны иметь большой математический кругозор, с другой стороны видеть, что эти абстрактные математические задачи имеют привязку к жизни. Во вторых, оценивать свои решения в зависимости от имеющихся ресурсов (обычно это время и память, которые используют программы). Вряд ли кому-то нужна программа, которая работает сотни лет или требует все имеющиеся жесткие диски в мире. В-третьих, работать качественно и в короткие сроки, в олимпиадах время ограничено и принимается решение только 100% верное. В-четвертых, работать в команде: у участников есть только один компьютер, поэтому они вынуждены обсуждать, распределять роли в команде, писать код по очереди, помогать сокоманднику, если у него что-то пошло не так. В-пятых, ребята учатся искать потенциальные проблемы своих решений, готовить контрольные примеры, тестировать свои решения. В-шестых, это соревнование - ребята учатся какого это обходить других и когда обходят тебя, как взаимодействовать с другими и видят насколько много людей участвуют в этом движении.
Кому это все нужно?
Это нужно науке.
Ребята принимающие участие в олимпиадах имеют чаще всего уровень знаний математики намного выше среднего студента, умеет решать нестандартные задачи, имеет большой кругозор из разных областей математики и информатики, чего часто не хватает другим студентам. Да, другие студенты часто знают многое, но олимпиадники умеют применять свои знания при решении задач.
Отличие олимпиад от классической науки в том, что олимпиадники обычно решают задачи в короткие сроки, а ученые проводят за исследованиями много дней, и только тогда находят решения. Однако, олимпиадники также проводят много времен, раздумывая над задачами не во время самой олимпиады, а при подготовке. При этом на самой олимпиаде чаще всего применятся уже наработанные знания и навыки, всплывающие из глубин памяти и интеллекта. Те, которые были выработаны в процессе долгих размышлений.
Есть много примеров, когда олимпиадники становятся учеными: многие олимпиадники КФУ защитили свои кандидатские или сейчас в процессе, в Москве и Петербурга вы можете встретить ученых, которые в своем прошлом участвовали в олимпиадах. Известные ученые в области квантовой информатики - победители олимпиад.
Это нужно промышленности.
Навыки создания оптимальных, надежных программ в короткие сроки, работы в команде, умение решать нетривиальные задачи - это то, что требуется любой IT-компании.
Многие компании, такие как Facebook, Google, Яндекс, Mail.ru, VK, Huaweii и друге организовывают собственные олимпиады и приглашают к себе сотрудников по их результатам. Многие компании принимают олимпиадников без собеседования или на льготных условиях. Третьи компании, к примеру Google, и другие проводят собеседование на олимпиадных задачах.
Потому что они понимают, что люди, которые могу решить сложную задачу, написать эффективный код и работать в команде - это те кто смогут обеспечить им обработку не 100 тысяч пользователей, а миллиона или 100 миллионов с той же скоростью, это те кто потом помогут написать распознавание лиц в их программах или построение оптимального маршрута. Это те, кто для компаний помогут заработать новые деньги, а пользователи из-за них будут считать, что внутри программ скрыта “магия”.
Да и просто люди, которые в студенческие годы написали сотни тысяч программ на много лучше будут работать, чем те, которые писали 100-200 программ в рамках своих домашних заданий в университете.
Небольшая социально-культурная составляющая.
Олимпиады позволяют познакомиться ребятам с будущей элитой IT-сообщества, попутешествовать по разным городам, Принять участие в соревнованиях, померяться силами с лучшими программистами мира.
В заключении.
Некоторые люди ругают олимпиады, другие их восхваляют. Нельзя сказать что олимпиады - полная замена каким-то предметам в университете, как некоторые пытаются это представить, но олимпиады это очень хорошее подспорье для будущих ученых, программистов, аналитиков.
Это интеллектуальный спорт, в котором спортсмены после окончания своей карьеры могут приносить реальную пользу обществу. Скажите, много ли видов спорта могут похвастаться этим? Это тот спорт, в котором участвуют большинство ведущих университетов мира. Победители в котором, известны IT и научному сообществу.
P.S. Кстати, это вид спорта в котором Россияне уже 5 лет подряд становятся чемпионами мира! А этим сколько видов спорта могут похвастаться?
"...сюда в двенадцать часов новогодней ночи, прорвавшись через пургу, пришли люди, которым было интереснее доводить до конца или начинать сызнова какое-нибудь полезное дело, чем глушить себя водкой, бессмысленно дрыгать ногами, играть в фанты и заниматься флиртом разных степеней легкости... Они были магами потому, что очень много знали, так много, что количество перешло у них наконец в качество, и они стали с миром в другие отношения, нежели обычные люди".
А. и Б. Стругацкие.
«В наше время считается общепризнанным,
что из всего, так или иначе касающегося искусства,
ничто более не может считаться общепризнаным»
Теодор Адорно
Все началось с того, как один человек пытался выяснить решение задачи контеста, который проходил в данный момент. Задача была очень простая, всем было очевидно, что этот человек не займет хорошего места, не получит футболку и т.п. Но тем не менее ни один из 5000+ членов сообщества не дал ни одной подсказки (ну или хотя бы из 30+ человек, которые это видели и знали ответ). Мне такой результат уже давно кажется закономерным и я попробовал объяснить его в двух словах. Теперь попробую чуть более подробно. Заранее прошу прощения у людей, которые в это понятие вкладывают не то, что я. Я лишь хотел изложить свой взгляд.
Сначала немного теории из википедии: Программирование , Олимпиады по программированию , Искусство . Обратите внимание, в последней статье указано "Понятие искусства крайне широко - оно может проявляться как чрезвычайно развитое мастерство в какой-то определённой области".
Мне всегда казалось, что программирование, это своего рода искусство. Вот есть узкая область - класс олимпиадных задач по программированию. Умение быстро и точно решать задачи схоже со спортом, и часто олимпиадное программирование называют спортивным, ведь здесь, как и в спорте, сначала несколько лет тренируешься, потом один раз выступаешь, сливаешь все нафиг и забиваешь на программирование достигаешь некоторых результатов и радуешься им. Но с другой стороны спорт - не сильно творческое занятие. Обычно стратегии составляются не главными участниками и они не блещут оригинальностью и красотой. А в программировании все не так.
Никто не будет спорить, что стихи - искусство. А ведь, что такое стихи? Стихи - это умение вкладывать свои мысли в четкие рамки ритма и рифмы, стиля и словарного набора. Есть множество ограничений, которые не дают просто излагать то, что ты хочешь. Зачем же они? Это добавляет стиху красоты и изящества, это показывает, что автор вложил усилия, чтобы выразить свои мысли таким образом, соответственно, эти мысли были тщательно обдуманы автором, обточены и получили материальную форму в виде стиха. Кроме того, язык мыслей сильно отличается практически от всех языков мира, будь это язык слов, язык изображений, язык звуков или язык архитектуры.
Похожим образом ситуация обстоит и с программированием. Если автор хочет написать стих, ему надо представить мысль, а затем создать стих, выражающий эту мысль. Для того, чтобы решить задачу, требуется сначала придумать решение, а потом последовательно превратить его в алгоритм, потом в программу на языке программирования. Но язык программирования плохо сочетается с языком мыслей, поэтому, мы должны найти способ выразить нашу мысль через этот язык. И мы год за годом улучшаем это умение создавая все более и более совершенные произведения искусства.
Вот вы видите доску в городском доме творчества. На доске сверху ровными буквами написано "Выставка детских рисунков", а под надписью уже не столь ровно изображены различные эпизоды из детского быта. Попробуйте ответить - это искусство? Мой ответ - да, безусловно. Эти дети нашли свой способ общаться с миром, показывать ему свои мысли. Пусть они весьма примитивны и грубо изображены (хотя, бывает по-разному, некоторые дети способны на шедевры, которые и не снились взрослым художникам), но это искусство. Возможно, когда нибудь, один из этих детей будет писать легендарные картины, и люди со всего света будут приезжать, чтобы посмотреть на них. Все начинается с малого.
Я бы хотел, чтобы подобные общества были своего рода клубами искусства программирования(как, например, будетляне), в которых люди общаются, делятся секретами, творят вместе, помогают новичкам, но никогда не будут выдавать чужие мысли за свои.
Буду поддерживать список неплохих комментариев и дополнений.