Вышла книга «Олимпиадное программирование»

    В издательстве “ДМК Пресс” вышла книга “Олимпиадное программирование” с подзаголовком “Изучение и улучшение алгоритмов на соревнованиях”. Она стала глотком свежего воздуха для всех, кто интересуется, готовит и готовится к участию, или только планирует в будущем, в таком интеллектуальном виде деятельности, как различные мероприятия спортивного программирования. В России с ними знакомы недостаточно.

    Российское издание книги “Guide to Competitive Programming” (издательство Springer International Publishing AG)вышло при поддержке Центра развития ИТ-образования МФТИ и его руководителя Алексея Малеева, Mail.Ru Group, а также проекта Moscow Workshops ICPC.



    «Олимпиадное программирование с каждым годом становится все более популярным среди шольников и студентов. Отличным примером этому стало то, что в 2019 году мы, Moscow Workshops ICPC, в ноябре мы проведем уже десятые сборы по подготовке к чемпионату мира в самых разных точках земного шара, они уже прошли в Сингапуре, и Европе и Южной Америке, и России — от Владивостока до Москвы. В начале октября в Москве прошел Moscow Programming Contest, участие в котором приняли 2284 человека на 18 площадках московских вузов — это абсолютный рекорд по масштабу соревнования, который состоялся при поддержке Росмолодежи.

    Мы очень рады столь живому интересу ребят, и готовы всячески его поддерживать — например, для студентов московских вузов мы проводим бесплатную подготовку к ICPC с участием самых лучших тренеров. И, конечно, закрепить материал, разобрать задания, подтянуть свои знания участникам всегда полезно. Поэтому я очень рад, что появилась ваша книга, и всех нас с этим поздравляю. Надеемся, что на финале ICPC в Москве в июне 2020 года будут уже те ребята, которые ее прочтут и станут героями второго, дополненного издания».

    Алексей Малеев, Директор финала чемпионата мира ICPC 2020 в Москве, проректор МФТИ, основатель проекта Moscow Workshops ICPC.
    На русский язык “Guide to Competitive Programming” была переведена с английского. Кроме английского и русского языка, увидело свет издание на корейском языке.

    Автор книги — Антти Лааксонен, преподаватель и исследователь из Хельсинского университета Аалто (Финляндия) [3] с большим опытом преподавания программирования и алгоритмов, тренер команды Финляндии на международных соревнованиях по программированию. Он имеет высокий рейтинг 2347 и статус “международный мастер” на портале Codeforces под ником “pllk” [4]. В 2008 году он А. Лааксонен стал одним из организаторов олимпиады по информатике в своей стране. В 2016 — научным руководителем Балтийской олимпиады по информатике.

    Целевой аудиторией книги являются все интересующиеся и/или работающие в сфере олимпиадного программирования. Но, для полноценного усвоения материала потребуется знание основ программирования, при этом автор не требует от читателя опыта проектирования алгоритмов и участия в олимпиадах. Все это позволяет рекомендовать данную работу достаточно широкому кругу заинтересованных читателей. Для начинающих она станет введением в современное олимпиадное программирование, опытным специалистам поможет систематизировать знания, станет для них справочным пособием.

    Подача материала в книге осуществляется от простого к сложному. Вначале знакомится с целями и задачами книги, с олимпиадным программированием, сборником задач CSES [5] и прочими актуальными книгами по олимпиадному программированию.

    Получив необходимую теоретическую базу читатель будет готов перейти к практике. Техника программирования — следующая тема. В нее автор включил основы языка С++ (стандарт С11), на котором реализованы все примеры в книге; разбор рекурсивных алгоритмов и поразрядных операций.

    В главах книги читатель сможет найти информацию о большинстве “стандартных” тем и примеров реализации алгоритмов, которые предлагаются участникам олимпиад по программированию: структуры данных, динамическое программирование, графовые алгоритмы и алгоритмы на деревьях, запросы по диапазону, работа со строками.

    Отдельно хотелось бы выделить ряд глав книги. Например, глава «Избранные вопросы проектирования алгоритмов». В нее вошли алгоритмы с параллельным просмотром разрядов, амортизационный анализ, нахождение минимальных значений. Читателю предлагаются алгоритмы нахождения расстояния Хэмминга, решение задачи на достижимость в графах, метод двух указателей, троичный поиск, минимизация сумм и другие интереснейшие темы для “олимпиадников” и их тренеров.

    В качестве примера, приведу пример задач из главы “Избранные вопросы проектирования алгоритмов”.

    Рассмотрим алгоритмы с параллельным просмотром разрядов, в которых для эффективной обработки данных используются поразрядные операции. В типичном случае мы можем заменить цикл for поразрядными операциями, что существенно уменьшает время работы алгоритма.

    Алгоритмы с параллельным просмотром разрядов


    Алгоритмы с параллельным просмотром разрядов основаны на том факте, что отдельными разрядами числа можно манипулировать параллельно, применяя поразрядные операции. Поэтому один из способов проектирования алгоритмов – представить шаги алгоритма таким образом, чтобы их можно было эффективно реализовать с помощью поразрядных операций.

    Расстояние Хэмминга Расстоянием Хэмминга


    hamming(a, b) между строками a и b одинаковой длины называется количество позиций, в которых эти строки различаются. Например:

    hamming(01101, 11001) = 2.

    Рассмотрим следующую задачу: дано n битовых строк длины k, вычислить минимальное расстояние Хэмминга между двумя строками. Например, для строк [00111, 01101, 11110] ответом будет 2, потому что

    • hamming(00111, 01101) = 2;
    • hamming(00111, 11110) = 3;
    • hamming(01101, 11110) = 3.

    Задачу можно решить «в лоб», вычислив расстояние Хэмминга между каждыми двумя строками. Временная сложность такого алгоритма равна (n

    $O(n^2k)2$

    k). Для вычисления расстояния между строками a и b служит следующая функция:

    int hamming(string a, string b) {
    int d = 0
    for (int i = 0; i < k; i++) {
    if (a[i] != b[i]) d++;
    }
    return d;
    }
    

    Но поскольку строки состоят из бит, решение можно оптимизировать, если хранить строки в виде целых чисел и вычислять расстояние между ними с помощью поразрядных операций. В частности, если k ≤ 32, то строки можно хранить как значения типа int и для вычисления расстояния использовать такую функцию:

    int hamming(int a, int b) {
    return __builtin_popcount(a^b);
    }
    

    Здесь операция ИСКЛЮЧАЮЩЕЕ ИЛИ строит строку, в которой единицы находятся в тех позициях, где a и b различаются. Затем число единичных разрядов вычисляется функцией __builtin_popcount. В таблице приведены результаты сравнения исходного алгоритма и алгоритма с параллельным просмотром разрядов с точки зрения времени выполнения на современном компьютере. Алгоритм с параллельным просмотром разрядов оказался примерно в 20 раз быстрее.

    Таблица: Время работы алгоритмов, вычисляющих минимальное расстояние Хэмминга для n битовых строк длины k = 30



    Не меньшего внимания заслуживают главы “Математика” и “Геометрия”. Как читатель уже догадался, они посвящены решению математических и геометрических задач средствами языка программирования С++ и построению соответствующих алгоритмов. В “математической” главе нас ждет пять больших тем: “Теория чисел”, “Комбинаторика”, “Матрицы”, “Вероятность” и “Теория игр”. А в “геометрической”: “Технические средства в геометрии”, “Алгоритмы на основе заметающей прямой”. Таким образом, комплексная подача построения алгоритмов для решения математических и геометрических задач, делает книгу “находкой” для “олимпиадников”, ведь на фоне дефицита книг по данной тематике, это большая редкость.

    Ряд проблем, автор решил поместить в главу “Дополнительные темы”. Их освоение “ иногда может помочь при решении наиболее трудных олимпиадных задач”. Это “Квадратный корень в алгоритмах”, “И снова о деревьях отрезков”, “Дучи”, “Оптимизация динамического программирования” и “Разное”. Исходя из названия дополнительного пояснения требуют подглавы о деревьях отрезков и о разном.

    Что касается деревьев отрезков, то читатель познакомится с ленивым распространением, динамическими деревьями, структурами данных в вершинах, двумерными деревьями. А в “Разном” его ждет: встреча в середине (разбиение пространства поиска на две части, приблизительно равные, выполнение поиска в каждой из частей, а далее объединение результатов), подсчет множеств, параллельный двоичный поиск, динамическая связность.

    Завершают книгу справочные сведения по математике и обширная библиография (32 источника).

    Итак, книга “Олимпиадное программирование” Антти Лааксонена отличное введение в мир спортивного программирования. Одновременно и замечательное справочное пособие. Книга подойдет начинающим “олимпиадникам” и поможет в систематизировании знаний опытным. Будет полезна и тренерам.

    Еще раз отметим, что все примеры в книге реализованы на языке программирования C++. Он наиболее востребован на олимпиадах. Но кто-то может посчитать это недостатком книги, ведь популярны и другие языки — Python, Java. Те, кто предпочитают эти языки программирования, могут решить предложенные задачи в книге на своем любимом языке. Это будет неплохой тренировкой. В конечном итоге, именно в поиске оптимального решения и заключается выполнение олимпиадных задач.

    Статью подготовил: Игорь Штомпель, автор и ведущий рубрики «Карьера\ Образование» в журнале «Системный администратор»

    Комментарии 17

      0
      Дочка участвовала в олимпиадах по программированию, жаловалась, что пока напишешь портянку с решением на C++, люди на Python уже всё решили в несколько строчек.
      P.S. Книжку заказал, спасибо.
        +1

        Я не олимпиадник, участвовал всего один раз, но мне кажется есть два разных типа задач на олимпиадах:


        1) Пожалуйста, простой найдите ответ (удобно Python)
        2) Пожалуйста, реализуйте алгоритм так, чтобы он прошел тесты производительности (неудобно писать на C++, но проще уложиться в нагрузку)


        Не уверен, что на всех школьных олимпиадах часто практикуются задачи второго типа, поэтому Python там куда более подходящий кандидат.

          0

          Именно так и есть. Те, кто берут первые места на уровне страны, чаще всего быстро пишут первую (иногда вторую) задачи на Python, остальные на плюсах.

            0

            Лимиты ресурсов разные для разных языков? Ведь c++ всегда будет выиграть по памяти, да и по CPU то же.

              0
              Кстати, да, лимиты разные. Иначе глупо давать задачу на питоне, если она всё равно не укладывается в указанные лимиты.
              0
              С одной стороны согласен. С другой стороны, я уверен, что C++ полезней с точки зрения изучения алгоритмов и структур данных, чем Python. Одновременно два языка тянуть дочке тяжеловато (но, по мнению учителя, вроде справляется).

              Заметил, что после решения задачи на C++, перенести решение на Python ей гораздо проще, чем с Python на C++. То есть хоть в C++ порог вхождения выше, но и понимания он даёт много больше. Стараюсь её убедить, что в перспективе упор на C++ принесёт свои плоды.
                0

                Советовал обратить ваше внимание и дочки на Rust. Возможности с++ с безопасность раст компилятора — хорошее сочетание, а разница достаточно не велика. И да, его тоже в олимпиадном используют, хотя и меньше.

                  0
                  Например, на крупнейшей студенческой олимпиаде — ICPC (International Collegiate Programming Contest), для северо-восточного региона, доступны следующие языки:

                  C++;
                  Java;
                  Python;
                  Kotlin.

                  При этом, не гарантируется, что все проблемы (problems) могут быть решены на Python.
                    0
                    The jury uses the following commands to run solutions: C++ = executable file


                    Если двоичный код проверяется в песочнице, то выбор С++ vs Rust может быть в пользу безопасного Rust. Хотя… я предлагал только обратить пристальное внимание на «плюшки», которые делают Раст компилятор уникальным, хотя и более «строгим» выдавая двоичный код под все основные платформы.
                    Если они должны компилировать только С++, тогда грусть.
                      0
                      Что касается Rust, то многое из того, что Вы написали справедливо. Сейчас, намечается интересная тенденция его развития.

                      В тексте прямо сказано: «доведение языка Rust до паритета с языком Си в области системного программирования».
                        0

                        На мой взгляд Rust обладает очень неприятной для олимпиад строгостью и ограничениями. Для промышленного применения это прекрасно, но для рамок в 30-90 минут на задачу, которая пишется один раз и мозг не теряет контекст это может быть фатальным. Тут борроу-чекер и принуждение к иммутабельности может сыграть весьма злую шутку. Посмотрите на ставший уже классикой разбор реализации связанных списков, особенно на моменты в двунаправленном связанном списке (это в конце). Хотя я не исключаю, что написав хотя бы 20-50 KLOC олимпиадных задач это всё становится достаточно незначимым (но это 50-100 не самых мелких задач, то есть порядка года интенсивной работы с учётом загрузки в учёбе).

                0

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

                  0
                  Автор книги отмечает, что в настоящее время на соревнованиях по программированию наиболее популярны — С++, Python, Java. Он приводит статистику Google Code Jam 2017 (3000 лучших участников):

                  79% писали на C++;
                  16% — Python;
                  8% — Java.

                  По мнению автора, достоинства C++ — высокая эффективность, наличие в стандартной библиотеке большого количества «разнообразных структур данных и алгоритмов».

                  Итак, С++ — быстрый с большими возможностями.

                  Java чуть медленнее (виртуальная машина), программы длиннее.

                  Python медленне С++, и соответственно, Java. Сложности в задачах, в которых важно время выполнения программы. Компактные программы. Более подойдет для решения задач, в которых нет ограничения по времени.

                  Итак, как сказал Антти Лааксонен в книге «Олимпиадное программирование»: «Если вы еще не знаете С++, самое время начать его изучение.».
                    0

                    Если дочка уже умеет на С++, то она и на Python сможет без проблем после дня ознакомления с ним.

                    0
                    У издательства ДМК выходит очень много толковых книг, и эта одна из книг, которая должна быть в моей библиотеке
                      0

                      Спасибо за наводку, заказал. Не так уж много книг хороших на эту тему.

                        0

                        Купил книгу. Читаю — пока около 100 страниц, но впечатление уже сложилось.


                        Эх! Эту книгу бы мне 25 лет назад, я б за неё душу продал! Тогда, правда, С++ был… э… слегка другой, но это же мелочи :)
                        Что мне понравилось:


                        • Акцент на типичных ошибках и пролётах в олимпиадах.
                        • Акцент на типичных приёмах, экономящих силы и время на олимпиадах. Сюда же практичность приёмов: без размусоливаний всех возможностей того же vector на паре страниц всё, что про него надо знать в олимпиадных задачах.
                        • Относительно доступное изложение. Ну то есть Дональда Кнута читать в разы сложнее.
                        • Всё иллюстрируется кодом.

                        Что не понравилось:


                        • Много неточных формулировок. Причём, судя по характеру неточностей — они таки пришли из оригинала. От изложения главы "3. Эффективность" и неаккуратного применения O-нотации в следующей главе меня вообще непрерывно бомбило. В той же главе ни слова про память, ни слова про системные вызовы (включая аллокацию/освобождение), а им там самое место.
                        • В целом изложение доступно (я бы в старших классах осилил), но местами простую мысль закочерыжили в такие формулировки, что абзац надо по три раза перечитывать. Тут я не знаю, где источник кривизны — в оригинале или в переводе.
                        • В этой книге органично бы смотрелось по 1-3 задачи в конце главы. А их нет.
                        • Общее ощущение от книги, как от слайдов к крутому докладу. Ну то есть в ней процентов 10 от каждой темы. Классные 10% и самые важные, которые нужны в 80% случаев. Правда, как будто автор поставил следующий слайд и несколько минут рассказывал всё это, но ты, блин, видишь только слайд.

                        Итоговое впечатление очень положительное. Книга must have для тех, кто планирует выходить хотя бы на уровень областных школьных олимпиад, не говоря уже о глобальных контестах. Спасибо за книгу!


                        Про цены. Я не особо задумываясь купил книгу в "Лабиринте". Но там с моими большими скидками и с чёрнопятничной распродажей получилось около 1000 (а без них так вообще 1600+). А в самой книге написан адрес магазина издательства, где она по 800 рублей. Причём мне до их склада 10 минут пешком идти. Ну да ладно, не разорюсь, всё равно календарей с котом Саймона к новому году заказал :)

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое