139A - Петя и книга

139B - Ремонт

Что подразумевалось в условии:

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

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

Для каждой комнаты перебираем типы обоев и выбираем минимальный по суммарной цене. Сложность - O(mn)

139C - Урок литературы

138A - Урок литературы

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

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

Здесь можно было использовать два указателя, либо пользоваться функцией взятия подстроки (в C++ s.substr(...)). Кроме того, надо было аккуратно разобрать случаи, когда k-ая с конца гласная - первая в строке, когда гласных меньше k, и проч.

Теперь будем поддерживать три логические переменные: aabb, abab и abba, в которых храним, верно ли, что все встреченные нами четверостишия можно отнести к соответствующему типу. Для каждого нового четверостишия их легко обновить - надо сравнить нужные пары строк на рифмуемость.

Если в конце все три переменные - TRUE, то ответ - aaaa. Если все - FALSE, ответ - NO. Иначе выставлена только одна из них, она и является ответом.

Сложность - O(S), где S - сумма длин строк.

139D - Перестановки цифр

138B - Перестановки цифр

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

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

Пускай мы фиксировали число общих нулей в конце для двух перестановок. Переберем варианты цифр, дающие в сумме 10. При выборе этих цифр для определения количества нулей достаточно знать, сколько каких цифр осталось свободными в каждом числе. Если в одном числе осталось a₀, ..., a₉ цифр, а в другом b₀, ..., b₉, то количество нулей, которые дают оставшиеся цифры равно min(a₀, b₉) + min(a₁, b₈) + ... + min(a₉, b₀). Если изначально сохранить количество вхождений каждой цифры в число, посчитать ответ становится просто.

Теперь надо перебрать количество общих нулей и цифры, дающие в сумме 10, и для каждого варианта посчитать указанную выше функцию (при этом надо не забыть вычесть уже использованные цифры), а после этого правильно восстановить ответ для максимального значения. Сложность - O(10 * 10 * N) = O(N).

Основная подлость, на которую можно было напороться - решить, что надо всегда ставить все нули в конец обоих чисел, а потом подбирать остальные цифры. Это опровергает 4 претест - 1099. Легко проверить, что все варианты с нулями в конце проигрывают 1909 + 1091.

Были и другие баги, например, не учитывать вариант, когда общие нули есть, но следующие цифры не дают в сумме 10.

139E - Грибные гномы - 2

138C - Грибные гномы - 2

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

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

Способов посчитать это быстро много:

1) Сканирующая прямая. Будем идти слева направо и рассматривать события "отрезок начался", "отрезок кончился", "нашелся гриб" и поддерживать произведение вероятностей отрезков, покрывающих текущую точку. Находим гриб - прибавляем к ответу текущую вероятность.

Чтобы это реализовать, надо сохранить все события в массив (с указанием типа), а потом отсортировать по координате.

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

Это можно побороть в рамках решения:

а) Воспользоваться тем, что различных значений вероятности всего 101, и хранить массив, сколько отрезков с каждой вероятностью встретилось. При обработке гриба проходится по массиву и за ~100 операций вычислять ответ. Описанной проблемы не будет, потому что ошибка не накапливается.

б) Хранить, например, set из встреченных отрезков с вероятностями. При обработке гриба надо пройтись по сету, что делается за линейное время. При этом если перемножении элементов сета число стало очень маленьким (< 1e-10), можно дальше не перемножать и считать ответ нулем. Эта оптимизация отсекает "глубокие" перемножения, поскольку максимальное число, которое надо хранить в сете - 0.99.

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

2) Дерево интервалов.

Отсортируем грибы по координате. Каждый отрезок покрывает некий сплошной кусок массива грибов (его концы находятся бинпоиском). Это позволяет построить на массиве грибов дерево интервалов по умножению и выполнить для каждого отрезка запрос "умножить числа на интервале массива на x". Здесь тоже никаких проблем с точностью нет, поскольку нет деления.

Все вышеуказанные методы работают за O((m + n)log(m + n)), что удовлетворяет ограничениям.

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

138D - World of Darkraft

Заметим, что для "четных" и "нечетных" клеток (т.е. клеток с четной и нечетной суммой координат) игра происходит независимо: игрок делает ход в одной из них на выбор. Это позволяет применить теорию Шпрага-Гранди для определения выигрышности всей игры.

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

После этого надо сравнить функции, соответствующие множеству всех четных клеток и множеству всех нечетных. Если они равны, то ответ - "LOSE", если нет - "WIN" (по свойствам функции Гранди).

Удобнее всего организовать вычисления, заведя четырехмерный массив, где каждое измерение - номер диагонали, ограничивающей кусок с очередной стороны. Перебирать клетки внутри куска теперь удобно по диагоналям, на которых лежит клетка. По номерам диагоналей вычисляются координаты клетки, после чего надо проверить, что она лежит внутри поля и рассмотреть соответствующий ход.

Сложность - O((n + m)⁴ (количество кусков) mn (количество ходов внутри куска).

138E - Адские ограничения

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

Припишем к строке справа новый символ (при этом к массиву добавится еще один элемент). Предположим, что он не задействован ни в одном из ограничений. Тогда легко видеть, что старая часть массива не изменится.

Пусть новый символ участвует в ограничении "c l r". Количество символов c в каждом суффиксе увеличилось на 1, поэтому можно понять, для каких позиций количество ограничений изменилось:

с[. . -1 . . .с]. . . . . с[ . +1. .c] . . c

r + 2. . . r + 1 . . . l + 1. . . . l. . . .1 - номер вхождения c, считая с конца

(Квадратными скобками обозначен участок строки, на котором произошло изменение.)

Алгоритм таков: будем приписывать к строке по одному символу и поддерживать количество чисел в массиве ограничений, удовлеторяющих L ≤ x ≤ R. При добавлении символа новый элемент массива можно посчитать за O(k). Для каждого из ограничений, содержащих новый символ, найдем отрезок, на котором будет происходить изменения (на этом этапе имеет смысл разделить верхнее и нижнее ограничение на два с весами +1 и -1). Пройдемся по отрезку и изменим значения массива, поддерживая значение счетчика чисел, удовлевторяющих ограничению L ≤ x ≤ R. Теперь значение счетчика - количество подстрок, заканчивающихся в текущем символе и удовлетворяющих ограничениям задачи. Будем прибавлять этот счетчик к ответу после обработки каждого символа. Ясно, что ответ правильный.

Рассмотрим одно ограничение. Видно, что при добавлении каждого нового символа полуинтервал, в котором изменяется состояние этого ограничения, смещается вправо и не пересекается с предыдущим. Поэтому суммарное количество изменений, которые придется проделать для данного ограничения, не превышает n, а суммарное количество изменений по всем ограничениям - nk.

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

Суммарная сложность - O(nk).