Автор задачи и разработчик: Рябчун Владимир
Будем называть блоком одно слагаемое (которое может состоять из нескольких множителей) в данном выражении. За $$$L$$$ будем обозначать максимальную длину числа, $$$C$$$ будет равно $$$10$$$ (количество различных цифр).
Для решения первой подзадачи достаточно было аккуратно перебрать все пары позиций, где будет заменена цифра, и вычислить значение полученного выражения за линейное время. Асимптотика такого решения составляет $$$\mathcal{O}(L^2 C^2 n^3)$$$, что при достаточной аккуратности реализации укладывается в ограничения по времени.
Решение второй подзадачи требовало предпосчитать префиксные и суффиксные суммы значений блоков и префиксные и суффксные произведения внутри одного блока. Тогда, при изменении цифр в числах из разных блоков или изменении цифр в одном числе, данная информация позволяла вычислить значение выражения за $$$\mathcal{O}(1)$$$. В случае изменения цифр в двух различных числах внутри одного блока, для вычисления произведения чисел между ними предлагалось либо просто предпосчитать их, либо использовать алгоритм деления по модулю (который, однако, требовал дополнительного рассмотрения нулей). Итоговое решение с предпосчетом имеет асимптотику $$$\mathcal{O}(n^2 + n^2 L^2 C^2)$$$.
Для решения всех следующих подзадач выделим три принципиально различных случая:
Разбор первого случая можно реализовать таким способом: переберем число и вычислим, каким оно должно быть, чтобы получилось равенство. Для этого все блоки без этого числа перенесем в другую часть равенства, а потом поделим на оставшиеся в этом блоке. Если среди оставшихся есть $$$0$$$, то результат зависит от выражения справа (либо равенство уже есть, либо оно невозможно). Иначе сравним исходное число и проверим, правда ли что оно и результат отличаются не более чем в двух позициях. Это решение будет работать за $$$\mathcal{O}(n \log{\mathrm{MOD}})$$$ с вычислением обратного по модулю. В группах 4 – 6 этот случай рассматриваться не будет.
В третьей подзадаче ввиду малых ограничений на значения чисел, было возможно для каждого блока явно хранить количество цифр от $$$0$$$ до $$$9$$$. Более того, возможно за $$$\mathcal{O}(n C)$$$ предпосчитать всевозможные степени чисел от 1 до 9.
Для случаев 1 и 3 можно в каждом блоке перебрать пару цифр — старую и новую. Пользуясь предпосчитанными значениями для фиксированного изменения, проверить ответ за $$$\mathcal{O}(C)$$$, что даст итоговую асимптотику $$$\mathcal{O}(n C^3)$$$, хотя это можно сделать и несколько быстрее.
Случай 2 также не вызывает трудностей — для каждого блока будем помнить возможные изменения значения при замене одной цифры на другую. Для одного блока таких чисел будет не более $$$C^2$$$. Пройдем по блокам слева направо, в каждом блоке переберем изменение и проверим, если ли нужное второе изменение среди запомненных. Это будет работать за $$$\mathcal{O}(n C)$$$.
В четвертой подзадаче невозможен случай 3. Разберем случай 2. Для каждого числа переберём все возможные замены одной цифры на другую, для каждой такой замены вычислим, насколько изменится значение этого числа. Будем идти по сумме слева направо и перебирать изменение в данном числе. Тогда мы знаем, какое изменение должно внести второе число. Будем поддерживать множество возможных изменений значений и искать в нем нужное число и изменение. Сложность такого решения $$$\mathcal{O}(n L C)$$$.
Пятая подзадача гарантирует отсутствие случая 2. Опишем здесь способ решения, который будет также применяться в подзадачах 6 и 7.
Предположим, что были изменены числа $$$x$$$ и $$$y$$$ на $$$d_1$$$ и $$$d_2$$$ соответственно. Пусть $$$P$$$ — произведение блока, а $$$R$$$ — требуемое значение. Тогда необходимо, чтобы $$$(x + d_1)(y + d_2) \frac{P}{xy}$$$ было равно $$$R$$$. Случай нулевых $$$x$$$ или $$$y$$$ требует отдельного рассмотрения, но он не очень сложен — деление здесь на самом деле представляет собой исключение множителя из произведения, нужно аккуратно рассмотреть случаи одного, двух и более нулей в блоке.
Далее будем предполагать, что в блоке нет нулей. Тогда выражение можно преобразовать к виду $$$\left(1 + \frac{d_1}{x} + \frac{d_2}{y} + \frac{d_1}{x} \frac{d_2}{y}\right) = \frac{R}{P}$$$.
Но здесь $$$x$$$ и $$$y$$$ вместе с их изменениями никак не связанны, поэтому можно перебрать $$$y$$$ и $$$d_2$$$ и проверить, встречали ли мы раньше необходимые $$$x$$$ и $$$d_1$$$.
Данное решение будет работать за $$$\mathcal{O}(n L C)$$$.
Решения двух последних подгрупп представляют собой объединение прошлых решений. Для получения полного балла требуется аккуратная реализация — предпосчитать как можно больше делений по модулю, чтобы не вычислять их несколько раз, использовать unordered_map или более быстрые ассоциативные контейнеры и оптимизировать программу по объему используемой памяти и количеству реаллокаций.