Я скоро засабмичу свои решения и положу здесь ссылки.

В некоторых разборах приведены дополнительные челленджи, над которыми можно поломать голову. Делитесь идеями в комментариях. =)

465A - inc ARG

Если прибавить к числу 1, его двоичная запись поведет себя понятным образом: все младшие единицы превратятся в нули, а следующий за ними ноль станет единицей. Найдем длину максимального суффикса из единиц, пусть она равна l. Тогда ответ равен l + 1, кроме случая, когда вся строка состоит из единиц, тогда ответ l.

Забавно, что в задаче div1E тоже приходится думать о том, что будет, если прибавить к числу 1. =)

465B - Входящие (100500)

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

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

464A - Нет палиндромам!

Если строка s содержит нетривиальную подстроку-палиндром w, то она содержит и подстроку-палиндром длины 2 или 3 (к примеру, это середина строки w). Поэтому строка s является терпимой тогда и только тогда, когда никакие два соседних символа или символа через один не совпадают.

Найдем теперь лексикографически следующую терпимую строку t. Она больше, чем s, поэтому у них есть общий префикс (возможно, нулевой длины), и следующий за ним символ больше в t, чем в s. Кроме того, этот символ должен располагаться как можно правее, чтобы строка t была как можно меньше. Для каждой позиции i мы можем попытаться увеличить s_i и проверить, не совпадает ли он с s_i - 1 или s_i - 2. Если у нас получилось сделать так с каким-то символом, оставшийся суффикс всегда можно корректно дополнить, если выполняется условие p ≥ 3, поскольку при заполнении его слева направо у нас всегда не больше двух запрещенных символов. Каждый символ в суффиксе надо жадно делать как можно меньше, чтобы не создать конфликтов с тем, что уже есть слева. Пишем жадность или умный перебор, они работают за O(n). Случаи p = 1 и 2 разобрать нетрудно, потому что в первом случае подходит только a, а во втором только a, b, ab, ba (впрочем, если жадность правильная, их и разбирать особо не надо).

Это пример общего алгоритма для генерации лексикографически следующего чего угодно: попытаемся увеличить элемент в позиции, расположенной как можно правее, чтобы суффикс можно было добить как-нибудь, после этого добиваем суффикс минимальным способом.

К сожалению, оказалось, что это более простой вариант задачи, которая уже встречалась на одном из старых раундов: 196D - Следующая хорошая строка. Мы не были в курсе этого и приносим за это свои извинения. В счастью, похоже, никто не стал копировать оттуда решения. Если вам понравилась эта задача, можете попытаться решить ее усложненный вариант. =)

464B - Восстановите куб

Для этой задачи есть куча способов решения. Опишем самый лобовой: переберем все перестановки координат для каждой точки, и для всех конфигураций проверим, является ли данное множество точек вершинами куба. Количество различных конфигураций в худшем случае можно достигать (3!)⁸ > 10⁶, поэтому проверка должно работать быстро.

Проверять можно, например, так: найдем минимальное расстояние между всеми парами точек, оно должно быть равно длине ребра куба, обозначим его за l. Для каждой вершины должно найтись ровно три другие вершины на расстоянии l, и ребра, исходящие в эти вершины, должны быть попарно перпендикулярны. Если это выполняется в каждой вершине, наша конфигурация является кубом, поскольку не-куб в таких условиях построить нельзя. Такой способ выполняет примерно 8² простых операций на каждую проверку, что достаточно быстро. Существуют и другие способы проверки, опирающиеся на различные свойства куба.

Такой алгоритм можно по-разному оптимизировать, чтобы наверняка влезть в TL. Можно, например, заметить, что если переставить все координаты каждой вершины куба одинаковым образом, получится снова куб. Отсюда заключаем, что порядок координат любой одной точки можно фиксировать и перебирать только остальные. Эта простая оптимизация ускоряет алгоритм в 6 раз, что сильно облегчает задачу упихивания во время.

Челлендж: судя по всему, работает и такой способ проверки: найдем длину стороны l, и посчитаем количество пар на расстоянии l, , . Куб должен содержать ровно 12 пар первого типа, 12 пар второго типа и 4 пары третьего типа. Можете ли вы доказать, что это необходимое условие является достаточным для того, что конфигурация является кубом? Верно ли это, если координаты могут быть нецелыми? Можете ли вы придумать еще более простой способ проверки на куб?

464C - Замены в числе

Хранить всю строку после каждого запроса тяжело, потому что ее длина растет экспоненциально и запросы меняют ее сложно предсказуемым образом. Иногда помогает мудрая мысль: не можешь решить задачу, попробуй решить с конца. =)

Пусть для последовательности запросов мы знаем для каждой цифры d, в какую строку превратится после выполнения всей последовательности (обозначим ее за t_d). Тогда строка s = d₁... d_n превратится в строку t_d1 + ... + t_dn (+ означает конкатенацию). Обозначим за v(s) числовое значение строки s. Тогда v(s) можно выразить как v(t_dn) + 10^|d_n|(v(t_dn - 1) + 10^{|d_n - 1|}(...)). Поэтому, чтобы найти v(s), достаточно знать m_d = v(t_d) и s_d = 10^|t_d| для всех цифр d. Раз ответ нужен по модулю P = 10⁹ + 7, сохраним все эти числа по модулю P.

Теперь добавим спереди к последовательности новый запрос d_i → t_i. Как поменяются чиселки m_d и s_d? Очевидно, для d ≠ d_i ничего не поменяется, а для d_i их надо пересчитать по формуле выше. Это делается за время O(|t_i|). Когда добавили все запросы, ответ для исходной строки s вычисляется точно так же за время O(|s|). Получили решение за . Код по сути состоит из одной формулы, поэтому реализация получается проще некуда.

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

Челлендж: пусть мы хотим выдавать ответ после каждого запроса. Это легко делать off-line за суммарное время O(n²). Можно ли быстрее? Что, если мы обязаны отвечать онлайн?

464D - World of Darkraft - 2

В этой задаче надо было хорошо понимать вероятность, но в остальном все тоже несложно.

Обозначим количество заработанных монет X, а количество монет за продажу только предметов типа i за X_i. Понятно. что X = X₁ + ... + X_k, и EX = EX₁ + ... + EX_k (здесь EX это мат. ожидание X). Поскольку все типы имеют равную вероятность выпадения, все EX_i равны между собой, и EX = kEX₁. Давайте искать EX₁.

Если следить только за предметами одного типа, например, 1, выпадение предметов выглядит так: с вероятностью нам ничего не выпадает, а с вероятностью мы получаем предмет, уровень которого распределен как обычно. Обозначим за d_n, t среднее количество заработанных денег после убийства n монстров, если в начале у нас есть предмет уровня t. Ясно, что d_0, t = 0 (убивать больше некого, и денег мы не заработаем), а , что то же самое, что и = . Ответ находится как EX₁ = d_n, 1. К сожалению, у этой динамики Ω(n²) состояний, что слишком много при .

Можем ли мы поотсекать маловероятные события, которые не сильно влияют на ответ? Мы видим, что вероятность улучшить наш предмет падает с ростом его уровня, поэтому вряд ли он может стать очень большим. Мы знаем, что среднее количество попыток до успешеного выпадения монетки с вероятностью выпадения p равно 1 / p. Поэтому, среднее количество монстров, которых надо убить, чтобы получить предмет уровня T, равно . Поэтому в общем случае уровень нашего предмета будет равен примерно , что в наших ограничениях не превосходит 500. Мы хотим найти такую границу B, что если отсечь все состояния при t > B, ответ изменится не сильно. Это можно сделать, если честно посчитать дисперсию T и применить какое-нибудь неравенство типа Чебышева, или установить опытным путем: если мы увеличили границу, а ответ не поменялся, значит, она уже достаточно хорошая. На практике оказывается, что B ≥ 700 хватает для заданной точности. Получили решение за время (мы опираемся на то, что , и константа C спрятана в О-большом).

Челлендж: пусть мы убиваем монстров и предметы выпадают по тем же правилам, но теперь мы каждый раз можем выбрать, хотим мы продать новый предмет или уже имеющийся того же типа. Мы хотим максимизировать количество монет в конце. Каково мат. ожидание этого количества, если мы действуем оптимально?

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

464E - Классическая задача

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

То, что вес каждого ребра — это степень двойки, подсказывает нам, что можно хранить битовую запись длины пути, поскольку она не сильно меняется при добавлении одного ребра. Но хранить все записи явно для всех вершин нельзя, поскольку суммарное количество единиц в них Ω(nd) (где d — это максимальное значение x_i), что не влезает в память даже с битовой магией.

Хочется воспользоваться какой-нибудь полезной структурой. Хорошо подходит персистентное дерево отрезков, которое хранит битовую запись. Персистентное дерево отличается от обычного тем, что каждый раз, когда мы хотим поменять состояние какой-то вершины, мы вместо этого создаем копию этой вершины и записываем новые значения в нее. Теперь у нас есть что-то вроде <<системы контроля версий>> над деревом: все состояния каждой вершины, и к любой вершине можно делать запросы, поскольку все ее поддерево, достижимое по ссылкам, остается неизменным. В таком дереве все запросы все еще выполняются за времени, но каждый запрос может потребовать создания дополнительных вершин.

Какие запросы к дереву мы хотим делать? Чтобы прибавить к числу 2^x, нужно найти ближайший ноль к x-ой позиции, записать в него единицу и заполнить нулями все позиции от него до x. Это умеет делать дерево с ленивым проталкиванием, которое тоже можно сделать персистентным.

Сравнивать два числа можно так: найдем самый старший бит, где числа отличаются, тогда то число, у которого в этом бите записан 0, меньше; если никакие биты в числах не различаются, они равны. Это можно делать за , если хранить хэши поддеревьев в каждой вершине и параллельно спускаться по обоим деревьям. Ограничения по времени и памяти были очень добрыми, поэтому разных хэшей можно было хранить сколько душе угодно и не бояться коллизии.

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

Главная ошибка, которую можно было сделать — сравнивать числа за дополнительной памяти, поскольку чтобы спускаться по дереву, нам иногда приходится делать проталкивания, и это создает новые вершины. Если так делать, мы съедим памяти, что в ML уже не влезает никак. От этого можно избавляться по-разному; например, если мы приходим в вершину, из которой надо что-то протолкнуть вниз, это значит, что весь отрезок этой вершины состоит из одинаковых чисел, поэтому ответить на запрос о сравнении можно уже сейчас.

Я хочу описать, как мне кажется, самое изящное решение по времени, памяти и простоте кода, которое позволяет совсем избавиться от ленивого проталкивания. Сперва создадим два дерева, полностью заполненных нулями и единицами соответственно. Пусть теперь мы присваиваем что-то на отрезке (пускай, для определенности, ноль), и текущая вершина целиком лежит внутри отрезка из запроса. Теперь вместо того, чтобы создавать копию и/или проставлять какие-то пометки, заменим эту вершину на соответствующую вершину из дерева с нулями. Все, поддерево этой вершины заполнено нулями, как мы и хотели. Если так делать, каждая операция создает новых вершин (с ленивым проталкиванием такого достичь не удастся, придется создавать минимум ), кроме того, вершины хранят в себе меньше информации и занимают меньше памяти. И про проталкивание чего бы то ни было думать не надо. Красота.

К этой задаче челлендж отсутствует, она и так достаточно challenging. =) Эта задача — хорошее упражнение, если вы хотите научиться работать со сложными структурами, поэтому всячески рекомендую ее написать и сдать в дорешку.

Все. Если остались вопросы, не стесняйтесь спрашивать в комментах. Благодарю за внимание.