Разбор Codeforces Round #323

Revision ru1, by danilka.pro, 2015-10-04 17:21:49

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

Let's fix s for every (l, s) pair. One could easily prove, that if subarray contains ai element, than ai must be greater-or-equal than aj for every j such that . Let's use this idea and fix g = gcd(n, s) (it must be a divisor of n). To check if ai can be in subarray with such constraints, let's for every 0 ≤ r < g calculate

.

It's true that every good subarray must consist of and only of . For finding all such subarrays we will use two pointers approach and for every good ai, such that is not good we will find aj such that are good and is not good. Let has k elements . Any it's subarray is superior, so it gives us arrays of length 1, 2, ..., k with count k, k - 1, ..., 1. As soon as sum of all k is not greater than n, we could just increase counts straightforward. There's a case when all ai are good, in which we must do another increases. Next we must add to the answer only counts of length x, such that gcd(x, n) = g.

Solution described above has complexity O(d(n)n), where d(n) is the number of divisors of n.

Jury's solution: 13390645

Ddiv1

It is a common fact that for a prime p and integer n maximum α, such that pα|n! is calculated as , where pw ≤ n < pw + 1. As soon as , the maximum α for is calculated as .

One could see, that if we consider numbers n, k and n - k in p-th based numeric system, rounded-down division by px means dropping last x digits of its p-th based representation. As soon as k + (n - k) = n, every i-th summand in α corresponds to carry in adding k to n - k in p-th numeric system from i - 1-th to i-th digit position and is to be 0 or 1.

First, let convert A given in statement from 10 to p-th numeric system. In case, if α is greater than number of digits in A in p-th numeric system, the answer is 0. Next we will calculate dynamic programming on A p-th based representation.

dp[i][x][e][r] — the answer for prefix of length i possible equal to prefix of A representation (indicator e), x-th power of p was already calculated, and there must be carry equal to r from current to previous position. One could calculate it by bruteforcing all of p2 variants of placing i-th digits in n and k according to r and e and i-th digit of A, and make a translation to next state. It can be avoided by noticing that the number of variants of placing digits is always a sum of arithmetic progression and can be calculated in O(1).

It's highly recommended to examine jury's solution with complexity O(|A|2 + |A|min(|A|, α)).

Jury's solution: 13390698

Ediv1

One could prove that the number of binary functions on 4 variables is equal to 224, and can be coded by storing a 24-bit binary mask, in which every bit is storing function value for corresponding variable set. It is true, that if maskf and maskg are correspond to functions f(A, B, C, D) and g(A, B, C, D), then function (f&g)(A, B, C, D) corresponds to maskf&maskg bitmask.

Now, we could parse expression given input into binary tree. I should notice that the number of non-list nodes of such tree is about . Now, let's calculate dynamic programming on every vertex vdp[v][mask] is the number of ways to place symbols in expression in the way that subtree of vertex v will correspond to function representing by mask. For list nodes such dynamic is calculated pretty straightforward by considering all possible mask values and matching it with the variable. One could easily recalculate it for one node using calculated answers for left and right subtree in 416 operations: dp[v][lmask|rmask] +  = dp[l][lmask] * dp[r][rmask].

But all the task is how to make it faster. One could calculate s[mask], where s[mask] is equal to sum of all its submasks (the masks containing 1-bits only in positions where mask contains 1-bits) in 24·224 operations using following code:

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];

Let's calculate sl[mask] and sr[mask] for dp[l][mask] and dp[r][mask] respectively. If we will find s[mask] = sl[mask] * sr[mask], s[mask] will contain multiplications of values of pairs of masks from left and right dp's, which are submasks of mask. As soon as we need pairs, which in bitwise OR will give us exactly mask, we should exclude pairs, which in bitwise OR gives a submask of mask, not equal to mask. This gives us exclusion-inclusion principle idea. The formula of this will be

, where p is the parity of number of bits in mask^submask.

Such sum could be calculated with approach above, but subtracting instead of adding

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];

In such way we will recalculate dynamic for one vertex in about 3·24·216 operations.

Jury's solution: 13390713

History

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