Здравствуйте! Я хотел бы затронуть тему о развитии сильных спортивных программистов. Многих интересует, как люди попадают на финал ACM ICPC или, например, получают 2200+ на Codeforces/Topcoder. В связи с этим, прошу всех, кому есть что сказать по данной теме, а в особенности вышеуказанную категорию людей, ответить на вопросы:
- Сколько времени вы занимаетесь СП?
- Что Вам дало наибольший толчок и когда?
- Какие ресурсы-архивы сейчас решаете (и как бы могли их охарактеризовать: acm.sgu.ru, acm.timus.ru, codeforces, topcoder и т.п.)?
- Какой язык программирования и среду сейчас используете (по возможности с кратким (или полным) комментарием)?
- Сколько часов в неделю вы тратите на СП (в том числе постоянны ли ваши тренировки, или они сезонные и направлены для успешного выступления на определенном соревновании)?
- Какой способ подготовки к серьёзным личным соревнованиям вы предпочитаете?
- Что Вас больше всего мотивировало во время вашего развития и мотивирует по сей день?
- Определяющие факторы для достижения успеха в СП?
9*.Дополнительные комментарии по этой теме.
На codeforces.ru есть много отдельных постов, в какой-то мере отражающих тематику, но мне хотелось бы все собрать в одном месте.
Единственная смежная содержательная запись в блоге, которую я знаю.
Просьба особо не флудить.
Примечание: Используется сокращение "СП" — "спортивное программирование".
Тут тема подготовки олимпиадников раскрыта гораздо лучше, чем по указанной в посте ссылке.
И вообще, красные, вы где? Почему никто не отвечает в теме? Интересно же почитать!
Подобная тема обсуждалась на топкодере.
Я начну.
1) Год и 2 месяца
2) Бессоница и депрессии =)
3) Решаю acmp.ru из желания прорешать весь =)
4) С++/Geany — минималистичненько
5) Часов 5-10 — на решение задач и контестов, не регулярно, сейчас вообще сессия на носу.
6) Не готовлюсь — мой уровень не позволяет мне рассчитывать на победу, просто решаю контесты.
7) Мне это нравится :) UPD: и ещё хочу выиграть футболочку =)
8) Способности к придумыванию алгоритмов + опыт
9) За год ничего не умеющий математик с уровня зелёного может раскачаться до желтого уровня без особых усилий. На топкодере несколько сложнее — почти весь этот год был синим, только сейчас удалось выбраться в желтые.
Теперь более подробно о некоторых аспектах.
Тимус в качестве архива подходит отлично. Берём задачу, думаем, решаем. Крайне полезен в начале олимпиадной "карьеры", когда несложные идеи приводят к успеху. Архив Codeforces — если хочешь научиться писать код. Не советую во многом из-за соблазна подсмотреть тест спустя часы мучений. Учиться находить косяки самостоятельно — бесконечно полезный скилл на соревнованиях. Тренировки на Topcoder — если хочешь научиться думать. Рекомендую решать в топкодерском стиле: убиваемся 75 минут, затем тестим, отлаживаем решения, учимся на ошибках, читаем чужой код, разбираемся. Обычно десятка таких тренировок хватало, чтобы следующий SRM показался немного проще предыдущих.
Мнение касательно отладчика: лучше не надо. Дебаг-аутпут учит задавать программе правильные вопросы и искать косяки в тех местах, где они действительно есть. Уверен, что именно отказ от отладчика накинул мне немного мозгов и сотню-другую баллов на топкодере.
О тренировках: можно рассматривать долгосрочные этапы тренировок, можно краткосрочные. В долгосрочных основная цель — добиться максимального роста. В краткосрочные важно заметить, что изменение уровня скилла идёт по синусоиде: спад-подъём, спад-подъём. Будет здорово, если ты поймёшь, как уменьшить и сократить этап спада и увеличить интенсивность и длительность этапа подъёма. Для этого нужно грамотно чередовать нагрузки и отдых. Каждый человек в этом плане индивидуален; мне, например, больше всего подходит такой режим: месяц интенсивных тренировок, месяц лёгких тренировок, месяц отдыха и занятия смежными областями. Подъём ощущается как раз после отдыха.
Всё написанное выше — исключительно моё мнение, поэтому не надо спорить, особенно на темы отладчик/не отладчик, студия/не студия, c++/не c++. С удовольствием почитаю мнения по-настоящему сильных олимпиадников.
Около пяти лет — у тебя, кажется, пять лет назад был диплом на всеросе :)
ого, это я такой старый уже? ну да, выходит у меня лет шесть более-менее серьёзных тренировок и лет девять — просто знакомства с программированием на уровне условий и циклов :(
Учите математику, без нее никак:)
Я ветеран ACM ICPC 2010 года, с тех пор осмысленно не тренируюсь, поэтому отвечу на вопрос, как тренировалась раньше.
9*. Не стоит пытаться повторить чей-то путь к успеху, лучше найти свой.
А можно поподробнее?
После летних петрозаводских сборов мы приняли решение перераспределить роли в команде (Дима пишет код, Стас за ним следит, я думаю над задачами). После этого у нас сразу произошел скачок в результатах и захотелось активно тренироваться дальше. Прошли упаднические настроения, вызванные сливом полуфинала 2007 года.
На самом деле Наташ это очень клево выглядело. Я когда был на первом курсе как раз постоянно наблюдал за вами: вы решали прямо как конвеер. Дима и Стас (пишут, дебужат), а ты думаешь.
У вас было четкое разделение — два хардкорных кодера и математик?
Не совсем. У нас скорее была давно известная в теории СП "столичная система" :) С тем небольшим отличием, что Стас не только придумывал тесты, но еще валидировал идею и следил за написанием кода. Крутым кодером был (да и сейчас является) только Дима.
Можно узнать, откуда такая точная дата? :)
Хорошая память может...я вот помню точный день, когда я начал заниматься СП....15 января 2009 :)
Может начало занятий по проге в каком-нить кружке при СГУ?
Да, это действительно начало занятий на кружке.
Опрос, вообще-то, социологический.
Приношу свои извинения. Спасибо!
You are welcome.
Ссылка на "Единственную содержательную запись в блоге" не работает...
Исправлено,спасибо!
А по теме:
Для тех кто сейчас в таком же положении как я, могу посоветовать книгy, которая по-моему мнению, позволит набраться нужного жаргона и основных алгоритмических фишек Programming-Challenges — Steven Skiena. Сам читаю ее сейчас, большой плюс книги в том, что после многих тем, автор приводит пример real-world проблемы, которая решалась именно при помощи алгоритма/техники, разобранной только что.
P.S хотелось бы видеть больше ответов опытных людей, и их рекомендации =)
10ый вижак весьма годен, вроде. Под линем запустить его — проблема, но всегда можно поставить VM.
Пользуясь случаем — если есть желающие написать такой плагин для плюсов, можно собраться и написать.
Меня после Idea очень бесит, что во всех C++-ных IDE какое-то идиотское нагромождение эвристик вместо честного парсинга программы (10ый вижак — не исключение). Ну и понятно, фич там гораздо меньше (о чём можно говорить, когда даже refactor->rename нормально работающего нет :) ).
Думаю, грамматика плюсов даже теоретически не позволяет честно парсить программу и, например, переименовывать переменные (даже просто конкатенация имен с использованием ## делает однозначное переименование невозможным). Полнота по Тьюрингу шаблонов, видимо, не позволяет делать статический семантический разбор иначе как нагромождением эвристик.
Не подскажите, где можно почитать про "конкатенация имен с использованием ##"? Или вкратце что это такое.
вторая ссылка в гугле по
preprocessor ##http://www.cplusplus.com/doc/tutorial/preprocessor/Ну хотелось бы, чтобы это работало хотя бы для обычного кода (даже пусть без директив препоцессора скажем, кроме #include'ов)
Все равно, как я понимаю, от них чаще стараются отходить (Правда, многие СП как раз юзают сокращения типа forn(), но это уже другой вопрос.)
Для обычного кода неплохо работает VisualAssistX. Также автокомплит и средства рефакторинга мне нравятся в QtCreatorе. Но до инструментов jetbrains им все равно далеко.
Правильно ли я понимаю, что это плагин который работает только для платных версий(или кроме Express есть бесплатные?) VS, которые еще и работают только под платной ОС? Печально, если так.
На самом деле, в NetBeans, который я юзаю, средства рефакторинга в каком-то виде есть (тот же rename variable), даже работает относительно нормально, хотя иногода зацепляет лишнее, но его там куда меньше. Например, кнопочка generate constructor и выбор списка аргументов — весьма крутая вещь, не реализована
Да, на express он не встанет. Можно попробовать получить студию professional через microsoft dreamspark.
После idea будет бесить любая среда разработки :) А вообще выше сказано верно — синтаксис плюсов слишком сложен для написания полноценных инструментов рефакторинга, как в других языках.
Я понимаю, что мнение стрёмного синего вряд ли интересно, но я брался за написание плагина для VS 2010.
В принципе, пишется несложно, но нужно разобраться в том, как это делается. Теоретически, можно писать коллективно (SVN, Git).
хотел бы спросить: а почему именно плагин? Почему бы не cli программулину, котарая парсит и инлайнит код? Кажется имея такую программу легче сделать плагин для любого блокнота(тем более во многих уже есть плагин и средства запуска сторонних инструментов).
Даешь C/C++ плагин для Idea!
Тока он не работает, а когда работал был кривой, и ни фига не умный(как другие проекты JetBrains)
(а также возможность кидать фразы типа "понабрали по ЕГЭ")). Сейчас только рейтинги, футболки и удовольствиеНе нужно искать чего-то в контестах, кроме самих контестов. Это не самый легкий способ получения чего бы то ни было полезного. А вот бесценные приятные часы они приносят, это правда.
2010-ая студия подчёркивает ошибки красной волнистой линией, так, как Word например.
UPD. это я к тому, что в 2010-ой она подчеркнёт необъявленную переменную.
Ты затронул такую тонкую тему: "рассказывание своих планов". Лично мне рассказывание планов сильно помогло. Я попал в очень хорошую конкурентную среду, и сильно поднялся по сравнению с тем, что было в начале (съездил на РОИ, правда, там всё слил).
Проблема в том, что сейчас почти все кодеры делают практически одно и то же: решают одни и те же контесты, одни и те же проблемсеты, читают одни и те же книги, пишут одинаковой стратегией. Поэтому нужно оставить каждому немного пространства, чтобы думать самому, экспериментировать и пр.
Насчёт стратегии не согласен. Что в личных соревнованиях, что в командных — она сильно отличается у разных людей.
Особенно сильно это заметно в команде. Наша команда (школьники) отработала стратегию на отлично, это нам сильно помогло. Мы потратили на это очень много времени и сил, и, к сожалению, впустую.
В этом году я хочу собрать новую команду в ВУЗ'е, придётся начинать всё заново.
Стратегия — это слишком индивидуальная вещь, у всех похожая, но такая разная.
Почему ты думаешь, что отработал стратегию на отлично, если результата не получилось?
Результата не получилось не потому что стратегия плохая, а потому что мы тупые. Это две большие разницы.
Во время контеста мы очень быстро нашли несколько халяв, но внезапно выяснилось, что система тестирования (Барнаул forever) не работает. Её включили на 15ой минуте, тогда мы сдали две задачи чисто. Потом ещё одну.
Мы очень долго не видели Питерский монитор, что опять же сыграло злую шутку (не знали, за что стоит браться). В нашей стратегии всё-таки была зависимость от монитора и на тренировках она работала.
И проблем со стратегией во время контеста не было, с этой точки зрения всё прошло очень хорошо: были распределены роли, но не хватило мозгов.
Да.. нечто подобное я уже некоторое время вынашиваю. Что если начать взращивать программиста совершенно отвлечённо от текущих контестов, не выставлять его лишь для того, чтобы посмотреть какого он уже уровня или фофан. Тогда, возможно, развиваясь в своей среде он не сможет понять, насколько он крут в сравнении с остальными, а если при этом постоянно делать уклон на то, что он ещё не достаточно крут, то это может стать причиной его постоянной мотивации расти вне зависимости от текущего уровня относительно других. Если же он увидит что и так уже крут, есть риск, что расслабится. То есть в тихую мне кажется может быть проще стать туристом, чем постоянно соревнуясь публично... надо лишь правильно подбадривать мыслями о недостаточной крутости. Возникает вопрос о том, что конкуренция — хорошее средство роста и мотивации.. тогда можно пойти дальше и улучшить этот метод: пусть будет группа людей, которая соревнуется только сама с собой, но не соревнуется в паблике, тогда все представители смогут расти вне зависимости от всего общества и подбадриваемые конкуренцией. Минус: нужно долго ждать, чтобы имел смысл выставлять по такой методике кодеров на соревнования.
Ну, например, я, если бы не учасвствовал в соревнованиях, быстро бы забил ибо было бы совctv не интересно. Так что тут все же все индивидуально.
Да, возможно, это ещё один минус. Тут, наверное, могут помочь только внутригрупповые плюшки... едва ли многим хватит "вы станете крутыми кодерами через 2-3 года, если будете меня слушать".
Задротство и талант это, безусловно, очень нужная и важная в СП вещь, но удача не всегда напрямую зависит от них. Иногда так называемая "удача" может в какашку опустить долгие и упорные тренировки и талант, а может и наоборот сделать так, что ты выступишь просто на невозможном для себя уровне. Так что это всё-таки отдельный пункт (хотя, конечно, без первых двух она вообще не состоятельна).
Пишу как было в 2008, когда это было релевантно.
5 лет
Не было толчка
Только внутренний архив в формате 5-ти часовых контестов.
Visual Studio для полуфинала (отладчик нереально крут и быстр), после полуфинала пересел на Eclipse для финала. Язык -- С++.
5 часов четыре-пять раз в неделю (ровно один контест в день)
5-ти часовые личные контесты. Мы делали и командные (тоже пятичасовые), я не помню как часто. Вероятно, ближе к выездам.
Мотивировала медалька и двери, которые она открывает.
Очень много тренировок.
В общем мое мнение всегда было такое: надо писать только в формате АСМ 5-ти часовых контестов без дорешек (потому что в день Х надо будет писать АСМ 5-ти часовой контест, и дорешать будет нельзя). Дорешки -- это спорный вопрос, я согласен. Фанатичную прорешку архивов считал и считаю неэффективной. В подтверждение тому -- большинство людей в топе Тимуса не круты. Мой тренер учил меня, что важно не уходить с пятичасовой тренировки раньше (потому что надо тренировать выдержку -- если тренироваться по 2 часа в день, то и на выезде перегоришь через два часа). Мне приходилось писать по 4-5 дней в неделю чтобы поднять нужный уровень, но я в курсе что люди становились чемпионами тренируясь только по разу в неделю.
Где взять овер 9000 задач = 9 задач в контесте × 4 контеста в неделю × 50 недель в году × 5 лет?
Тоже мне проблема, задачи найти:)
http://neerc.ifmo.ru/school/io/index.html — вот тут порядка 1000 задач.
http://neerc.ifmo.ru/school/archive/index.html — вот тут еще... Точно больше 1500.
http://informatics.mccme.ru/moodle/ — тут тоже, даже если отбросить те, которые попадались выше, и те, которые "а+б", то больше 1000 явно наберется.
Дальше склеить вместе http://acm.tju.edu.cn/toj/, http://poj.org/, http://acm.zju.edu.cn/onlinejudge/, http://acm.hdu.edu.cn/ и остальных "китайцев" — еще несколько тысяч задач.
Дальше, есть еще http://uva.onlinejudge.org/ , всеми забытая, на которой можно накопать еще 4значное число задач, которые не проскакивали на названных мною раньше сайтах.
http://www.spoj.pl — тут тоже очень-очень много авторских задач, которые нигде больше не попадались. Тоже, думаю, больше 1000. Хотя и не гарантирую.
Большая часть этих материалов была доступна и 4-5 лет назад.
Так что найти задачи — не проблема :D Даже если их реально надо было бы в таких количествах, как Вы написали.
Ну разве что проблема с повторами, да и то в целом "лечится" просто.
внутренний архив же...
А, ок) точно)
По крайней мере я ответил на другой вопрос — "Где найти задачи для тренировок"...
Ну да, по поводу внутреннего архива — самому интересно стало. Понятно, что оценка в 9000 задач завышена в несколько раз, но все равно получается немаленький сборник.
Про 9000 я, понятно, пошутил :)
Можно вот так: 1500 Петрозаводск + 1500 school.ifmo + разные официальные контесты и наберётся почти сколько надо
Хотя, наверное, есть способы проще
Уже этот вопрос всплывал. Архивы Петрозаводска выдаются после сборов участникам, их можно где-то находить. Школьные олимпиады -- это очень крутой источник задач (они очень сложные, и часто нестандартные), тоже все доступны. Польские полуфиналы -- неплохой источник задач, тоже доступны. Американские полуфиналы и другие американские задачи -- это отличный источник задач, в которых нет ограничений (такое на финалах, по крайней мере раньше, было обычным делом, и хорошо иметь такой опыт тоже). Это уже будет хорошее количество задач.
2 контеста в неделю на contest.yandex.ru (да ещё и с разборами задач) + opencup'ы (0.5 в неделю) + тренировки на neerc.ifmo.ru/trains + командные контесты на всяких uva.onlinejudge.org. Должно хватить :)
не первый раз читаю мнение, что хорошо решать 5 часов без дорешивания. Ок, раз люди добиваются успеха следуя этому правилу — значит работает. Но не понятно почему. :) Вот решаешь контест. X задач решил, Y нет. В следующий раз будет нечто похожее из Y — опять не решишь? Откуда берется прогресс?
На самом деле выносливость -- весьма важный фактор во время контеста. Когда я писал по 5 часовому контесту 2 раза в неделю -- концовка контеста становилась всё более и более продуктивной.
После года перерыва от контеста оставалось 2-3 часа полезного времени и пришлось заново набирать форму...
Относительно скиллов решения задач: если у тебя на 5 часов серьёзный контест где 1-2 халявы, то это не сильно будет отличаться от дорешивания. А дорешивание, кажется, привывает скилл решать задачу(пусть и сложную) в фоновом режиме за 10 часов...
Дорешка -- это действительно спорный вопрос.
Дорешка наверное полезна, чтобы научиться решать все типы задач.
Но мне кажется, что я набрал уровень, которого достаточно, чтобы решать любые задачи, достаточно быстро -- максимум год. Но уровень, которого достаточно чтобы решать любые типы задач -- это далеко не тот уровень, который нужен, чтобы получить медальку. Дальше надо развивать умение быстро понять какой алгоритм прячется за задачей (это на дорешке никак не развивается), научиться быстро и без ошибок их реализовывать (дорешка ничего не привносит в этом плане), научиться правильно рассчитывать свои силы на контесте (не залипать на три часа на задаче) -- тоже дорешка никак не поможет.
Проблема, которую я вижу в дорешке, заключается в том, что есть опасность привыкнуть к тому, что задачу можно дорешать в дополнительное время. Надо привыкать решать за пять часов.
Сам я конечно дорешивал все равно -- потому что иногда просто не получается взять после контеста и оставить задачу не решенной :о)
Позвольте полюбопытствовать, со скольки задач на среднестатистическом петрозаводском контесте вы начинали?
И через какое время после интенсивного годичного курса подготовки это было?
P.S. промазал; должно быть комментом сюда
" научиться быстро и без ошибок их реализовывать (дорешка ничего не привносит в этом плане)" Лично мне кажется, что если дорешка что-то и дает, то именно умение реализовывать.
Ключевые слова быстро и без ошибок. На дорешке тебя никто не гонит, ты можешь спокойно сходить попить чайку, думая над деталями реализации, написать код, часа два подебужить, в итоге задача сдается, но далеко не в то время когда должна.
Дорешка руку набивает. У меня, конечно, относительно скудный опыт, но идеи быстрой и простой реализации различных методов гораздо чаще приходят в голову во время спокойной дорешки, а не когда на контесте пишешь самое тупое из того, что работает.
Я думаю , что если тренироваться способом 5-ти часовых контестов, это развивает сразу с нескольких сторон. Во первых на реальном контесте тебе уже будет легче, у тебя уже будет свой подсознательный, отработанный метод решения задач за 5 часов, ты не будешь теряться. Во вторых ограничение во времени помогает тебе сконцентрироваться и развить свою способность сконцентрироваться на задачах, ты не будешь отвлекаться , а будешь решать. В третьих у тебя отработается способность просидеть 5 часов на контесте, просидеть 5 часов решая задачи не очень легко , но так как у тебя уже будет большой опыт в этом , это уже для тебя не будет проблемой. В четвёртых ты научишься быстро решать задачи на время.
Вообще я думаю , что если во время решения даже 1 задачи поставить на неё ограничение по времени, то от этого будет больше пользы, чем от решения с отвлечениями (например разговоры , тв, музыка и и.т.п). Потому что программист будет знать, что у него время ограничено и соответственно осознавая это он не будет отвлекаться, он будет решать , временя-то идёт. Но в этом методе есть одна проблема, то что программист просто может забить на это ограничение, с мыслями о том что это ничего не решает , никакого приза за неё не будет, никакой отбор решив её сейчас и с этим ограничением он не пройдёт. В таком случае решающему поможет только его сильная сила воли и осознавание того что это тоже важно.
А прогресс от метода тренировок 5-ти часовыми контестами идёт думаю так: Сначала программист успевает решить только 2 лёгкие задачи, а на третью времени не хватает. Потом уже со временем он успевает решить и 3. Он тренируется и уже 3 у него идут легко, но над 4 он успевает только подумать. И уже с тренировками у него идёт и 4. и так далее. Есть конечно множество других причин прогресса , но думаю эта основная.
"Решение с отвлечениями" выглядит неправдоподобно.
Обычно, если уж взялся решать, то хочешь или поскорее закончить 1/3/5/10/20 задач или решить как можно больше за 1/3/5/10/20 часов. Если есть желание отвлечься, то следует сначала сделать все побочные дела, а потом уже садиться за решение задач.
То же самое с "установкой ограничений на задачу".
Про 2 задачи на контест тоже выглядит смешно(хотя и для многих правда). Для раскачки на начальных уровнях нет ничего полезнее, чем решать тимус(или другой OJ).
Про “Решение с отвлечениями” , у всех по разному , есть и люди , которые во время задачи одновременно слушают музыку , бывает смотрят телевизор , отвлечений то всяких не мало в наше время, лень мешает некоторым, соблазн компютерных игр. Насчёт того, что если появилось желание отвлечься, следует сначала сделать все побочные дела, а потом уже садиться за решение задач согласен.
Про "установка ограничений на задачу" лично я думаю что такой вид решения задачи имеет эффет по-больше, чем другой вид, в котором нет ограничений.
ИМХО, без минимальной дисциплины никакого развития в СП. Получается СП как хобби.
невозможно провести за одной задачей больше Х времени?
Совсем не понимаю, чем отличается процесс решения с "установкой". Только тем, что после Х времени забиваешь на задачу
Хорошо, если на задачу тратиться не слишком мало времени (т.е. нет "чтения решения без процесса самостоятельного поиска решения"), но и не слишком много (т.е. нету неоптимальной траты времени на слишком сложные задачи.
Отклонение в обе стороны негативно влияет на результат. Если найти золотую середину и установить такое ограничение, то результаты должны улучшаться значительно быстрее.
Читаешь задачу , в глове сразу оцениваешь её и определяешь примерное время Х (ко мне в голову оно обычно само приходит после прочтения задачи) , за которое ты думаешь , что сможешь решить её. И потом стараешься решить эту задачу за время Х. Если не успел решить за Х, можешь забить на неё , можешь прочитать решение, а можешь добавить ещё несколько минут к Х-су.
Я читал где-то , если у человека есть кое какое задание, которое ему надо решить и если поставить на него ограничение по веремени, например Х дней/часов/минут, то он выполнит максимум из всего что он может за эти Х дней/часов/минут. Я не знаю доказано это или нет.
Можно ещё всё-таки сдать задачу, а потом посмотреть, как время, потраченное на неё, соотносится с X. Полезно собрать такую статистику, а потом понимать, что первая мысль "я сдам эту задачу за X минут" на самом деле обычно означает, скажем, "за 2X минут", и соответствующим образом корректировать стратегию на соревнованиях.