Codeforces Round #355 (Div. 2) Editorial

Revision ru2, by Wild_Hamster, 2016-06-01 21:48:47

677A - Vanya and Fence

Для каждого друга смотрим, будет ли его высота больше h. Если да, то его ширина — 2, иначе — 1.

Complexity O(n).

677B - Vanya and Food Processor

Решение, которое просто делает то, что описано в условии, не пройдет, т.к. если высота каждой картофелины будет 109, а скорость измельчения — 1, то на каждую картофелину будем тратить 109 операций.

С каждой новой картофелиной высотой ai будем измельчать картофель до высоты ai MOD k, тогда мы будем тратить на это a[i] / k секунд. Если мы не можем засунуть после этого новую картофелину, то мы потратим еще 1 секунду, иначе просто положим эту картофелину. Мы получим такой же ответ, как бы если мы делали то, что описано в условии.

Асимптотика O(n).

677C - Vanya and Label

Переведем слово в 2-ичную систему счисления, это сделать легко, так как 64 — степень двойки. Проходимся по битах этого числа: если бит равен 0, то у нас может быть 3 различных варианта этого бита в нашей паре слов: 0&1, 1&0, 0&0, иначе только один вариант: 1&1. В таком случае результатом будет 3nullbits, где nullbits — количество нулевых битов.

Асимптотика O(|s| * 6).

677D - Vanya and Treasure

Сделаем динамику 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)).

677E - Vanya and Balloons

Для каждой клетки (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).

Tags разбор, 355

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English Wild_Hamster 2016-06-01 22:49:36 111
ru6 Russian Wild_Hamster 2016-06-01 22:47:18 133
en8 English Wild_Hamster 2016-06-01 22:22:10 196
ru5 Russian Wild_Hamster 2016-06-01 22:20:00 194
ru4 Russian Wild_Hamster 2016-06-01 22:16:49 4042 Мелкая правка: 'oiler/spoiler
en7 English Wild_Hamster 2016-06-01 22:14:18 4026
ru3 Russian Wild_Hamster 2016-06-01 22:07:19 11918
en6 English Wild_Hamster 2016-06-01 22:03:29 11650
en5 English Wild_Hamster 2016-06-01 21:50:43 95
ru2 Russian Wild_Hamster 2016-06-01 21:48:47 11 Мелкая правка: 'высоты$a_i%k$, тогда ' -
en4 English Wild_Hamster 2016-06-01 21:47:02 4 Tiny change: 'till $a[i] MOD k$, so we ' -> 'till $a[i]$ $MOD$ $k$, so we '
en3 English Wild_Hamster 2016-06-01 21:44:36 10
ru1 Russian Wild_Hamster 2016-06-01 21:43:50 3370 Первая редакция перевода на Русский
en2 English Wild_Hamster 2016-06-01 21:40:41 97
en1 English Wild_Hamster 2016-06-01 21:39:09 3178 Initial revision (published)