В издательстве “ДМК Пресс” вышла книга “Олимпиадное программирование” с подзаголовком “Изучение и улучшение алгоритмов на соревнованиях”. Она стала глотком свежего воздуха для всех, кто интересуется, готовит и готовится к участию, или только планирует в будущем, в таком интеллектуальном виде деятельности, как различные мероприятия спортивного программирования. В России с ними знакомы недостаточно.
Российское издание книги “Guide to Competitive Programming” (издательство Springer International Publishing AG)вышло при поддержке Центра развития ИТ-образования МФТИ и его руководителя Алексея Малеева, Mail.Ru Group, а также проекта Moscow Workshops ICPC.
Автор книги — Антти Лааксонен, преподаватель и исследователь из Хельсинского университета Аалто (Финляндия) [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, потому что
Задачу можно решить «в лоб», вычислив расстояние Хэмминга между каждыми двумя строками. Временная сложность такого алгоритма равна (n
Но поскольку строки состоят из бит, решение можно оптимизировать, если хранить строки в виде целых чисел и вычислять расстояние между ними с помощью поразрядных операций. В частности, если k ≤ 32, то строки можно хранить как значения типа int и для вычисления расстояния использовать такую функцию:
Здесь операция ИСКЛЮЧАЮЩЕЕ ИЛИ строит строку, в которой единицы находятся в тех позициях, где a и b различаются. Затем число единичных разрядов вычисляется функцией __builtin_popcount. В таблице приведены результаты сравнения исходного алгоритма и алгоритма с параллельным просмотром разрядов с точки зрения времени выполнения на современном компьютере. Алгоритм с параллельным просмотром разрядов оказался примерно в 20 раз быстрее.
Таблица: Время работы алгоритмов, вычисляющих минимальное расстояние Хэмминга для n битовых строк длины k = 30
Не меньшего внимания заслуживают главы “Математика” и “Геометрия”. Как читатель уже догадался, они посвящены решению математических и геометрических задач средствами языка программирования С++ и построению соответствующих алгоритмов. В “математической” главе нас ждет пять больших тем: “Теория чисел”, “Комбинаторика”, “Матрицы”, “Вероятность” и “Теория игр”. А в “геометрической”: “Технические средства в геометрии”, “Алгоритмы на основе заметающей прямой”. Таким образом, комплексная подача построения алгоритмов для решения математических и геометрических задач, делает книгу “находкой” для “олимпиадников”, ведь на фоне дефицита книг по данной тематике, это большая редкость.
Ряд проблем, автор решил поместить в главу “Дополнительные темы”. Их освоение “ иногда может помочь при решении наиболее трудных олимпиадных задач”. Это “Квадратный корень в алгоритмах”, “И снова о деревьях отрезков”, “Дучи”, “Оптимизация динамического программирования” и “Разное”. Исходя из названия дополнительного пояснения требуют подглавы о деревьях отрезков и о разном.
Что касается деревьев отрезков, то читатель познакомится с ленивым распространением, динамическими деревьями, структурами данных в вершинах, двумерными деревьями. А в “Разном” его ждет: встреча в середине (разбиение пространства поиска на две части, приблизительно равные, выполнение поиска в каждой из частей, а далее объединение результатов), подсчет множеств, параллельный двоичный поиск, динамическая связность.
Завершают книгу справочные сведения по математике и обширная библиография (32 источника).
Итак, книга “Олимпиадное программирование” Антти Лааксонена отличное введение в мир спортивного программирования. Одновременно и замечательное справочное пособие. Книга подойдет начинающим “олимпиадникам” и поможет в систематизировании знаний опытным. Будет полезна и тренерам.
Еще раз отметим, что все примеры в книге реализованы на языке программирования C++. Он наиболее востребован на олимпиадах. Но кто-то может посчитать это недостатком книги, ведь популярны и другие языки — Python, Java. Те, кто предпочитают эти языки программирования, могут решить предложенные задачи в книге на своем любимом языке. Это будет неплохой тренировкой. В конечном итоге, именно в поиске оптимального решения и заключается выполнение олимпиадных задач.
Статью подготовил: Игорь Штомпель, автор и ведущий рубрики «Карьера\ Образование» в журнале «Системный администратор»
Российское издание книги “Guide to Competitive Programming” (издательство Springer International Publishing AG)вышло при поддержке Центра развития ИТ-образования МФТИ и его руководителя Алексея Малеева, Mail.Ru Group, а также проекта Moscow Workshops ICPC.
«Олимпиадное программирование с каждым годом становится все более популярным среди шольников и студентов. Отличным примером этому стало то, что в 2019 году мы, Moscow Workshops ICPC, в ноябре мы проведем уже десятые сборы по подготовке к чемпионату мира в самых разных точках земного шара, они уже прошли в Сингапуре, и Европе и Южной Америке, и России — от Владивостока до Москвы. В начале октября в Москве прошел Moscow Programming Contest, участие в котором приняли 2284 человека на 18 площадках московских вузов — это абсолютный рекорд по масштабу соревнования, который состоялся при поддержке Росмолодежи.На русский язык “Guide to Competitive Programming” была переведена с английского. Кроме английского и русского языка, увидело свет издание на корейском языке.
Мы очень рады столь живому интересу ребят, и готовы всячески его поддерживать — например, для студентов московских вузов мы проводим бесплатную подготовку к ICPC с участием самых лучших тренеров. И, конечно, закрепить материал, разобрать задания, подтянуть свои знания участникам всегда полезно. Поэтому я очень рад, что появилась ваша книга, и всех нас с этим поздравляю. Надеемся, что на финале ICPC в Москве в июне 2020 года будут уже те ребята, которые ее прочтут и станут героями второго, дополненного издания».
Алексей Малеев, Директор финала чемпионата мира ICPC 2020 в Москве, проректор МФТИ, основатель проекта Moscow Workshops ICPC.
Автор книги — Антти Лааксонен, преподаватель и исследователь из Хельсинского университета Аалто (Финляндия) [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
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. Те, кто предпочитают эти языки программирования, могут решить предложенные задачи в книге на своем любимом языке. Это будет неплохой тренировкой. В конечном итоге, именно в поиске оптимального решения и заключается выполнение олимпиадных задач.
Статью подготовил: Игорь Штомпель, автор и ведущий рубрики «Карьера\ Образование» в журнале «Системный администратор»
