Для каждого друга смотрим, будет ли его высота больше h. Если да, то его ширина — 2, иначе — 1.
Complexity O(n).
677B - Ваня и кухонный комбайн
Решение, которое просто делает то, что описано в условии, не пройдет, т.к. если высота каждой картофелины будет 109, а скорость измельчения — 1, то на каждую картофелину будем тратить 109 операций.
С каждой новой картофелиной высотой ai будем измельчать картофель до высоты ai MOD k, тогда мы будем тратить на это a[i] / k секунд. Если мы не можем засунуть после этого новую картофелину, то мы потратим еще 1 секунду, иначе просто положим эту картофелину. Мы получим такой же ответ, как бы если мы делали то, что описано в условии.
Асимптотика O(n).
Переведем слово в 2-ичную систему счисления, это сделать легко, так как 64 — степень двойки. Проходимся по битах этого числа: если бит равен 0, то у нас может быть 3 различных варианта этого бита в нашей паре слов: 0&1, 1&0, 0&0, иначе только один вариант: 1&1. В таком случае результатом будет 3nullbits, где nullbits — количество нулевых битов.
Асимптотика O(|s| * 6).
Сделаем динамику dp[col][row], где dp[col][row] — минимальное время, которое нужно для того, чтобы открыть сундук в клетке (col, row). Для клеток цвета 1 dp[x][y] = x + y. Для каждого следующего цвета color будем перебирать все клетки цвета color - 1 и все клетки цвета color, тогда для каждой клетки цвета color с координатами (x1, y1) и клетки цвета color - 1 с координатами (x2, y2) dp[x1][y1] = dp[x2][y2] + abs(x1 - x2) + abs(y1 - y2).
Но этого решения будет недостаточно, так как его асимптотика — O(n2 * m2)
Можем сделать такое улучшение: пусть cnt[x] — количество клеток цвета x, тогда когда cnt[color] * cnt[color - 1] ≥ n * m, можно сделать поиск в ширину от клеток цвета color - 1 к клеткам цвета color.
В таком случае будет асимптотика O(n * m * sqrt(n * m)).
Для каждой клетки (x, y) в таблице возьмем максимально возможный крест, в котором не присутствуют нули. Чтобы сделать это быстро, сохраним массивы частичных сумм для всех возможных 8 направлений, где каждая клетка будет обозначать количество ненулевых шариков в каждом из направлений. Например для того, чтобы узнать, сколько ненулевых шариков находится справа от клетки (x, y), создадим массив p[x][y], в котором p[x][y] = p[x][y - 1] + 1 если a[x][y]! = 0 иначе p[x][y] = 0
Таким образом для каждой клетки (x, y) мы можем найти крест максимального размера, в котором не будет нулей.
Мы можем сравнить значения произведений для крестов в координатах (x, y) и с радиусом r, воспользовавшись логарифмированием. К примеру, если нам нужно сравнить кресты с значениями x1 * x2 * ... * xn и y1 * y2 * ... * ym, мы можем сравнить log(x1 * x2 * ... * xn) и log(y1 * y2 * ... * yn), что будет эквивалентно сравнению log(x1) + log(x2) + ... + log(xn) и log(y1) + log(y2) + ... + log(ym).
Таким образом для нахождения значения log(x1) + log(x2) + ... + log(xn) для каждого креста мы можем аналогично хранить массивы частичных сумм для каждого с направлений и для каждой клетки (x, y) искать максимальное значение креста с центром в ней за O(1).
Итоговая асимптотика O(n2).
