A. Электронные таблицы

Вычтем из k единицу, перейдя к нумерации столбцов с 0.

Выясним сначала, сколько символов входит в название столбца. Для этого будем последовательно отнимать от k степени числа 26, пока очередная степень не окажется больше оставшегося числа k'.

Теперь для получения имени столбца достаточно перевести k' в 26-ричную систему счисления с цифрами A–Z и дополнить ведущими нулями (точнее символами A) до необходимого числа символов. Это можно сделать стандартными методами языка программирования (правда при этом получатся цифры 0–9, A–P, их надо будет заменить), либо самостоятельно реализовав алгоритм перевода в систему счисления с заданным основанием.

Небольшое замечание: за день до тура один из тестеров указал, что задача B с раунда CF Beta 1 очень похожа на эту задачу. После некоторого обсуждения, учитывая, что раунд 1 на CF был очень давно, наша задача существенно проще, а хорошо подготовленной, достаточно простой замены у нас не было, мы решили оставить эту задачу в раунде.

B. Смертный бой

Посчитаем количество единиц здоровья, которое i-й персонаж до своей гибели может снять боссу в одиночку: p_i = a_i·⌈ h_i / A⌉. После этого отсортируем персонажей по невозрастанию p_i и будем посылать их к боссу по одному в этом порядке, пока он не будет убит.

C. Слегка палиндромные числа

Научимся считать количество слегка палиндромных чисел среди первых n натуральных чисел. Чтобы получить количество таких чисел на отрезке с l по r, нужно посчитать их количество среди первых r и l - 1 натуральных чисел и вычесть одно из другого.

Все числа от 1 до 9 слегка палиндромные, поэтому если n ≤ 9, то ответ равен n. В противном случае прибавим к ответу 9 и посчитаем количество слегка палиндромных чисел на отрезке с 10 по n. Рассмотрим десятку чисел от 10k до 10k + 9, где k ≠ 0. Среди них ровно одно слегка палиндромное, так как последняя цифра должна равняться первой цифре k. Таким образом, есть по одному слегка палиндромному числу на отрезках от 10 до 19, от 20 до 29, и так далее.

Пусть n = 10k + d, где 0 ≤ d ≤ 9. Тогда на отрезке от 10 до n находятся k слегка палиндромных чисел, если d не меньше первой цифры k (а она равна первой цифре n), и k - 1, если меньше.

D. Дерево и многочлены

Сформулируем ключевые идеи решения.

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

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

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

В запросах первого типа нужно добавить многочлен q(x) в каждую вершину поддерева v. Для этого просто оставим пометки, что это надо сделать: будем хранить в вершине v многочлен push1[v], при выполнении запроса первого типа прибавим многочлен q к многочлену push1[v].

Аналогично для запросов второго типа будем использовать многочлен push2[v], который для каждой вершины будет хранить сумму многочленов из запросов второго типа к этой вершине.

Пускай теперь sum1[u]  — сумма всех многочленов, которые нужно было учесть в вершине u в запросах первого типа.

Для вычисления sum1[u] выполним поиск в глубину от корня дерева, который будет поддерживать многочлен cur и прибавлять к многочлену cur значение push1[v] при посещении новой вершины v и вычитать его обратно при выходе из неё. Соответственно, находясь в вершине u присваиваем sum1[u] = cur.

Аналогично, обозначим как sum2[u]  — сумма всех многочленов, которые нужно было учесть в вершине u в запросах второго типа.

Для вычисления sum2[u] также поспользуемся обходом в глубину. Значение sum2[u] равно сумме значений sum2[v] для детей u и значения push2[u].

Получив многочлены sum1[u] и sum2[u] в каждой вершине, вычислим их значение от величины d[u] и сложим, результат и будет ответом.

Время работы решения — O(nk).

E. Красивый отчёт

Перед решением основной задачи решим следующую, пока слабо связанную с исходной, задачу: на вход даётся последовательность элементов (a₁, a₂, ..., a_n) и нужно посчитать число различных элементов в этой последовательности. Особенностью этой задачи будет то, что:

1. элементы можно считывать только последовательно и только один раз: после считывания элемента a_i последует считывание a_i + 1, вернуться к a_i будет нельзя;
2. вы не можете использовать больше O(1) дополнительной памяти.

Чтобы подойти к решению этой подзадачи, вспомним, что математическое ожидание минимума из m равномерно распределённых на отрезке [0;1] случайных величин равно 1 / (m + 1). Например, если вы возьмёте четыре случайных числа из отрезка [0;1], то минимальное из этих чисел в среднем будет равно 0, 2.

Возьмём хеш-функцию h: A → [0;1], отображающую элементы a_i в числа на отрезке [0;1]. Посчитаем значение M = min {h(a₁), h(a₂), ..., h(a_n)}. В качестве ответа на задачу вернём 1 / M - 1. Проблемой этого решения является то, что нам может «не повезти» и, например, h(a_i) окажется очень маленьким, что окажет существенное влияние на ответ. Чтобы сгладить эту проблему, повторим описанный процесс несколько раз для различных хеш-функций h₁, h₂, ..., h_k для некоторого фиксированного k и усредним полученные результаты.

Вернёмся к нашей задаче поиска числа достижимых вершин. Рассмотрим сначала случай ацикличного графа. Ациклический граф отличается от графа с циклами, в том числе, тем, что у него существует топологическая сортировка: такой порядок следования вершин, при котором рёбра графа идут только от вершин, стоящих в порядке позже к вершинам, стоящим в порядке раньше. Существование топологической сортировки позволит для графа, в котором в каждой вершине записано случайное число из отрезка [0;1] посчитать, какое минимальное число достижимо из каждой вершины. Это можно сделать с помощью динамического программирования: рассматривание вершин в порядке топологической сортировки позволит посчитать значение для текущей вершины на основе уже посчитанных достижимых из неё. Посчитав минимальное достижимое число M_i из каждой вершины, можно указать в качестве ответа для данной вершины 1 / M_i - 1. Описанное требуется повторить несколько раз и усреднить результаты.

Однако, в данной задаче в графе могут быть циклы. Чтобы решить эту проблему, построим конденсацию графа. В полученном ацикличном графе в каждой вершине находится, на самом деле, несколько вершин начального графа. Для всех этих вершин ответ будет один и тот же. Отличие в подсчёте ответа будет заключаться в том, что в вершину пишется не случайное число из [0;1], а минимум из w_i случайных чисел из [0;1], где w_i — число вершин начального графа, содержащихся в i-й вершине сконденсированного.

Более подробно с методом решения этой и некоторых других подобных задач любопытный читатель может ознакомиться в статье "Size-Estimation Framework with Applications to Transitive Closure and Reachability", доступной по адресу http://cohenwang.com/edith/Papers/tcest.pdf.