Мы хотели бы также поблагодарить тестеров задач этого раунда и олимпиады ЗКШ: alger95, thefacetakt, adamant, -imc-, riskingh, ASverdlov.

Пожалуйста, пишите в комментариях о найденных ошибках.

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

520A - Панграмма

Идея:Endagorion

Подготовка:Endagorion

Чтобы проверить, что все буквы присутствуют, заведем массив длины 26 и для каждой буквы поставим в соответствующую ячейку единичку. В конце надо проверить, что все 26 единичек на месте. Решение работает за O(n). Также надо не забыть перевести все буквы к нижнему регистру (или наоборот, все буквы к верхнему).

Чтобы перевести буквы в нижний регистр, можно использовать встроенные функции, например, tolower в Python. Также можно пользоваться тем, что буквы от a до z идут подряд по их ASCII-номерам; ASCII-номер для символа можно получить при помощи ord(c) во многих языках. Теперь, чтобы получить номер буквы в алфавите, надо написать ord(c) - ord('a'), а на C++ или C просто c - 'a' (поскольку в C/C++ символ — это число, равное его ASCII-номеру). Также, например, чтобы проверить, что буква имеет нижний регистр, надо написать неравенство ord('a') <= ord(c) && ord(c) <= ord('z').

Challenge: сколько существует различных панграмм длины n? Строки, отличающиеся капитализацией некоторых символов, считаются различными. Сможете ли вы придумать линейное по времени решение?

520B - Две кнопки

Идея: Endagorion

Подготовка: Endagorion

Самое простое решение — просто запустить обход в ширину. Построим граф, в котором вершины — числа, а ребра ведут из одного числа в другое, если можно получить второе из первого за одну операцию. Можно заметить, что первое число никогда не выгодно делать больше, чем 2m, поэтому в графе будет не больше 2·10⁴ вершин и 4·10⁴ ребер, и BFS сработает очень быстро.

Однако, есть решение гораздо быстрее. Развернем задачу: изначально у нас есть число m, и мы хотим получить число n, пользуясь операциями "прибавить к числу 1" и "поделить число на 2, если оно четно".

Пускай мы в какой-то момент применили две операции типа 1, и потом операцию типа 2; но эти три операции можно заменить на две: сначала операция типа 2, а потом одна операция типа 1, и количество операций от этого уменьшится. Отсюда следует, что применять больше одной операции типа 1 имеет смысл только тогда, когда операций типа 2 больше не будет, то есть, когда n меньше m и осталось сделать несколько прибавлений, чтобы их сравнять. На самом деле, теперь существует ровно одна последовательность операций, удовлетворяющая таким требованиям: если n меньше m, прибавляем единички пока нужно, иначе если n четно, делим на 2, а если нечетно, прибавляем 1 и потом делим на 2. Количество операций в такой последовательности можно найти за время .

Challenge: рассмотрим обобщенную задачу: мы хотим получить число n из числа m с помощью операций двух типов "отнять a" и "умножить на b". Обобщите решение исходной задачи и научитесь находить минимальное количество операций за время в случае, если a и b взаимно просты. Справитесь ли вы, если у a и b могут быть нетривиальные общие делители?

520C - Выравнивание ДНК/521A - Выравнивание ДНК

Идея: Endagorion

Подготовка: Endagorion

Что это за функция — ρ(s, t)? Для каждого символа t и каждого символа s существует ровно один циклический сдвиг, который их совмещает (действительно, после 0, ..., n - 1 сдвигов символ t пробежит все возможные положения в строке, и ровно одно из них — это положение символа из s); поэтому, существует ровно n способов циклически сдвинуть s и t, при которых выбранные символы совместятся (поскольку ситуация симметрична для любого положения символа из s). Таким образом, вклад в ρ, который дает символ t_i, равен n × (количество символов s, равных t_i). Поэтому ρ(s, t) максимально, когда каждый символ t встречается в s наибольшее количество раз. Посчитаем для каждого символа количество вхождений в s; ответ равен Kⁿ, где K — это количество типов символов, которые встречаются в s чаще всего. Решение за O(n).

Challenge: мы знаем, что ρ_max(s) = C(s)·n², где C(s)--- максимальное количество вхождений какого-либо символа. Сколько существует строк s длины n над алфавитом размера k, таких что C(s) = m? Сможете придумать решение за время O(kn²)? За время ? За время ? Может быть, еще быстрее? (Подсказка: для быстрого решения необходим удачно подобранный простой модуль. =))

520D - Кубики/521B - Кубики

Идея: savinov

Подготовка: savinov, sokian, zemen

В эквивалентной формулировке, первый игрок стремится максимизировать лексикографиский порядок последовательности кубиков, а второй игрок — минимизировать его. Поэтому, на каждом шагу первый игрок берет максимальный из доступных кубиков, а второй — минимальный.

Сперва научимся проверять, можно ли в текущей ситуации взять некоторый кубик. Его нельзя взять только тогда, когда есть какой-то кубик, который на нем "стоит" (т.е. имеет координаты (x - 1, y + 1), (x, y + 1) или (x + 1, y + 1)), и наш кубик является единственным, на котором он стоит. Это условие можно явно проверить. Из-за больших координат это не получится сделать путем простых обращений к массиву, поэтому придется завести ассоциативный массив, например, в C++ можно воспользоваться set.

Теперь надо научиться находить максимальный/минимальный кубик среди доступных. Просто линейный проход — это слишком долго, поэтому заведем еще одну структуру, в которой будем хранить номера доступных кубиков. Структура должна уметь добавлять, удалять, а также искать максимум/минимум, так что что-нибудь вроде set нам снова подойдет.

После того, как ход сделан, какие-то кубики могли стать доступными или, наоборот, перестать быть доступными. Однако, после каждого хода состояние могло поменяться только для O(1) кубиков: кубики (x ± 1, y) и (x ± 2, y) могли стать недоступными, потому что какой-то из кубиков выше стал опасным (т.е., остался один кубик, на котором он держится), и еще какие-то из кубиков (x - 1, y - 1), (x, y - 1) и (x + 1, y - 1) могли сделаться доступными, потому что единственный опасный кубик, который на них стоял, был удален. В любом случае, для всех них надо просто заново сделать проверку, и про случаи можно особо не думать.

Решение с подходящей структурой работает за .

Challenge (по мотивам вопросов от jk_qq и RetiredAmrMahmoud): пусть теперь кубики выкладываются в ряд справа налево, т.е. от младших разрядов к старшим. Первый игрок все так же хочет максимизировать итоговое число, второй — минимизировать его. Если оставить правила убирания кубиков такими же, в общем случае задача не выглядит решаемой. Попробуйте решить новую задачу в случае, когда кубики выстроены в несколько независимых башен, т.е. кубик можно убрать, если он находится на вершине своей башни.

520E - Сплошные плюсы/521C - Сплошные плюсы

Идея: Endagorion

Подготовка: gchebanov, DPR-pavlin

Рассмотрим какой-нибудь способ расставить плюсы, а также какую-то цифру d_i (цифры пронумеруем с нуля слева направо). Эта цифра дает вклад в сумму чисел, равный d_i·10^l, где l — расстояние до ближайшего плюса справа или до конца строки, если справа нет плюсов. Если просуммировать эти значения по всем цифрам и по всем способам расставить плюсы, получим в точности ответ.

Сколько существует способов расставить плюсы для выбранной цифры d_i и какого-то фиксированного l? Во-первых, рассмотрим случай, когда при разбиении по плюсам часть, содержащая цифру d_i, не является последней, т.е., i + l < n - 1. Всего существует n - 1 позиция, куда можно ставить плюсы; ограничение, связанное с цифрой d_i и расстоянием l, означает, что после цифр d_i, ..., d_{i + l - 1} плюсов не стоит, а после цифры d_i + l плюс стоит. Иными словами, строка выглядит примерно так:

На рисунке точка означает отсутствие плюса, а вопросик значит, что неважно, стоит там плюс или нет. Видно, что из n - 1 возможных позиций для плюсов состояния (l + 1)-ой позиции определены, и среди них использован только один плюс. Это значит, что в остальные (n - 1) - (l + 1) = n - l - 2 надо поставить k - 1 плюс любым из способов; значит, искомое количество способов равно . Рассуждая схожим образом, получим, что если цифра d_i входит в последнюю часть (т.е. i + l = n - 1), количество способов равно .

В итоге получаем, что ответ равен

Преобразуем:

Чтобы посчитать такие суммы, нам надо предпосчитать все степени 10 до n-ой (по модулю 10⁹ + 7), а также биномиальные коэффициенты. Чтобы их посчитать, вспомним, что , поэтому достаточно вычислить все k! для k вплоть до n, а также их обратные значения по модулю. Помимо этого, нам пригодится массив префиксных сумм для цифр d_i, т.е., значения . Осталось просто просуммировать произведения этих величин.

В итоге получили решение за , поскольку стандартные алгоритмы для поиска обратных по модулю (а именно, малая теорема Ферма с бинарным возведением в степень и решение диофантова уравнения при помощи обобщенного алгоритма Евклида) имеют верхнюю оценку сложности . Однако, можно воспользоваться интересным трюком и вычислить все обратные элементы для первых n чисел за линейное время, после чего итоговоая сложность решения становится O(n); почитать про интересный трюк можно в комментарии от Kaban-5 (непонятно, почему он заминусован; может быть, кто-то вспомнит ссылку на более фундаментальный источник для этого метода?).

Challenge: теперь мы хотим посчитать сумму всех выражений, в которых расставлено k плюсов для всех k от a до b; т.е. мы хотим просуммировать ответы для исходной задачи по всем k = a, ..., b. Числа a и b любые, такие что 0 ≤ a ≤ b ≤ n - 1. Решение за O(n²) очевидно: для каждого k посчитаем ответ отдельно. Сможете ли вы придумать решение за линейное время?

521D - Магазин

Идея: Endagorion

Подготовка: gchebanov

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

Теперь рассмотрим также прибавления, а про умножения временно забудем. Ясно, что для каждого скилла надо взять несколько максимальных прибавлений (возможно, ни одного). Для каждого скилла отсортируем прибавления по невозрастанию b_i; теперь для каждого скилла надо взять несколько первых апгрейдов. Итак, теперь для выбранного скилла есть невозрастающая последовательность прибавлений b₁, ..., b_l, и начальное значение скилла равно какому-то a. Раз мы решили взять некоторый префикс массива b, это значит, что когда мы берем апгрейд b_i, значение скилла увеличивается с a + b₁ + ... + b_i - 1 до a + b₁ + ... + b_i - 1 + b_i. Иными словами, значение, на которое домножится значение скилла (а значит, и все произвдение значений скиллов), равно дроби . Теперь, когда это отношение однозначно определилось для каждого прибавления, мы можем считать любое прибавление умножением. =) Теперь посчитаем такие отношения для всех прибавлений (т.е., отсортируем b-шки для каждого скилла по отдельности и найдем значения всех дробей), и затем посортируем умножения и прибавления вместе по тому, во сколько раз они увеличивают итоговый ответ. Ясно, что все умножения надо использовать уже после того, как были сделаны все прибавления; иными словами, для определения того, какие апгрейды брать, мы сортируем их все вместе по их отношениям, но реальный порядок применения должен быть таким: сперва все прибавления, а потом все умножения.

Наконец, разберемся с присваиваниями. Очевидно, что для каждого скилла имеет смысл делать не более одного присваивания, и использовать можно только максимальное присваивание для данного скилла. Кроме того, присваивание необходимо делать перед всеми прибавлениями и умножениями. Поэтому, для каждого скилла надо просто определиться, берем мы для него максимальное присваивание или нет. Однако есть проблема с тем, что когда мы сделали присваивание, отношения для прибавлений стали неправильными, поскольку стартовое значение a поменялось.

Представим теперь, что мы уже выбрали, какие прибавления мы сделаем, и теперь решаем, брать присваивание или нет. Если мы берем присваивание, то итоговое значение скилла поменяется с a + b₁ + ... + b_k на b + b₁ + ... + b_k. Иными словами, присваивание работает примерно так же, как и прибавление значения b - a. Единственная разница в том, что присваивание необходимо ставить раньше всех прибавлений.

Итак, переделаем все максимальные присваивания для каждого скилла в прибавления b - a и обработаем их вместе со всеми остальными присваиваниями (которые, как мы знаем, в итоге станут умножениями =)).

В итоге, задача свелась к сортировке отношений для всех апгрейдов. Оценим, какие числа у нас будут стоять в дробях. Отношение для умножения — это целое число до 10⁶; отношение для прибавления — это дробь, которая выглядит как . Поскольку k может быть порядка 10⁵, а b_i — порядка 10⁶, числитель и знаменатель дроби могут быть порядка 10¹¹. Когда мы сравниваем дроби и , мы сравниваем произведения ad и bc, которые по нашим оценкам могут быть порядка 10²². Это, к сожалению, приводит к переполнению встроенных целочисленных типов во многих языках. Чтобы разобраться с этой проблемой, вычтем из всех дробей единицу (очевидно, на порядок сортировки это не повлияет), и теперь отношения для прибавлений выглядят как . Теперь, числитель стал всего лишь порядка 10⁶, произведения будут порядка 10¹⁷, что уже помещается в стандартный 64-битный тип в любом языке.

Challenge: пускай нам надо сравнить две дроби и , где числа a, b, c, d могут быть порядка 10¹⁸. Каким способом вы бы это сделали? Сможете ли вы придумать простое решение, которое не использует длинную арифметику, вещественные числа или волшебные целочисленные типы, такие как __int128 и им подобные (однако, возможно, совершает неконстантное число операций)?

521E - Cycling City

Идея: Endagorion

Подготовка: Endagorion

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

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

Теперь, у нас есть двусвязная компонента и та же самая задача. Во-первых, найдем любой цикл в этой компоненте обычным DFS'ом; единственный случай, когда цикл не найдется, — это когда компонента состоит из одного ребра, но это неинтересный случай. Теперь, предположим, что ни из какой вершины цикла не исходит ребра, которое бы не лежало в цикле; в этом случае цикл не связан ни с какой другой вершиной компоненты, поэтому компонента сама по себе является этим циклом; очевидно, что в этом случае решения также нет.

В противном случае, возьмем вершину v, из которой исходит ребро e, не лежащее в выбранном цикле (обозначим цикл за c). Если мы сможем найти такой путь p, который начинался бы с ребра e и заканчивался в какой-то вершине из цикла u (отличной от v), мы сможем выделить три непересекающихся пути между u и v: один из них — это p, а два других — половинки исходного цикла. Чтобы найти путь p, запустим DFS, который начинается с ребра e и заканчивается, как только мы приходим в вершину цикла c, отличную от v, а потом восстанавливает все пути для ответа.

Что же делать, если такого пути p не найдется? Обозначим за C компоненту, которую обошел этот DFS. У него не получилось найти пути между вершинами из множества C\ {v} и множества c\ {v}, поэтому любой путь между этими двумя множествами должен проходить через v. Но тогда оказывается, что если удалить v, компонента C\ {v} оказывается отделена от вершин из множества c\ {v}, что противоречит тому, что исходная компонента была двусвязной. Отсюда следует, что тот DFS, который мы запускали из e, всегда найдет подходящий путь p и получит ответ, если наша двусвязная компонента — не цикл и не отдельное ребро.

В итоге мы пришли к тому, что ответа нет в единственном случае, когда все двусвязные компоненты — либо отдельные ребра, либо циклы; другими словами, когда граф является несвязным набором кактусов. В противном случае, за пару запусков DFS'ов мы сможем найти три непересекающихся пути. В итоге получилось решение за время O(n + m); для упрощения можно было бы где-нибудь накрутить парочку логарифмов.

Challenge: сколько существует графов G, таких что в G можно выбрать две вершины, соединенные тремя непересекающимися путями? (Подсказка: мы знаем, что достаточно посчитать количество несвязных объединений кактусов.) Можете ли вы придумать какое-нибудь полиномиальное по времени решение? Решение за время O(n³)? Возможно, еще быстрее?