Олимпиадное программирование с чего начать
Инструкция: как стать «мастером спорта» по программированию
В карьере разработчика нет высшей финальной точки – осваивать новое приходится постоянно. Зато можно быстро прокачать навыки и перепрыгнуть сразу несколько ступенек карьерной лестницы. Лучший способ это сделать – освоить спортивное программирование.
Школу олимпиадного кодинга прошли сотни тысяч айтишников, в том числе топ-менеджеры Google, Facebook и VK. Команда Moscow Workshops составила подробную инструкцию для начинающего «спортсмена».
Спортивное программирование, как понятно из названия, – это разновидность интеллектуального спорта. Разработчики решают сложные алгоритмические задачи на скорость, используя популярные языки программирования – в основном C/C++, Kotlin, Java и Python.
Существуют как локальные конкурсы, например, мини-турниры на платформах Codeforces, TopCoder или Codechef, так и крупные международные чемпионаты и олимпиады, в которых участвуют десятки тысяч программистов.
От обычного промышленного программирования спортивное отличается более жесткими требованиями и регламентами. Инструменты и задачи на контестах порой оказываются сложнее, чем в офисе. Поэтому спортивные программисты часто становятся выдающимися разработчиками.
Во-первых, это сильно затягивает. На платформе Codeforces зарегистрировано больше 750 тыс. человек и из них 60 тыс. участвует в рейтинговых раундах. Большинство решает задачи в свободное от работы время, чтобы получить красный статус гроссмейстера.
Интервью со спортивными программистами и видео с лайфхаками собирают миллионы просмотров на YouTube. Например, ролик, в котором Геннадий Короткевич завершает финальный раунд чемпионата Google Code Jam, посмотрели почти полмиллиона раз. Геннадий Короткевич – легенда спортивного программирования, двукратный чемпион мира, который победил практически во всех существующих соревнованиях.
Во-вторых, спортивное программирование быстро прокачивает полезные навыки. Постоянные тренировки в алгоритмах и математике помогают выработать устойчивый навык писать сложный код быстро и без ошибок, а если они всё-таки возникают, то спортивный программист уверенно их находит и исправляет.
Из спортивного программирования выходят успешные предприниматели и топ-менеджеры. Например, бывший CTO Facebook и основатель Quora Адам Д’анджело или сооснователь стартапа AI Factory Александр Машрабов, который продал свою компанию гиганту Snap. Ну а о том, какую роль спортивные программисты сыграли в истории «ВКонтакте» и Telegram, можно не упоминать.
Кстати, именно в России базируются лучшие спортивные программисты. Россия стабильно занимает верхние строчки рейтингов Google Code Jam, Facebook Hacker Cup и TopCoder Open, а на студенческих турнирах МГУ, ИТМО, МФТИ и НИУ ВШЭ обходят MIT, Гарвард, Оксфорд, Кембридж и Университет Цинхуа.
Проверьте «базовые настройки». Спортивное программирование не лучший вариант для новичка, который не владеет базовыми знаниями. Хотя контесты проводятся даже для школьников, не стоит недооценивать их сложность.
Главное для начинающего «спортсмена» – это знание хотя бы одного языка программирования. Лучше всего подойдут С, С++ и Java, но популярный сейчас Python тоже неплохой вариант для начала. Раньше в ходу был и Pascal, но на современных турнирах этот язык уже давно не практикуется.
Потребуется также знание английского на уровне достаточном, чтобы читать условия задач, общаться с жюри и понимать профессиональную лексику.
Также обязательно пригодится базовая математическая подготовка, знание векторной геометрии и тригонометрии. Делимость, ее свойства, представление целых чисел, теория графов, алгоритм Евклида – это точно нужно знать. Без опыта алгоритмического программирования и базовых знаний информатики тоже не обойтись. Увы, но школьных знаний в этих сферах недостаточно – на уроках и задачи не те, и инструменты другие.
Если планируете выступать на чемпионатах в высших дивизионах, потребуется более серьезная прокачка. Теория графов, остовные деревья, алгоритм Флойда – Уоршелла, преобразование Фурье, выпуклые оболочки, базовая теория игр, основы динамического программирования – все это вы должны знать так, чтобы, проснувшись посреди ночи, применить знания на практике.
Подтяните теорию. Чтобы лучше разбираться в алгоритмах, подтяните теорию. Начните с онлайн-курсов.
Начните решать задачи. Practice makes perfect – это правило работает и для спортивного программирования. Чтобы понять специфику заданий на соревнованиях, зарегистрируйтесь на популярных платформах, например, Timus Online Judge, SPOJ, Codechef, тех же TopCoder и Codeforces, Codingame и C Puzzles. На русском есть отличный ресурс informatics.mccme.ru.
Начинайте с задач, у которых самый большой процент решаемости – они самые простые. А потом понемногу повышайте уровень сложности.
Если возникнут трудности, изучите разборы задач – их часто публикуют на форумах. Анализ – это обязательный этап для любого спортивного программиста. После чемпионатов обязательно проводится дорешка – решение и разбор задач, с которыми возникли трудности на соревнованиях.
Посмотрите мастер-классы на YouTube – там часто пошагово показывают решения сложных кейсов. Еще стоит заглянуть в тред вопросов на Quora: там программисты делятся своими тревогами, а новички советуются с мастерами. Например, можно узнать, был ли Цукерберг хорошим кодером и как олимпиадное программирование помогает в карьере.
Подключайтесь к коммьюнити. Среда и живая коммуникация помогают продвигаться быстрее и выходить из тупика, в котором часто оказываются новички. Дома один на один с компьютером часто пропадают драйв и мотивация, но наверстать их можно на офлайн-встречах.
Регистрируйтесь на сборы, буткэмпы и интенсивы – сейчас большинство проходит в онлайн-режиме. Начинать можно еще в старших классах – например, на кампуспе МФТИ проходит лагерь Moscow Workshops Juniors. Занятия в них ведут преподаватели российских и зарубежных вузов.
Приготовьтесь к жесткому графику – например, студенческие сборы Moscow Workshops длятся 8 дней, причем тренировки проходят ежедневно. Мастер-классы организуют в Европе, Азии, на Ближнем Востоке, в Южной Америке – география широкая. Это не только отличный способ быстро прокачать навыки, но и возможность познакомиться с новыми людьми – в том числе с будущими конкурентами из разных стран. Многие, кстати, заводят друзей на сборах, а потом вместе открывают бизнес.
На сборах программисты учатся работать в команде – а это ценный навык на чемпионатах. Дома в одиночку его не прокачаешь, поэтому все чемпионы так или иначе участвуют в командной подготовке. К тому же большинство контестов предполагают коллективное участие – обычно в состав команды входит три человека.
Начинайте участвовать в контестах. Большинство крупных чемпионатов проводят онлайн-раунды, в которые попасть может любой желающий. В редких случаях в чемпионате можно участвовать без предварительного отборочного турнира – например, международный фестиваль RuCode, который запустили МФТИ, Яндекс и МегаФон при поддержке Фонда президентских грантов, открыт для программистов всех возрастов разного уровня. Чемпионат пройдет в это воскресенье и поучаствовать в нем сможет любой, кто прошел регистрацию на сайте. HashCode, Google Code Jam, TopCoder Open и VK Cup устанавливают минимальные требования для прохождения отборочных туров – можно попытать удачу и, если повезет, пройти в финал.
Студентам стоит попробовать свои силы на крупнейшем чемпионате ICPC, а школьникам – на Всероссийской олимпиаде школьников по информатике, а затем и международной IOI, Открытой олимпиаде школьников по программированию, ВКОШП и Технокубке.
Продумайте стратегию заранее и почитайте об особенностях начисления баллов. На школьных олимпиадах часто очки можно набрать даже за частичное решение – в этом случае важно набросать хотя бы какие-то варианты, чтобы получить частичный зачет. В приоритет ставьте самые простые задачи, потому что все задачи стоят одинаково. Но не забывайте переключаться – тренеры советуют не зацикливаться на одной задаче долгое время, потому что фокус «замыливается». Лучше вернуться к ней попозже, чтобы посмотреть свежим взглядом. На студенческих соревнованиях баллы начисляют только за полное решение: каждая задача либо решена полностью, либо не решена. Очки на Сodeforces вообще имеют принципиально другой смысл.
На забывайте про тайм-менеджмент – сколько раз олимпиадники страдали из-за того, что им не хватило буквально пары секунд на завершение работы. Попробуйте еще на стадии подготовки включать таймер и отслеживать, сколько времени уходит на задачи разного типа.
Учитывайте, что с первого раза практически никто не проходит в финалы международных соревнований по программированию, нужны чаще всего годы тренировок. Это нормально, поэтому не бойтесь поражения. В чемпионатах участвуют лучшие из лучших, а значит, вы конкурируете с самыми продвинутыми программистами, и проиграть им не так обидно.
Как готовиться к олимпиадам по информатике
Anton Morgunov
Во-первых, если вы мало-мальски умеете программировать, вам обязательно нужно идти на CodeForces если вы еще там не сидите. Это, в принципе, все что нужно.
А что же если вы только только начинаете? Вот подборка комментариев от опытных олимпиадников по информатике:
0) В школе на уроках информатики изучают: устройство компьютера, ПО, компьютерные сети, программирование, представление и измерение информации. Учатся работать с операционной системой и приложениями (Paint, Word, PowerPoint, Excel, Access и тп.). Но на олимпиадах по информатике дают задачи только на программирование.
1) В первую очередь надо выбрать язык программирования. В настоящее время на соревнованиях по программированию популярнее всего языки C++, Python и Java. Если вы только начинаете программировать, то знающие люди рекомендуют начать с Python 3, а после того как вы изучите основы и решите десятки задач, следует переходить на С++. Если у вас уже есть опыт на любом другом языке, то рекомендуется выбрать С++.
2) Прежде, чем приступить к изучению языка, вам следует установить специальные программы, с помощью которых вы сможете программировать. Для новичков которые выбрали Python → инструкция (скачается PDF файл). А если вы выбрали С++, то разберетесь сами → дистрибутивы.
3) В сети Интернет существует множество ресурсов, позволяющих изучать основы программирования самостоятельно. Перечислю несколько интернет ресурсов для подготовки к олимпиадам:
Напишу несколько советов к прохождению этого курса. К каждой теме дается видеоурок, конспект и около 11 задач. В каждом шаге присутствуют комментарии. При решении задачи не следует сразу читать комментарии, потому что там часто пишут подсказки. Читайте комментарии если вы застрянете при решении задачи на минут 40-50. После решения задачи вы получите доступ к решениям других людей. Будет полезно постараться понять альтернативные решения. Если в одной теме вы решили 2/3 задач, то переходите к следующей теме, чтобы побыстрее приступить к изучению новой теории. Но при этом возвращайтесь регулярно к нерешенным задачам предыдущих тем.
● При прохождении первых нескольких тем вышеперечисленных курсов будут встречаться задачи которые можно легко решить используя материал из последующих тем, чего делать не надо. Допустим если вы решаете задачу из темы условный оператор, то некоторые задачи решаются проще с циклами и массивами, но даже если вы уже знаете циклы и массивы следует решить задачу используя только изученные темы.
● Решая задачи, нужно иметь в виду, что не так важно количество решенных задач, как их качество. Возникает соблазн выбирать красивые и легкие задачи, пропуская те, что кажутся трудными и требующими кропотливого труда. Но чтобы отточить свои навыки, нужно отдавать предпочтение именно задачам второго типа.
5) Напоследок, в качестве мотивации, опыт олимпиадного программирования сильно поможет вам устроиться на работу программистом. В качестве меры измерения возьмем систему уровней с algoprog.ru. Условно, вы можете пройти собеседование алгоритмической секции в крупную компанию на 5 уровне, с отдельными темами более высоких уровней (со слов разработчика из Яндекс). Будучи студентом, чтобы пройти на стажировку в Google, Facebook и тд. необходимо уметь решать задачи примерно уровня заключительного этапа Республиканской олимпиады школьников (со слов программиста из Google).
P.S. Оставлю здесь ссылку для тех кто не хочет заниматься олимпиадным программированием, а просто хочет стать программистом → Что надо учить?
Хочешь получать рассылку от нас?
WRO-2019-дағы Қазақстан командасы: Робототехникада нақты нұсқаулық жоқ
Осы жылдың \(10\) қарашасында Қазақстан өзінің Халықаралық Робототехника Олимпиадасына (WRO) қатысу тарихында алғашқы рет жоғары-шығармашылық санатта жүлделі үшінші орынды иеленді. WRO-\(2019\) Венгриядағы Дьор қаласында өтті. Оған дейін Талдықорған қаласының командасы \(2014\) жылы орта-шығармашылық санатта үшінші орынға және \(2016\) жылы жоғары-шығармашылық санатта «Creativity Award» (креативтілік үшін) жүлдесіне ие болған. Талдықорған
[Математика ғажабы] Пифагор теоремасы
«Пән ғажабы неде» жобаның барлық мақалалары «Математика ғажабы» циклдың басқа мақалалары Визуалды дәлелдемелер Байес теоремасы Ойлаудың көркемдігі Сымдарды кесеміз Геометриямен жасырынбақ ойнау Шексіздік Математика тек формулалар ғана емес. Математика — бізді қоршайтын барлық нәрселер. Онда теоремалар мен аксиомаларды білу ғана емес, фундаментал қағидаларды түсініп, сезе білу де маңызды. Мұндай фундаментал білім
[Математика ғажабы] Геометриямен жасырынбақ ойнау
«Пән ғажабы неде» жобаның барлық мақалалары «Математика ғажабы» циклдың басқа мақалалары Визуалды дәлелдемелер Байес теоремасы Ойлаудың көркемдігі Сымдарды кесеміз Шексіздік Пифагор теоремасы Кез-келген геометриялық есепті аналитикалық жолмен шығаруға болады деп қабылданған. Шыныменде, егер сізде жеткілікті түрде тәжірибе болса онда сізге декарттық немесе бариентрлік координаттарды тұрғызу арқылы барлық геометрияны «сандар» арқылы
Если не указано иначе, все текстовые материалы блога ОФ Beyond Curriculum лицензированы под CC BY-NC-SA 4.0
Как развиваться в олимпиадном программировании? [закрыт]
Хотите улучшить этот вопрос? Переформулируйте вопрос так, чтобы на него можно было дать ответ, основанный на фактах и цитатах.
С недавнего времени меня очень зайтересовало олимпиадное программирование.
Я учусь на первом курсе.
Основы языка и несложные алгоритмы я уже выучил.
Но вот как мне дальше развиваться не знаю.
Что учить?
Где учить?
Где можно поучаствовать?
Какие-нибудь курсы?
Какие-нибудь форумы?
Буду очень признателен если кто-то поможет.
5 ответов 5
Выскажу своё мнение, так как много лет занимался олимпиадами и был участником чемпионата мира по программированию (19-е место). Сейчас я программист-математик в довольно узкой области, но владею этой областью как профессионала международного уровня. Не смог бы стать таким профессионалом если бы вовремя не соскочил с иглы олимпиад.
Седьмое. Как только поймёте, что дошли до точки насыщения и дальнейший рост в олимпиадах приводит только к развитию навыков скорости и соревнования, а классические основы всех алгоритмов вам уже известны, валите оттуда как можно скорее. Потому что с этого момента начинается ваша деградация как человека практического. Сразу переключайтесь на реальную работу, изучайте стандарты программирования, которые не смогли изучить в бытность олимпиадником и беритесь за реальные задачи. Если вы проигнорировали совет делать это параллельно, то придётся несколько лет переучиваться.
Всё, желаю удачи, и да прибудет с вами здравый смысл 🙂
Спорт для разработчиков: как устроено олимпиадное программирование
Ключевые соревнования, советы по подготовке и работе в команде
Спортивное программирование часто ассоциируется у людей с профессиональными командами, которые занимаются им со средней школы (или даже с начальной, как самый титулованный спортивный программист мира Геннадий Короткевич) и тратят на подготовку большую часть своего времени. Однако в соревнованиях участвует множество разработчиков с разным уровнем подготовки и с разной мотивацией: многие хотят научиться быстро писать рабочий код, углубить знания в области алгоритмов или добавить олимпиадный опыт в своё резюме. Академия Яндекса поговорила с участниками олимпиад и с Сергеем Чернышёвым — руководителем управления по работе с талантами Яндекса, финалистом ICPC 2002 года, о том, как начать заниматься спортивным программированием и зачем это делать.
Как устроены соревнования по программированию
Задача участников соревнований — решить как можно больше предложенных задач за ограниченное время. Соревнования бывают как индивидуальными, так и командными. Они состоят из нескольких этапов (например, отборочный тур, полуфинал и финал) и проводятся отдельно для школьников, студентов и выпускников вузов.
Одна из самых известных таких олимпиад — Международная студенческая олимпиада по программированию (ICPC). Она впервые состоялась в 1977 году в рамках конференции АСМ и с тех пор проводится каждый год. Последние восемь лет подряд выигрывают студенты российских университетов — МГУ, СПбГУ и ИТМО.
В ICPC могут участвовать студенты вузов или аспиранты первого года обучения не старше 24 лет. Это групповое соревнование, в котором участвуют команды из трёх человек.
Тур олимпиады проходит следующим образом: каждой команде выдаётся ноутбук и от восьми до двенадцати задач (их условия написаны на английском языке), которые нужно выполнить за пять часов. Участники пишут решения на языках программирования C, C++, Java, Python или Kotlin, компилируют и посылают их на тестирующий сервер.
При этом частичные решения не учитываются, а побеждает команда, правильно решившая наибольшее число задач.
Зачем участвовать в командных соревнованиях
«Олимпиадное программирование как большой спорт, и для того, чтобы занимать первые места на чемпионатах, нужно уделять подготовке почти всё своё время», — рассказывает Сергей Чернышёв, который сейчас занимается организацией олимпиад. У профессиональных команд есть свои тренеры (бывшие победители и призёры олимпиад и преподаватели университетов), которые отбирают перспективных студентов и готовят их к соревнованиям.
Многие участвуют в олимпиадах не ради победы. Например, студенты начинают заниматься спортивным программированием, потому что им нравится решать задачи или потому что на соревнования ездят их однокурсники. Однако из соревнований можно вынести пользу, даже если подходить к ним по-любительски. Чернышёв говорит о том, что участие в олимпиадах развивает как индивидуальные навыки и знания, так и умение работать в команде.
Команда во время перерыва. Фото: Moscow Programming Contest
«По сути, ICPC — это дополнительное дистанционное обучение, которое позволяет „прокачать“ себя. Благодаря олимпиадам студенты лучше узнают, что такое динамическое программирование, строковые и другие алгоритмы — эти темы не всегда глубоко преподаются в университетах», — объясняет Сергей.
Влад Бидзиля, участник ICPC и других олимпиад по программированию, считает, что у людей, которые хотят стать сильными разработчиками, есть несколько возможных направлений развития. Первое — набираться практического опыта, изучать новые фреймворки и технологии. А второе — развивать интеллект, занимаясь фундаментальными задачами (например, участвуя в олимпиадах). Опыт участия в соревнованиях помогает быстрее осваивать новые области. Этот опыт пригодился и в учёбе на ФКН НИУ ВШЭ и в ШАДе, и в работе в Яндексе: Влад говорит, что он везде замечал похожие паттерны.
Кроме того, олимпиады учат писать код без багов. «В контестах встречаются запутанные логические конструкции, которые редко возникают на практике», — поясняет Бидзиля. — В работе код обычно разделен: есть отдельные компоненты с понятными связями между собой. Поэтому если человек научился работать со сложной логикой, то в промышленной разработке он уже вряд ли допустит ошибки».
Как подготовиться и что делать во время соревнования
«Для того, чтобы начать участвовать в соревнованиях, ничего не нужно — только желание и умение программировать на каком-нибудь языке», — убеждает Сергей Чернышёв. А начать подготовку можно с решения задач на таких сайтах, как Codeforces, Topcoder и CodeChef.
Участник ICPC этого года Саша Минаков говорит: «Чтобы оказаться хотя бы в середине рейтинга участников, нужно знать популярные алгоритмические методы, типичные нелинейные структуры данных и графы». А профессиональные команды отличает знание специфичных алгоритмов, которые появляются в задачах олимпиад раз в несколько лет.
Ресурсы для подготовки:
Для участия в соревнованиях важно собрать грамотную команду и организовать её работу. Нередко в группах появляются «лидеры», которые сильнее всего мотивированы и сдают наибольшее количество задач за тур. «Однако только за счёт этого сложно достичь высоких результатов, потому что за несколько часов работы этот человек выдыхается и начинает совершать ошибки», — отмечает Чернышёв.
Хорошие команды — те, в которых все три участника постоянно сдают задачи и сменяют друг друга: пока один решает задачу, другой сидит за компьютером. Раньше бытовал стереотип, что в команде должны быть математик, программист и специалист по алгоритмам, но сейчас он неактуален, так как изменился формат соревнования и задачи стали более прикладными.
Команда за работой. Фото: Moscow Programming Contest
Во время тура нельзя терять концентрацию: на ICPC нужно решить до двенадцати задач за пять часов, и времени переделывать их нет. При этом на соревнованиях необязательно писать «чистый» код: он используется один раз, а жюри оценивает только итоговый результат. В случае с промышленным программированием, наоборот, важно сделать так, чтобы код было легко читать и поддерживать другим разработчикам.
Как изменялось спортивное программирование и что его ждёт
«За последние годы спортивное программирование стало более прикладным», — убеждён Сергей Чернышёв. Это связано с повышением культуры программирования: раньше в российских школах изучали Pascal, и задачи решали тоже на нём. Со временем у людей в олимпиадном сообществе появился опыт использования библиотек Java и C++ и различных структур данных. На их базе придумывали более сложные структуры для спортивного программирования, и за счёт этого прикладная и олимпиадная разработки сблизились. К тому же компьютеры стали работать быстрее, и ограничения по времени выполнения задач (на ICPC это обычно одна, две или три секунды) отошли на второй план. Ключевую роль в задачах стали играть аспекты реализации.
Чернышёв рассказывает, что олимпиадное движение развилось в России примерно на десятилетие раньше, чем хакатоны, которые набрали популярность после 2010 года. Организатор олимпиад говорит о том, что нынешним студентам будет полезно принять участие как в тех, так и в других соревнованиях. Хакатоны пригодятся тем, кто хочет развить продуктовое мышление или реализовать свою идею: они мало влияют на сам навык разработки. А спортивное программирование подойдёт как раз для того, чтобы углубить знания.
В будущем Сергею хотелось бы повысить престиж участия в олимпиадах по программированию. По его словам, сейчас для этого не хватает чёткой мотивации участвовать, нет, например, денежных призов или привилегий при приёме на работу. Чернышёв сравнивает студенческие олимпиады с Всероссийской олимпиадой школьников, где призёры и победители заключительного этапа гарантированно получают значимый приз — поступление в любой вуз России на соответствующее направление.
Мне кажется, что количество переходит в качество, поэтому если спортивное программирование будет популярным, то в нём автоматически будут очень сильные игроки.
Школьник об олимпиадном программировании
Об обучении
Меня всегда привлекало программирование (что это такое я понял аж в 4 классе). Я был очень рад, когда в седьмом классе начали преподавать Pascal и различные вычислительные алгоритмы. Именно тогда я написал первый «Hello World!», алгоритм Евклида; изучил условные операторы, циклы, массивы.
С восьмого класса учителя приглашали на факультативы по информатике, где мы изучали графы, алгоритмы сортировки массивов и многое другое.
Задачи
Требования
От олимпиадника требуется написать программу на одном из принимаемых языков (обычно этот набор состоит из Pascal (сам пишу, никогда проблем не было), Delphi, C++, Java, Visual Basic, в последнее время добавляют C#, Python). После этого исходный файл отправляется в систему-песочницу, где он компилируется и выполняется на группе тестов. За каждый тест участник олимпиады получает некоторый балл, которые потом складываются. После олимпиады результаты становятся видны всем. Чем больше суммарный балл — тем выше место.
Стоит отметить, что обычно проверяющими системами плохо обрабатывается управляемый код (Java, C#). Мой друг лично на региональном этапе получил на трех из четырех задач 0 баллов из-за ошибки во время выполнения (писал на C#), хотя проверялось все нормально. Что делать в таком случае не понял ни я, ни он; на апелляции жюри просто пожали плечами.
Риски
Wrong answer
Неверный ответ. Результат работы программы не совпадает с ответом жюри
Неверный формат вывода или алгоритмическая ошибка в программе
Time limit exceeded
Превышен указанный в задаче лимит времени. Программа выполняется дольше установленного времени
Неэффективное решение или алгоритмическая ошибка в программе
Presentation Error
Отсутствие выходного файла OUTPUT.TXT
Файл не создан, неверное имя файла или сбой программы до открытия выходного файла
Compilation error
Ошибка компиляции. В результате компиляции не создан исполняемый файл
Синтаксическая ошибка в программе или неверно указано расширение файла. Возможно, что при реализации на языке Java был использован класс, отличный от Main
Memory limit exceeded
Превышен указанный в задаче лимит памяти. Программа использует больше установленного размера памяти.
Неэффективный алгоритм, либо нерациональное использование памяти
Runtime error
Ошибка исполнения. Программа завершила работу с ненулевым кодом возврата. В этом случае результат работы не проверяется
Возможно, в программе произошло обращение к несуществующему элементу массива, деление на ноль и т.д. Возможно, программа на C++ не завершается оператором «return 0» или по иной причине вернула ненулевой код возврата
Олимпиады
Как проходит всероссийская олимпиада по информатике?
Я прошел всего 5 этапов: 8-9 классы в школе, 8-11 классы в школе, муниципальный этап, дистанционный тур региональной олимпиады, региональная олимпиада. Далее идет всероссийский тур, но я на него, к сожалению, не попал. Сейчас я расскажу про те задачи, которые мне очень понравились.
Этап среди старшеклассников
Во время тура среди 8-11 классов была задача «Полиномиальные хэш функции» условие которой было записано на двух страницах формата A5. В этом условии была приведена краткая информация о хэш функциях, их истории, была предложена одна такая функция. Задача заключалась в её вычислении для массива входных данных. Нас испугало очень страшное название, сложная терминология, запись суммы её значком (тот который выглядит как буква E) и в результате её мало кто вообще начал решать. Условие сейчас найти, к сожалению, не смогу.
Муниципальный этап
Решить задачу, если объект один достаточно просто. Но когда объектов больше — приходится применять достаточно сложный раздел программирования, «Динамическое программирование». Учитель, который вел у нас факультатив признался в том, что он плохо представляет как решить эту задачу (совместными усилиями мы вывели значение, которое нужно минимализировать, просто построив несколько графиков, даже не спрашивайте что это за значение — я его благополучно забыл).
В результате задачу на полный балл решил лишь один участник олимпиады.
В. Великий архиватор
Ввод/вывод: стандартный
Ограничения по времени: 1 секунда
На планете роботов очень любят автоматическую обработку текстов. Для этого роботы ввели специальную должность Великого Архиватора. В обязанности Великого Архиватора входит составление списка всех слов текста и замена слов на число, обозначающее номер этого слова в списке.
Напишите программу, выполняющую функции Великого Архиватора.
Формат входных данных:
В единственной строке входных данных приводится строка длиной не более миллиона символов, состоящая из строчных и заглавных букв английского алфавита и пробелов. Любые два соседних слова в тексте разделены ровно одним пробелом. Слова считаются одинаковыми, если они равны с точки зрения сравнения строк, причем строчные и заглавные буквы считаются различными.
Формат выходных данных:
В единственной строке выходных данных необходимо вывести последовательность номеров слов текста, причем слова в списке должны быть упорядочены в порядке их появления в тексте. Нумерация слов должна начинаться с единицы.
Примеры входных и выходных данных:
Входные данные
To be or not to be
Why do you cry Willie Why do you cry Why Willie Why Willie Why Willie Why
Выходные данные
1 2 3 4 5 2
1 2 3 4 5 1 2 3 4 1 5 1 5 1 5 1
Пояснение к примерам входных и выходных данных: текст во втором примере не содержит символов перевода строки и возврата каретки.
Достаточно простой алгоритм сжатия (не помню как называется). Мне было интересно реализовать. Я решил эту задачу созданием массива из слов, добавлял туда первое слово. Затем считывал каждое следующее слово, проверял, нет ли его в массиве. Если оно было — записывал в выходной поток номер слова, иначе — добавлял в массив, записывал номер.
В принципе, мое решение не получило полный балл.
Полный текст заданий можно найти здесь.
На дистанционном туре я занял 1 место среди девятиклассников.
Региональный этап
На этапе региональном было не так весело, тура было два. Я боялся подвести школу и не пройти на следующий этап, плохо показать нашу школу. Поэтому и задания воспринимались не так весело и приятно. В общем: ничего не запомнил оттуда, но получил заветный диплом. Да и условия мне не удалось найти.
На второй день к нам приехали представители местной компании «Прогноз», поиграли с нами в «Что? Где? Когда?», провели викторину. Победителям раздали призы.
Подготовка
Как же я готовился?
Ответ достаточно прост: у меня хорошие учителя. Мне это было интересно и я получал от всего происходящего удовольствие. Я усердно готовился и добился того, чего хотел.
Что же дальше?
Говоря это, я подразумеваю вопрос о том, насколько олимпиадники приспособлены к работе в реальных условиях.
Хоть я и не работал еще в IT индустрии, но я считаю: олимпиадники никак не приспособлены к реальной работе. На таких олимпиадах требуется уметь быстро изобрести «велосипед», знать хорошо алгоритмы. Я с другом занимаюсь написанием небольших игр и понимаю, что гораздо важнее уметь выбрать правильную технологию для твоих целей, уметь найти готовое решение чтобы ускорить разработку, «Велосипеды не нужны». Поправьте меня, если это не так.
Если кого интересует то, чего я в жизни хочу: на самом деле я не очень-то люблю IT и информатику, мечта моя — выучиться на физика-теоретика и заниматься исследованиями. А так как в РФ с этим проблемы я планирую уехать в Канаду или США.
Приму любые пожелания в ЛС или в комментариях. Надеюсь, данная статья не получилась длинной. Надеюсь она была для Вас интересна. Надеюсь Вас не раздражала моя неграмотность, уж очень я плохо знаю пунктуацию.