На четвёртом курсе наша провинциальная команда (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 октября – как раз прошло ровно пять месяцев. И по внутренним ощущениям всё по-настоящему здорово.
Вот так вот, с одного короткого разговора начался путь олимпиадника в промышленное программирование. И я уверен, что это только начало. Так что, ребят, дерзайте, учитесь, тренируйтесь, - и всё непременно получится!
Задача А:
Паркет
Ограничение по памяти: 16 Мб
В далекой заморской земле в самом большом здании города, представляющем собой прямоугольник размерами
N
´
M
, решено положить новый паркетный пол. После продолжительных обсуждений на всеобщем городском совете был, наконец, одобрен следующий проект: фигурками вида (только такие паркетные доски и производит местная паркетная фабрика):
уложить вот такой рисунок (рисунок начинается с левого верхнего угла):
Ясно, что некоторые из приобретенных фигурок при укладке рисунка придется распилить. При этом возможно, некоторые части, на которые разделили фигурку, не будут участвовать в формировании рисунка. Вам необходимо определить минимальное количество фигурок требующих распила. Например, если размеры здания 3 x 4, то можно будет уложить 2 целых фигурки, а еще одну придется распилить. На рисунке ниже части, на которые распилили дополнительную фигурку, закрашены серым цветом.
Формат выходного файла: Необходимо вывести одно целое число – количество фигурок, которые придется распилить при укладке рисунка.
Пример:
parket.in | parket.out |
Задача В: Словарь
Ограничение по времени: 1 секунда
Ограничение по памяти: 16 Мб
В языке одного из племен, затерянных на марсианских просторах, все слова одной и той же длины
N , причем буквы в каждом слове попарно различны. В алфавите этого племени насчитывается N букв. Ученые-марсологи выяснили, что в словарь входят все возможные перестановки из N букв.Переводчик в своем походном марсианско-русском словаре обозначает первую букву марсианского алфавита за « A », вторую за « B » и так далее (N не превосходит 20). Разумеется, слова в словаре упорядочены по алфавиту. И когда он встречает в какой-нибудь марсианской книге редко используемое слово, ему приходится долго листать словарь в поисках перевода. Помогите переводчику по марсианскому слову определить его порядковый номер в словаре.
Формат входного файла: В первой строке файла записано натуральное число N , не превосходящее 20, - длина слова. Следующая строка содержит марсианское слово для перевода. Слово состоит из заглавных латинских букв.
Формат выходного файла: Необходимо вывести одно целое число – порядковый номер этого слова в марсианско-русском словаре.
Примеры:
slovar.in | slovar.out |
|
ABC | |
4
|
Задача C: Школа
Ограничение по времени: 1 секунда
Ограничение по памяти: 64 Мб
В школе некоторые из ребят хотели бы перейти из своего класса в другой, параллельный. Однако сделать это можно только в том случае, если кто-то из учеников этого класса также решит сменить класс – и освободит, таким образом, место. Скажем, ученик «10А» Антон сможет перейти в «10Г», если, например, Вера из «10Г» захочет перейти в «10Б», а Лена из «10Б» – в «10А».
Вам известны предпочтения ребят (ровно одно для каждого ученика). Необходимо определить длину максимальной цепи переходов учеников из класса в класс. Например, в разобранном выше случае длина цепи переходов составляет 3.
Формат входного файла: В первой строке входного файла задано количество N учеников, желающих перейти в другой класс. Каждая из следующих N строк состоит из имени ученика, буквы класса (отделенной от имени одним пробелом), в котором он учится, и отличной от нее буквы класса (также отделенной одним пробелом), куда хочет перейти. Используются только латинские буквы. Буквы класса – прописные. Длина имени ученика не превосходит 20.
Формат выходного файла: Одно целое число – длина максимальной цепи переходов.
Пример:
school.in |
Демонстрации:
- 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 с.
"...сюда в двенадцать часов новогодней ночи, прорвавшись через пургу, пришли люди, которым было интереснее доводить до конца или начинать сызнова какое-нибудь полезное дело, чем глушить себя водкой, бессмысленно дрыгать ногами, играть в фанты и заниматься флиртом разных степеней легкости... Они были магами потому, что очень много знали, так много, что количество перешло у них наконец в качество, и они стали с миром в другие отношения, нежели обычные люди".
А. и Б. Стругацкие.
«В наше время считается общепризнанным,
что из всего, так или иначе касающегося искусства,
ничто более не может считаться общепризнаным»
Теодор Адорно
Все началось с того, как один человек пытался выяснить решение задачи контеста, который проходил в данный момент. Задача была очень простая, всем было очевидно, что этот человек не займет хорошего места, не получит футболку и т.п. Но тем не менее ни один из 5000+ членов сообщества не дал ни одной подсказки (ну или хотя бы из 30+ человек, которые это видели и знали ответ). Мне такой результат уже давно кажется закономерным и я попробовал объяснить его в двух словах. Теперь попробую чуть более подробно. Заранее прошу прощения у людей, которые в это понятие вкладывают не то, что я. Я лишь хотел изложить свой взгляд.
Сначала немного теории из википедии: Программирование , Олимпиады по программированию , Искусство . Обратите внимание, в последней статье указано "Понятие искусства крайне широко - оно может проявляться как чрезвычайно развитое мастерство в какой-то определённой области".
Мне всегда казалось, что программирование, это своего рода искусство. Вот есть узкая область - класс олимпиадных задач по программированию. Умение быстро и точно решать задачи схоже со спортом, и часто олимпиадное программирование называют спортивным, ведь здесь, как и в спорте, сначала несколько лет тренируешься, потом один раз выступаешь, сливаешь все нафиг и забиваешь на программирование достигаешь некоторых результатов и радуешься им. Но с другой стороны спорт - не сильно творческое занятие. Обычно стратегии составляются не главными участниками и они не блещут оригинальностью и красотой. А в программировании все не так.
Никто не будет спорить, что стихи - искусство. А ведь, что такое стихи? Стихи - это умение вкладывать свои мысли в четкие рамки ритма и рифмы, стиля и словарного набора. Есть множество ограничений, которые не дают просто излагать то, что ты хочешь. Зачем же они? Это добавляет стиху красоты и изящества, это показывает, что автор вложил усилия, чтобы выразить свои мысли таким образом, соответственно, эти мысли были тщательно обдуманы автором, обточены и получили материальную форму в виде стиха. Кроме того, язык мыслей сильно отличается практически от всех языков мира, будь это язык слов, язык изображений, язык звуков или язык архитектуры.
Похожим образом ситуация обстоит и с программированием. Если автор хочет написать стих, ему надо представить мысль, а затем создать стих, выражающий эту мысль. Для того, чтобы решить задачу, требуется сначала придумать решение, а потом последовательно превратить его в алгоритм, потом в программу на языке программирования. Но язык программирования плохо сочетается с языком мыслей, поэтому, мы должны найти способ выразить нашу мысль через этот язык. И мы год за годом улучшаем это умение создавая все более и более совершенные произведения искусства.
Вот вы видите доску в городском доме творчества. На доске сверху ровными буквами написано "Выставка детских рисунков", а под надписью уже не столь ровно изображены различные эпизоды из детского быта. Попробуйте ответить - это искусство? Мой ответ - да, безусловно. Эти дети нашли свой способ общаться с миром, показывать ему свои мысли. Пусть они весьма примитивны и грубо изображены (хотя, бывает по-разному, некоторые дети способны на шедевры, которые и не снились взрослым художникам), но это искусство. Возможно, когда нибудь, один из этих детей будет писать легендарные картины, и люди со всего света будут приезжать, чтобы посмотреть на них. Все начинается с малого.
Я бы хотел, чтобы подобные общества были своего рода клубами искусства программирования(как, например, будетляне), в которых люди общаются, делятся секретами, творят вместе, помогают новичкам, но никогда не будут выдавать чужие мысли за свои.
Буду поддерживать список неплохих комментариев и дополнений.
В России олимпиадным программированием занимаются уже достаточно давно. Школьные олимпиады проводятся с конца 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 лет подряд становятся чемпионами мира! А этим сколько видов спорта могут похвастаться?
