Где искать теорию для спортивного программирования?
Хотел бы узнать где можно подыскать теорию. Практику я знаю где найти но вот теорию не знаю. Я видел различные лекции от ИТМО, Иннополиса, и т.п. Но мне не ясно в каком порядке структурировать эти лекции. Так же хотел бы какие ни будь книги по алгоритмам.
Василий Банников, Я владею синтаксисом языков С++ и Python на неплохом уровне. Сейчас для олимпиад решил заняться спорт программированием. Так что пока знанию в этой области не имею.
Дмитрий Забелин, ну тогда можно начать с базы - "алгоритмы. Проектирование и анализ" - там и про разные структуры данных, и про разные типичные задачи и подходы для решения. Читать от корки до корки не обязательно.
Если страшно брать такую толстенную книгу, то тогда "Алгоритмы. Вводный курс".
(Имхо лучше эти две, чем что-то распиаренное типа "грокаем")
По практике - есть литкод, там также по каждой отдельной теме есть задачки (только читай условия внимательно, тк часто на хард задачках там есть требования типа "уложиться в такой-то big-O" или "не использовать дополнительную память".
+ Я бы ещё что-нибудь кроме C++ и Python потрогал, тк это буквально две крайности.
C++ не очень хорошо на олимпиадах идёт из-за своего страшного синтаксиса и бедноватой стандартной библиотеки.
C# например (он отдельно приколен из-за того что всякие ленивые вычисления в нём легко и лаконично делаются)
+ Ещё стоит почитать про то как работают те или иные вещи в твоём основном языке. Те же list comprehension во что превращаются в рантайме или как работают генераторы, на сколько и то и то тяжёлое и где лучше использовать их, а где циклы.
+ Математику ещё надо прокачать, тк многие вещи не очень очевидны без неё и многие олимпиадные задачки решаются чисто через какой-нибудь математический трюк.
Василий Банников, Спасибо за ответ. А что дальше изучать после того как изучил основы которые о которых вы написали? (Ну примерно хотя бы обрисовать путь)
+ Ещё стоит почитать про то как работают те или иные вещи в твоём основном языке. Те же list comprehension во что превращаются в рантайме или как работают генераторы, на сколько и то и то тяжёлое и где лучше использовать их, а где циклы.
+ Математику ещё надо прокачать, тк многие вещи не очень очевидны без неё и многие олимпиадные задачки решаются чисто через какой-нибудь математический трюк.
По практике - есть литкод, там также по каждой отдельной теме есть задачки (только читай условия внимательно, тк часто на хард задачках там есть требования типа "уложиться в такой-то big-O" или "не использовать дополнительную память".
C++ не очень хорошо на олимпиадах идёт из-за своего страшного синтаксиса и бедноватой стандартной библиотеки.
Наоборот, С++ один из самых популярных языков на соревнованиях. потому что быстр. И алгоритмы на нем писать нормально. Ничего для них синтаксис не беден. А стандартная библиотека во многих языках примерно одинаково помогает в задачах. Самые стандартные структуры данных там есть почти везде, но часто надо что-то более заковыристое и все равно писать руками приходится всякие деревья и прочие извращения. Единственное, чего в C++ действительно нет - это длинная арифметика. Поэтому я в свое время на соревнованиях писал на С++ и редко на java, когда BigInt был нужен.
Wataru, охотно верю. А реально эта производительность помогает? Если аналогичный алгоритм на какойнибудь жаве или шарпе сделать, то там по времени/памяти не уложится?
Василий Банников, В редких случаях - не уложится. Т.е. конечно, есть идеальное решение, которое пройдет на любом языке, но на С++ можно немного меньше запариваться микрооптимизациями (битовое сжатие, развороты циклов и вот это вот все).
Суть подготовки в том что ты берешь олимпиадные задачи и каждый день (в СБ и ВС) с утра начинаешь
решать. Как спорстмен. У тебя - режим жизни. И в будни и в выходные.
Сначала долго. Потом быстрее и быстрее. Решение этих задач это навык. И он приобретается.
Там - обычное программирование и оно использует достаточно простые алгоритмы и структуры
данных. Но оно содержит в условиях
- ограничения (например все числа от 0 до 99999)
- время работы алгоримта не должно превышать допустим 30 секунд.
- обычно условие содержит пример в виде
Input:
Output:
И в условии всегда есть некая подсказка чтоб упростить решение. Очень часто может
применяться динамическое программирование и рекурсия. Но в этом нет никакой
олимпиадной магии. Это и есть ОБЫЧНОЕ программирование.
Просто есть лимит времени.
И код - обычно говнокод. Нет тестов. Нет рефакторинга. Нет генериков. Ты пишешь
бегом-бегом как на хакатоне. Все пишешь сплошной main функецией. Как бог даст.
Простой
