Доброго времени суток.
Помогите разобраться с решением задачи (
https://www.hackerrank.com/contests/w17 ... s-building) с последнего contest'а на HackerRank.
Решение, которое я смог придумать имеет квадратичную сложность, и, в принципе, совпадает с авторским. Но в конце решения автора есть приписка, как улучшить время. И я никак не могу понять что имеется в виду.
Вот она:
Цитата:
... This gives us quadratic solution.
We can get faster solution after we note that we can omit minimum function and write the answer as the sum of max{S−1−D1(X)−DN(Y),0} over all the pairs of (X,Y) such that X and Y are nodes. For calculating this sum, we can just iterate though the nodes X in this sum and use sliding window and prefix sums to calculate the whole sum.
X и Y -- просто вершины в графа. Расстояния D1 и DN от первой и последней вершины до остальных предвычислены. S -- тоже есть.
Как избавиться от квадрата в сумме по всем парам с помощью prefix sum и sliding window?
Спасибо.
