Где искать теорию для спортивного программирования?

Question

[Дмитрий Забелин]

Хотел бы узнать где можно подыскать теорию. Практику я знаю где найти но вот теорию не знаю. Я видел различные лекции от ИТМО, Иннополиса, и т.п. Но мне не ясно в каком порядке структурировать эти лекции. Так же хотел бы какие ни будь книги по алгоритмам.

Comments

[Василий Банников]

Что уже успел прочитать?

[Дмитрий Забелин]

Василий Банников, Я владею синтаксисом языков С++ и Python на неплохом уровне. Сейчас для олимпиад решил заняться спорт программированием. Так что пока знанию в этой области не имею.

[Василий Банников]

Дмитрий Забелин, ну тогда можно начать с базы - "алгоритмы. Проектирование и анализ" - там и про разные структуры данных, и про разные типичные задачи и подходы для решения. Читать от корки до корки не обязательно.
Если страшно брать такую толстенную книгу, то тогда "Алгоритмы. Вводный курс".
(Имхо лучше эти две, чем что-то распиаренное типа "грокаем")

По практике - есть литкод, там также по каждой отдельной теме есть задачки (только читай условия внимательно, тк часто на хард задачках там есть требования типа "уложиться в такой-то big-O" или "не использовать дополнительную память".

+ Я бы ещё что-нибудь кроме C++ и Python потрогал, тк это буквально две крайности.
C++ не очень хорошо на олимпиадах идёт из-за своего страшного синтаксиса и бедноватой стандартной библиотеки.
C# например (он отдельно приколен из-за того что всякие ленивые вычисления в нём легко и лаконично делаются)

+ Ещё стоит почитать про то как работают те или иные вещи в твоём основном языке. Те же list comprehension во что превращаются в рантайме или как работают генераторы, на сколько и то и то тяжёлое и где лучше использовать их, а где циклы.

+ Математику ещё надо прокачать, тк многие вещи не очень очевидны без неё и многие олимпиадные задачки решаются чисто через какой-нибудь математический трюк.

[Дмитрий Забелин]

Василий Банников, Спасибо за ответ. А что дальше изучать после того как изучил основы которые о которых вы написали? (Ну примерно хотя бы обрисовать путь)

[Василий Банников]

Дмитрий Забелин,

+ Ещё стоит почитать про то как работают те или иные вещи в твоём основном языке. Те же list comprehension во что превращаются в рантайме или как работают генераторы, на сколько и то и то тяжёлое и где лучше использовать их, а где циклы.

+ Математику ещё надо прокачать, тк многие вещи не очень очевидны без неё и многие олимпиадные задачки решаются чисто через какой-нибудь математический трюк.

По практике - есть литкод, там также по каждой отдельной теме есть задачки (только читай условия внимательно, тк часто на хард задачках там есть требования типа "уложиться в такой-то big-O" или "не использовать дополнительную память".

Да и в принципе там уже сам поймёшь, что нужно)

[Wataru]

Василий Банников,

C++ не очень хорошо на олимпиадах идёт из-за своего страшного синтаксиса и бедноватой стандартной библиотеки.

Наоборот, С++ один из самых популярных языков на соревнованиях. потому что быстр. И алгоритмы на нем писать нормально. Ничего для них синтаксис не беден. А стандартная библиотека во многих языках примерно одинаково помогает в задачах. Самые стандартные структуры данных там есть почти везде, но часто надо что-то более заковыристое и все равно писать руками приходится всякие деревья и прочие извращения. Единственное, чего в C++ действительно нет - это длинная арифметика. Поэтому я в свое время на соревнованиях писал на С++ и редко на java, когда BigInt был нужен.

[mayton2019]

Есть книги - сбоники задач по олимпиадному программированию.

Купи и начни решать.

[Василий Банников]

Wataru, охотно верю. А реально эта производительность помогает? Если аналогичный алгоритм на какойнибудь жаве или шарпе сделать, то там по времени/памяти не уложится?

[Wataru]

Василий Банников, В редких случаях - не уложится. Т.е. конечно, есть идеальное решение, которое пройдет на любом языке, но на С++ можно немного меньше запариваться микрооптимизациями (битовое сжатие, развороты циклов и вот это вот все).

[Дмитрий Забелин]

mayton2019,

Практику я знаю где найти но вот теорию не знаю.

[mayton2019]

Дмитрий Забелин, там нет никакой теории.

Суть подготовки в том что ты берешь олимпиадные задачи и каждый день (в СБ и ВС) с утра начинаешь
решать. Как спорстмен. У тебя - режим жизни. И в будни и в выходные.

Сначала долго. Потом быстрее и быстрее. Решение этих задач это навык. И он приобретается.

Там - обычное программирование и оно использует достаточно простые алгоритмы и структуры
данных. Но оно содержит в условиях
- ограничения (например все числа от 0 до 99999)
- время работы алгоримта не должно превышать допустим 30 секунд.
- обычно условие содержит пример в виде

Input:
Output:

И в условии всегда есть некая подсказка чтоб упростить решение. Очень часто может
применяться динамическое программирование и рекурсия. Но в этом нет никакой
олимпиадной магии. Это и есть ОБЫЧНОЕ программирование.

Просто есть лимит времени.

И код - обычно говнокод. Нет тестов. Нет рефакторинга. Нет генериков. Ты пишешь
бегом-бегом как на хакатоне. Все пишешь сплошной main функецией. Как бог даст.

[edward_freedom]

Василий Банников, так у плюсов великолепный синтаксис, из которого сейчас все тянут в шарп

[Василий Банников]

edward_freedom, ну тут вкусовщина. Мне вот плюсы не очень нравятся и в шарпы нечего из современных плюсов вроде не тащат

Answer 1

[Maryna]

Начни с классики: "Алгоритмы. Построение и анализ" от Кормена. Эта книга охватывает почти всё: от базовых структур данных до сложных алгоритмов. Также рекомендую "Грокаем алгоритмы" от Бхаргава для простого и наглядного погружения. А еще нашла книгу "Competitive Programmer’s Handbook" от Antti Laaksonen — я ее не читала, но название говорит само за себя, возможно тебе будет полезно
По поводу Лекций ИТМО и Иннополиса — это хороший выбор! Чтобы их структурировать, попробуй пройтись по уровням сложности:
Начальный уровень: основы алгоритмов, жадные алгоритмы, динамическое программирование.
Средний уровень: графы, теории чисел, строковые алгоритмы.
Продвинутый: математические основы (теория вероятностей, линейная алгебра), геометрия.
Параллельно смотри курсы на CS50, Coursera, или на YouTube вроде Errichto и WilliamFiset — у них отличная структура