Leetcode. 2221. Треугольная сумма массива. Казалось бы, при чём здесь Паскаль?
В общем-то, задача не особо сложная, в комментариях куча выпускников видеокурсов, закодивших решение "в лоб" на своём любимом Питончике, удивляются, почему у неё уровень Medium, а не Easy. Сложность, как обычно, заключается в том, чтобы сделать качественно: чтобы тесты проходили за единицы миллисекунд, а не за 700 (C++) или 1200 (Питончик).
Есть массив десятичных цифр 'a'. Суммируем попарно все цифры: a[0] + a[1], a[1] + a[2] и т.д., и берём каждую сумму по модулю 10. Получается новый массив десятичных цифр на единицу меньшей размерности. Повторяем процедуру, пока не остаётся одна цифра. Она - и есть ответ.
Здесь - подробности, картинки, граничные условия и тест кейсы: https://leetcode.com/problems/find-triangular-sum-of-an-array/
Кто сказал "рекурсия"? А, это нейросеть. Ладно, что с неё возьмёшь, она же думать не умеет...
В общем-то, если посмотреть, сколько раз каждая исходная цифра входит в итоговую сумму, то можно заметить закономерность:
длина массива веса элементов в итоговой сумме
1 1
2 1 1
3 1 2 1
4 1 3 3 1
5 1 4 6 4 1
... Нам нужна строка № n-1 треугольника Паскаля, где n - длина исходного массива, и тогда ответом будет скалярное произведение по модулю 10 этой строки и массива, рассматриваемых как векторы. Проблемка только одна: n принимает значения до 500, а как известно, точное представление максимального биномиального коэффициента в этом ряду C(500; 250) требует очень много бит. Много бит - много вычислений, и вот мы уже почти в топе, но с другой стороны (где времена максимальные). Вычислять же биномиальные коэффициенты классической формулой
C(n; k) = C(n; k - 1) * (n - k + 1) / k но по модулю 10 мы не можем, т. к. делимое в этой операции требуется полностью. Но зато нам и весь коэффициент не нужен, а хватит его последней циферки.
Естественно, существуют и другие варианты:
Тупо просуммировать числа 500*499/2 ~ 125000 раз и столько же раз взять остатки от деления. Это неспортивно, и такими решениями заполнен диапазон от 170 до 700 мс в разделе C++ (в других не смотрел, но говорят, Чарльз Бэббидж на своём арифмометре считает быстрее тех решений).
Можно брать остаток не каждый раз, а где-то по достижении суммой значения 2⁶³, сэкономив на тяжёлых делениях. Но плохая асимптотика никуда не денется. Да и ещё неизвестно, что хуже, деление или if для его обхода.
Один лихой решатель просуммировал динамическим программированием не сами числа, а треугольник Паскаля по модулю 10, и потом сосчитал скалярное произведение. Так себе затея, как по мне, но 20 мс выжать у него получилось.
В общем, эти способы не подходят, если мы хотим достичь заветных 7 мс (быстрее пока реализовать не смогли даже по Лукасу с табличками заранее посчитанных остатков и малых комбинаций). Нужно нормальное решение.
Этот код
class Solution {
public:
int triangularSum(vector<int>& nums) noexcept {
ios::sync_with_stdio(false);
cin.tie();
constexpr auto ten = 10;
const auto first = &nums[0];
const auto end = &nums[1];
auto last = &nums[nums.size()];
auto count = 0;
while (last != end) {
for (auto prev = first, next = end; next != last; ++prev, ++next) {
*prev += *next;
}
if (!(++count % 27)) {
for (auto begin = first; begin != last; ++begin) {
*begin %= ten;
}
}
--last;
}
return nums[0] % ten;
}
}; у меня показал такой результат
В 4 раза хуже ожидаемого результата, но вполне терпимо.
Я тоже за предварительные расчеты, в любом виде.
Чисто практически, либо это счастье нужно нам 1 раз, и тогда мы можем подождать 700 мс, или оно нам нужно кучу раз, и тогда нет ничего плохого в том, чтобы посчитать все заранее.
Так на c++ просто делаем предподсчет шаблонами на этапе компиляции, и всё
Если вы хотите достичь оптимального времени выполнения, следуя описанным требованиям, то можно использовать следующий алгоритм:
1. Вычислить строку n-1 треугольника Паскаля по модулю 10.
2. Вычислить скалярное произведение полученной строки и исходного массива по модулю 10.
Для оптимизации этого процесса, вы можете использовать следующий метод для вычисления строки треугольника Паскаля по модулю 10:
def pascal_row_mod10(n):
row = [1]
for k in range(n):
row.append((row[-1] * (n - k)) // (k + 1) % 10)
return row[:n//2+1] + row[:n//2][::-1] Это функция вычисляет строку треугольника Паскаля с помощью сочетаний (C(n, k), где n - номер строки, а k - номер элемента в строке) и использует свойство, что строка треугольника Паскаля является симметричной (первая половина строки равна второй половине строки в обратном порядке).
Затем вы можете вычислить скалярное произведение:
def dot_mod10(a, b):
return sum(x*y for x, y in zip(a, b)) % 10 Итоговая функция, которую вы можете использовать, будет выглядеть следующим образом:
def triangular_sum(array):
n = len(array)
pascal_row = pascal_row_mod10(n)
return dot_mod10(array, pascal_row) Этот алгоритм выполняет вычисления быстро и эффективно для больших значений n, и он должен быть эффективным для n до 500.