Разбор Codeforces Round #323

Правка ru4, от danilka.pro, 2015-10-04 18:11:51

Adiv2

Для решения задачи будем хранить два массива hused[j] и vused[j] размера n, изначально заполненных false. Будем обрабатывать перекрестки в списке от 1-го к n-му, и если для i-го перекрестка оба значения hused[hi] и vused[vi] равны false , i-ый день нужно добавить к ответу и установить значения hused[hi] и vused[vi] в true, означающих, что hi-ая горизонтальная и vi-ая вертикальная теперь заасфальтирована, а в противном случае нужно просто пропустить очередной перекресток.

Такое решение работает за O(n2).

Авторское решение: 13390628

Bdiv2

Чтобы получить оптимальный ответ, роботу нужно двигаться от первого компьютера к последнему, затем от последнего к первому, потом опять от первого к последнему, и т.д., попутно собирая те части информации, которые он может собрать на момент нахождения рядом с компьютером. Таким образом робот будет по максимуму использовать ресурсы, затраченные на смену направления движения. Несмотря на наличие более быстрых решений, от участников требовалось лишь решение с асимптотикой O(n2).

Авторское решение: 13390612

Adiv1

Пусть ответ представляет собой массив a1 ≤ a2 ≤ ... ≤ an. Далее будем пользоваться тем, что gcd(ai, aj) ≤ amin(i, j).

Верно, что gcd(an, an) = an ≥ ai ≥ gcd(ai, aj) для любых 1 ≤ i, j ≤ n. Это значит, что an равен максимальному элементу таблицы. Запишем в ответ an максимальный ответ и удалим его из текущего набора элементов. После удаления gcd(an, an) в наборе будут содержаться gcd(ai, aj) для любых 1 ≤ i, j ≤ n, таких, что 1 ≤ min(i, j) ≤ n - 1.

Из последних двух неравенств следует, что gcd(ai, aj) ≤ amin(i, j) ≤ an - 1 = gcd(an - 1, an - 1). Поскольку в наборе содержится gcd(an - 1, an - 1), максимальный элемент в наборе равен an - 1. Поскольку an уже известен, удалим из набора gcd(an - 1, an - 1), gcd(an - 1, an), gcd(an, an - 1) . Теперь в наборе содержатся gcd(ai, aj), для любых 1 ≤ i, j ≤ n таких, что 1 ≤ min(i, j) ≤ n - 2.

Далее повторим это операцию для каждого k from n - 2 to 1, устанавливая ak равным максимальному элементу в оставшемся наборе и удаляя gcd(ak, ak), gcd(ai, ak), gcd(ak, ai) для всех k < i ≤ n из набора.

С помощью математической индукции нетрудно доказать корректность такого алгоритма. Чтобы быстро выполнять удаление и получение максимального элемента в наборе, можно использовать, например, структуры map или set, что позволит реализовать решение с асимптотикой .

Авторское решение: 13390679

Bdiv1

Можно посчитать матрицу размера n × n mt[i][j] — длина наибольшей неубывающей подпоследовательности в массиве a1, a2, ..., an, начинающейся с элемента, не меньшего ai и заканчивающейся непосредственно в элементе aj.

Теперь, если мы имеем две матрицы размера n × n A[i][j] (ответ для массива a1, a2, ..., apn начинающегося с элемента, не меньшего ai и заканчивающейся элементом aj в последнем блоке массива (a(p - 1)n + 1, ..., apn) и B[i][j] (ответ для массива a1, a2, ..., aqn ), то произведение этих матриц

даст подобную матрицу, но для массива из p + q блоков. Так как такое произведение матриц является ассоциативным, воспользуемся быстрым возведением матрицы в степень для подсчета M[i][j] (ответ для массива a1, a2, ..., anT) — матрица mt[i][j] в степени T. Ответ на задачу — максимум матрицы M. Такое решение имеет асимптотику .

Авторское решение (с матрицами): 13390660

Существует альтернативное решение. Так как a1, a2, ..., anT содержит максимум n различных элементов, любая его неубывающая подпоследовательность содержит максимум n - 1 последовательных возрастающих соседних элементов. Пользуясь этим фактом, будем считать стандартное динамическое программирование на первых n блоках массива (a1, ..., an2) и на n последних блоках массива (anT - n + 1, ..., anT). Все остальные блоки (а их T - 2n) между ними будут порождать равные элементы в результирующей неубывающей подпоследовательности.

Таким образом, для фиксированного ai, в котором заканчивается неубывающая подпоследовательность длины p массива из первых n блоков, и для фиксированного aj ≥ ai, в котором аналогичная подпоследовательность длины s на последних n блоках массива начинается, нужно обновить ответ величиной p + (T - 2n)count(ai) + s, где count(x) — количество вхождений x в массив a1, ..., an. Получаем решение за .

Авторское решение ( с динамикой): 13390666

Cdiv1

Зафиксируем s и рассмотрим каждую пару (l, s). Тогда, если превосходящий подмассива содержит ai, то ai должен быть не меньше каждого aj такого, что . Будем использовать этот факт и решать задачу для фиксированного g = gcd(n, s) (g|n). Для последующей проверки того, что ai может содержаться в превосходящем подмассиве, посчитаем для каждого 0 ≤ r < g

.

Каждый периодический подмассив состоит из и только из них. Для нахождения количества таких подмассивов будем пользоваться методом двух указателей и для каждого подходящего ai такого, что не является подходящим, найдем такое aj, что являются подходящими и не является подходящим. Пусть представляет подотрезок из k элементов, т.е. . Любой подотрезок этого подотрезка так же является превосходящим, поэтому к отрезкам длины 1, 2, ..., k мы должны прибавить k, k - 1, ..., 1 соответственно. Так как сумма всех k не превосходит n, можно циклом увеличивать нужные значения. Случай, когда все ai являются подходящими, нужно обрабатывать отдельно. После подсчета всех необходимых величин, мы должны добавить лишь те количества подотрезков длины x, для которых gcd(x, n) = g.

Описанное решение имеет асимптотику O(d(n)n), где d(n) — количество делителей n.

Авторское решение: 13390645

Ddiv1

Известно, что для простого p и натурального n максимальное α такое, что pα|n!, вычисляется по формуле , где pw ≤ n < pw + 1. Так как , максимальное α для вычисляется по формуле .

Примечательно, что если представить n, k и n - k в p-ичной системе счисления, деление числа с округлением вниз на px соответствует отбрасыванию последних x цифр в его p-ичном представлении. Поскольку k + (n - k) = n, i-ое слагаемое в формуле для α соответствует величине переноса разряда с i - 1-ой к i-ой цифре в сложении k и n - k в p-ичной системе счисления и может принимать значения ноль или один.

Переведем A в p-ичную систему счисления и будем далее работать только с этим его представлением. В случае, если α превышает количество цифр в представлении A то, как описано выше, ответ равен 0. Далее будем считать динамическое программирование на представлении числа A.

dp[i][x][e][r] — ответ, если мы рассмотрели первые i цифр числа n и k, при этом эти цифры в n могут равняться первым цифрам A (булева e), x-ая степень p уже была набрана, и величина переноса с текущего в следующий разряд равна r . Переходы будем осуществлять вперед, имея, таким образом, не более p2 вариантов расстановки цифр в n и k. Поскольку перебор всех таких вариантов невозможен, нужно заметить, что для перехода в фиксированное состояние (его первый параметр равен i + 1) количество вариантов расстановки цифр равняется сумме арифметической прогрессии, поэтому переход с помощью умножения на сумму прогрессии можно осуществлять за O(1).

Крайне рекомендуется ознакомиться с авторским решением за O(|A|2 + |A|min(|A|, α)).

Авторское решение: 13390698

Ediv1

Количество бинарных функций на 4 переменных равняется 224, и каждую из них можно закодировать двоичным числом из 24 бит , где значение каждого бита соответствует значению функций в наборе переменных, соответствующему номеру бита. Верно, что если maskf и maskg соответствуют функциям f(A, B, C, D) и g(A, B, C, D), то функции (f|g)(A, B, C, D) соответствует maskf|maskg bitmask.

Построим бинарное дерево разбора выражения. Замечу, что количество нелистовых вершин в нем равно . Будем считать динамическое программирование для каждой вершины v дерева разбора — dp[v][mask] равно количеству способов вставить символы в выражение, образованное поддеревом вершины v так, чтобы оно соответствовало функции, задающейся маской mask. Для листовых вершин значения динамики вычисляются ``в лоб'' перебором каждой из 16 функций и подстановкой переменной в функцию. Для нелистовых вершин существует способ перебирать все пары варинтов функций в сыновьях за 416: dp[v][lmask|rmask] +  = dp[l][lmask] * dp[r][rmask].

Однако вся задача в том, чтобы делать это быстрее. Давайте посчитаем s[mask], где s[mask] равняется сумме ответов динамики для всех подмасок mask (submask&mask = submask) за 24·224 операций с помощью следующего кода:

for (int mask = 0; mask < (1 << 16); ++mask) s[mask] = dp[x][mask];
for (int i = 0; i < 16; ++i)
    for (int mask = 0; mask < (1 << 16); ++mask)
        if (!(mask & (1 << i))) s[mask ^ (1 << i)] += s[mask];

Посчитаем sl[mask] и sr[mask] для dp[l][mask] и dp[r][mask] соответственно. Если приравнять s[mask] = sl[mask] * sr[mask], s[mask] будет хранить сумму произведений пар значений масок левого и правого сына, таких, что обе эти маски являются подмасками mask. Так как нам нужны пары, побитовый OR которых даст ровно mask, нужно исключить пары, побитовый OR которых дает подмаску mask, не равную mask. Для этого будем пользоваться формулой включений-исключений:

, где p равно количеству единичных бит в mask^submask.

Такую сумму можно посчитать аналогичному выше образом, но используя вычитание вместо сложения:

for (int mask = 0; mask < (1 << 16); ++mask) s[mask] = sl[mask] * sr[mask];
for (int i = 0; i < 16; ++i)
    for (int mask = 0; mask < (1 << 16); ++mask)
        if (!(mask & (1 << i))) s[mask ^ (1 << i)] -= s[mask];

Таким образом можно пересчитывать значения динамики в вершине за 3·24·216 операций.

Авторское решение: 13390713

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru6 Русский danilka.pro 2015-10-05 16:27:13 13
en38 Английский danilka.pro 2015-10-05 16:27:03 13
ru5 Русский danilka.pro 2015-10-05 16:25:24 4 Мелкая правка: 'C[i][j]=\min\limits_{k' -> 'C[i][j]=\max\limits_{k'
en37 Английский danilka.pro 2015-10-05 16:25:08 4 Tiny change: 'C[i][j]=\min\limits_{k' -> 'C[i][j]=\max\limits_{k'
ru4 Русский danilka.pro 2015-10-04 18:11:51 2795
ru3 Русский danilka.pro 2015-10-04 17:50:17 2316
ru2 Русский danilka.pro 2015-10-04 17:32:41 1720
en36 Английский danilka.pro 2015-10-04 17:22:08 0 (published)
ru1 Русский danilka.pro 2015-10-04 17:21:49 11138 Первая редакция перевода на Русский (сохранено в черновиках)
en35 Английский danilka.pro 2015-10-04 16:38:30 4 Tiny change: '\n$mn_r=\min\limits_{i' -> '\n$mn_r=\max\limits_{i'
en34 Английский danilka.pro 2015-10-04 00:34:59 54
en33 Английский danilka.pro 2015-10-03 23:46:45 12
en32 Английский danilka.pro 2015-10-03 23:38:05 38
en31 Английский danilka.pro 2015-10-03 23:36:33 389
en30 Английский danilka.pro 2015-10-03 23:26:56 1 Tiny change: ' \cdot sr[mask]$, wh' -> ' \cdot sr[smask]$, wh'
en29 Английский danilka.pro 2015-10-03 23:15:16 9 Tiny change: 'nts $i+k-1\equiv j \mod{n}). Any it's' -
en28 Английский danilka.pro 2015-10-03 22:12:48 0 (published)
en27 Английский danilka.pro 2015-10-03 22:12:15 107
en26 Английский danilka.pro 2015-10-03 22:10:24 5 Tiny change: 'bitmask.\n()&()\nNow, we ' -> 'bitmask.\n\nNow, we '
en25 Английский danilka.pro 2015-10-03 22:09:58 1 Tiny change: ' in $mask ^ submask$' -> ' in $mask \^ submask$'
en24 Английский danilka.pro 2015-10-03 22:09:28 3238
en23 Английский danilka.pro 2015-10-03 21:42:17 2 Tiny change: '~~\n\n\n\n' -> '~~\n\n\n\n\n'
en22 Английский danilka.pro 2015-10-03 21:39:38 595
en21 Английский danilka.pro 2015-10-03 21:32:22 48
en20 Английский danilka.pro 2015-10-03 21:31:26 2313
en19 Английский danilka.pro 2015-10-03 20:42:49 196
en18 Английский danilka.pro 2015-10-03 20:33:33 413
en17 Английский danilka.pro 2015-10-03 20:24:17 26 Tiny change: 'alpha = \left$\n\n' -> 'alpha = \lfloor \frac{n}{p} \rfloor$\n\n'
en16 Английский danilka.pro 2015-10-03 20:22:20 26
en15 Английский danilka.pro 2015-10-03 20:22:08 990
en14 Английский danilka.pro 2015-10-03 19:43:54 93
en13 Английский danilka.pro 2015-10-03 19:39:55 44
en12 Английский danilka.pro 2015-10-03 19:38:49 1441
en11 Английский danilka.pro 2015-10-03 19:16:11 1016
en10 Английский danilka.pro 2015-10-03 18:56:25 419
en9 Английский danilka.pro 2015-10-03 18:55:30 1 Tiny change: ' inductions. For perf' -> ' induction. For perf'
en8 Английский danilka.pro 2015-10-03 18:55:08 8 Tiny change: 'g maximum operation' -> 'g maximum element operation'
en7 Английский danilka.pro 2015-10-03 18:54:42 13 Tiny change: '< i \le n$.\n\nOne c' -> '< i \le n$ from the se.\n\nOne c'
en6 Английский danilka.pro 2015-10-03 18:54:27 24 Tiny change: 'a_k, a_i)$.\n\nOne ' -> 'a_k, a_i)$ for every $k < i \le n$.\n\nOne '
en5 Английский danilka.pro 2015-10-03 18:53:52 47
en4 Английский danilka.pro 2015-10-03 18:52:50 22
en3 Английский danilka.pro 2015-10-03 18:52:04 1329
en2 Английский danilka.pro 2015-10-03 18:51:34 38 Tiny change: 'herwise.\n\n' -> 'herwise.\nSuch solution has $O(n^2)$ complexity.\n'
en1 Английский danilka.pro 2015-10-03 18:49:46 494 Initial revision (saved to drafts)