Topological Sorting of a Tree (Editorial)

Автор задачі:	Матвій Асландуков
Задачу підготував:	Матвій Асландуков
Розбір написав:	Матвій Асландуков

Блок 1

Оскільки усі числа від $1$ до $n$ повинні зустрічатися у масиві $a$ рівно один раз, існує всього $n!$ можливих варіантів записати числа у вершинах дерева. Усі їх можна перебрати та просто перевірити, що виконуються усі $(n - 1)$ (n - 1) необхідних умов. Складність такого розв'язку — $O (n \cdot n!)$ O(n \cdot n!).

Розв'язок — https://pastebin.com/M2VXx76u

Блок 2

Для розв'язання цієї групи можна було використати динамічне програмування по підмножинам. А саме, нехай dp[mask] — це кількість способів записати числа від $1$ до $m$ у вершинах дерева, номера яких присутні в масці mask. Тут $m$ позначає кількість одиничних бітів в масці $ma s k$ . При цьому враховуються тількі ті способи, для яких виконуються усі умови для тих вершин, що вже присутні в масці.

База такої динаміки — dp[0] = 1. Для того, щоб зробити перехід, необхідно перебрати вершину $v$ , в якій буде записано значення $(m + 1)$ (m + 1). Якщо для чергової вершини виконуються усі необхідні умови, необхідно зробити перехід dp[mask | (1 <.< v)] += dp[mask]. Після підрахунку усіх значень динаміки, відповіддю на задачу буде dp[(1 <.< n) - 1], що відповідає повній масці з усіми обраними вершинами. Складність такого розв'язку — $O (2^{n} n^{2})$ O(2^n n^2) чи $O (2^{n} n)$ O(2^n n) в залежності від реалізації.

Розв'язок — https://pastebin.com/tQYcGQwG

Блок 3

Нехай $s z_{v}$ sz_v — кількість вершин у піддереві вершини $v$ . Оскільки усі записані символи дорівнюють «<», то використовуючи транзитівність можна неважко довести, що значення у вершині повинно бути менше усіх значеннь вершин свого піддерева. Це означає, що значення $1$ обов'язково повинно бути записано у корені дерева. Усі інші значення від $2$ до $n$ можна незалежно розподілити по піддеревам кореня дерева. Це можна зробити $c n t_{v} = \frac{s z _{v} !}{\prod _{t o \in g_{v}} s z _{t o} !}$ cnt_v = \frac{sz_v!}{\prod_{to \in g_v} sz_{to}!} способами, де $g_{v}$ g_v — це список вершин $t o$ таких, що $p_{t o} = v$ p_{to} = v. Після того, як ми визначали які числа будуть присутніми у кожному піддереві першої вершини, можна незалежно розв'язати задачу для кожного такого піддерева. Саме тому відповідь на задачу дорівнює $v = 1 \prod c n t_{v}$ \prod\limits_{v=1} cnt_v. Складність такого розв'язку — $O (n)$ чи $O (n^{2})$ O(n^2) в залежності від реалізації.

Розв'язок — https://pastebin.com/xsv6URJ3

Блок 4

Оскільки в даній групі усі $p_{i} = 1$ p_i = 1, то усі некореневі вершини відрізняються між собою тільки символом $c_{v}$ c_v. Нехай $x$ — кількість ребер, на яких записано символ «>», а $y = (n - 1 - x)$ y = (n - 1 - x) — кількість ребер, на яких записано символ «<». Неважко побачити, що значення $a_{1}$ a_1 повинно дорівнювати $(x + 1)$ (x + 1). Більш того, усі значення від $1$ до $x$ можуть бути записані в будь-якому порядку в $x$ вершинах, на ребрах до яких написаний символ «>». Аналогічно усі значення від $(x + 2)$ (x + 2) до $n$ можуть бути записані в будь-якому порядку в $y$ вершинах, на ребрах до яких написаний символ «<». Тому відповідь на задачу дорівнює $x! y!$ та може бути підрахована за $O (n)$ .

Розв'язок — https://pastebin.com/apWgXHKH

Блок 5

У наступних двох групах для усіх вершин $v$ виконується рівність $p_{v} = (v - 1)$ p_v = (v - 1). Це означає, що дерево являє собою звичайний масив довжиною $n$ , а символи $c_{v}$ c_v задають результат порівняння кожної пари сусідніх елементів масиву.

Спробуємо розв'язати задачу методом динамічного програмування. Нехай dp[l][r] — кількість способів розставити $(r - l + 1)$ (r - l + 1) число на позиціях від $l$ до $r$ включно так, щоб виконувались усі необхідні відношення. База динаміки — dp[l][r] = 1 для усіх пустих підвідрізків ( $1 \leq l \leq n + 1, r = l - 1$ 1 \leq l \leq n + 1, r = l - 1). Для того щоб підрахувати значення dp[l][r] для $1 \leq l \leq r \leq n$ 1 \leq l \leq r \leq n, переберемо позицію $i = l \dots r$ i = l \ldots r, на якій буде знаходитися максимальне число серед елементів з $l$ по $r$ . Для такої позиції повинно виконуватися дві умови:

$i = l$ i = l або $c_{i} =$ c_i = «<». Дійсно, якщо ця умова не виконується, елемент на позиції ( $i - 1$ i - 1) буде більший ніж $a_{i}$ a_i, а тому $a_{i}$ a_i не може бути максимальним числом серед елементів з $l$ по $r$ .
$i = r$ i = r або $c_{i + 1} =$ c_{i + 1} = «>». Дійсно, якщо ця умова не виконується, елемент на позиції ( $i + 1$ i + 1) буде більший ніж $a_{i}$ a_i, а тому $a_{i}$ a_i не може бути максимальним числом серед елементів з $l$ по $r$ .

Якщо ж ці дві умови виконуються, необхідно розподілити $(r - l)$ (r - l) чисел що залишилися на дві половини, і незалежно розв'язати дві підзадачі на менших підвідрізках. Розподілити числа на дві половини можна $C_{r - l}^{i - l}$ C_{r - l}^{i - l} способами, а тому до значення dp[l][r] необхідно додати значення C[r - l][i - l] * dp[l][i - 1] * dp[i + 1][r]. Тут $C_{n}^{k}$ C_n^k позначає кількість способів обрати $k$ предметів з $n$ . Ці значення можна підрахувати за $O (n^{2})$ O(n^2) за допомогою рекурентної формули $C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k}$ C_n^k = C_{n-1}^{k-1} + C_{n-1}^{k} перед підрахунком основної динаміки. Після підрахунку усіх значень динамічного програмування, відповіддю на задачу буде значення dp[1][n].

Оскільки всього підвідрізків масиву $O (n^{2})$ O(n^2), та для кожного з них значення динаміки знаходиться за $O (n)$ , загальна складність такого розв'язку — $O (n^{3})$ O(n^3).

Розв'язок — https://pastebin.com/d9NsgVHA

Блок 6

Спробуємо розв'язати задачу за допомогою трохи іншої динаміки. Нехай dp[r][x] ( $1 \leq r \leq n, 1 \leq x \leq r$ 1 \leq r \leq n, 1 \leq x \leq r) — кількість способів розставити числа від $1$ до $r$ на перших $r$ елементах масиву так, щоб виконувалися усі необхідні відношення, і значення $a_{r}$ a_r дорівнювало $x$ .

База динаміки — dp[1][1] = 1. Подивимось, як можна підрахувати значення динаміки dp[r][x] при $r > 1$ r > 1. Не обмежуючи загальності будемо вважати, що $c_{r} =$ c_{r} = «<». Оскільки повинно виконуватись відношення $a_{r - 1} < a_{r}$ a_{r - 1} < a_r, можемо перебрати, чому дорівнює $a_{r - 1} = y = 1 \dots x - 1$ a_{r-1} = y = 1 \ldots x - 1. Отримуємо, що $d p [r] [x] = y = 1 \sum x - 1 d p [r - 1] [y]$ dp[r][x] = \sum\limits_{y=1}^{x - 1} dp[r - 1][y].

Можна побачити, що $y = 1 \sum x - 1 d p [r - 1] [y] = d p [r - 1] [x - 1] + y = 1 \sum x - 2 d p [r - 1] [y] = d p [r - 1] [x - 1] + d p [r] [x - 1]$ \sum\limits_{y=1}^{x-1} dp[r - 1][y] = dp[r - 1][x - 1] + \sum\limits_{y=1}^{x-2} dp[r - 1][y] = dp[r - 1][x - 1] + dp[r][x - 1]. Використовуючи цю формулу, можна підрахувати усі значення динаміки за $O (n^{2})$ O(n^2). Після підрахунку усіх значень динамічного програмування, відповіддю на задачу буде $i = 1 \sum n d p [n] [i]$ \sum\limits_{i=1}^n dp[n][i].

Розв'язок — https://pastebin.com/Pw84hhBM

Блок 7

Спробуємо модифікувати розв'язок, описаний у попередньому пункті, для довільного дерева. Нехай dp[v][x] ( $1 \leq v \leq n, 0 \leq x < s z_{v}$ 1 \leq v \leq n, 0 \leq x < sz_v) — кількість способів розставити числа від $1$ до $s z_{v}$ sz_v в усіх вершинах піддерева $v$ так, щоб виконувалися усі необхідні відношення, а також існувало рівно $x$ значень в піддереві $v$ менших за $a_{v}$ a_v (іншими словами, $a_{v} = x + 1$ a_v = x + 1).

Будемо рахувати $d p [v]$ ітеративно, на кожній ітерації додаючи до вершини $v$ його чергове піддерево $t o$ , та збільшуючи $s z_{v}$ sz_v на $s z_{t o}$ sz_{to}. База динаміки — dp[v][0] = 1, sz[v] = 1. Для того щоб додати чергове піддерво $t o$ та перейти у наступний шар динаміки, переберемо $x$ ( $0 \leq x < s z_{v}$ 0 \leq x < sz_v) — поточну кількість вершин менших за $a_{v}$ a_v та $c n t$ — кількість вершин у піддеріві $t o$ менших за $a_{v}$ a_v. Не обмежуючи загальності будемо вважати, що $c_{t o} =$ c_{to} = «>». Оскільки $a_{v}$ a_v повинно бути більше ніж $a_{t o}$ a_{to}, у піддереві $t o$ буде хоча б одна вершина менша ніж $a_{v}$ a_v, а тому $1 \leq c n t \leq s z_{t o}$ 1 \leq cnt \leq sz_{to}.

Тоді у новому шарі динаміки, кількість значень менших за $a_{v}$ a_v буде дорівнювати $(x + c n t)$ (x + cnt). Кількість способів розподілити ці $(x + c n t)$ (x + cnt) значень на вершини поточного піддерева та вершини піддерева $t o$ дорівнює $C_{x + c n t}^{x}$ C_{x + cnt}^x. У свою чергу, кількість значень більших за $a_{v}$ a_v дорівнює $(s z_{v} - 1 - x)$ (sz_v - 1 - x) у поточному піддереві та $(s z_{t o} - c n t)$ (sz_{to} - cnt) у піддереві вершини $t o$ . Загальна кількість значень більших за $a_{v}$ a_v дорівнює $(s z_{v} - 1 - x + s z_{t o} - c n t)$ (sz_v - 1 - x + sz_{to} - cnt), а тому кількість способів розподілити їх на два піддерева — $C_{s z_{v} - 1 - x + s z_{t o} - c n t}^{s z_{t o} - c n t}$ C_{sz_v - 1 - x + sz_{to} - cnt}^{sz_{to} - cnt}. Оскільки $a_{v} > a_{t o}$ a_v > a_{to} та існує рівно $c n t$ значень у піддереві $t o$ менших за $a_{v}$ a_v, то кількість значень у піддереві $t o$ менших за $a_{t o}$ a_{to} повинна не перевищувати $c n t - 1$ cnt - 1.

Тому можемо зробити перехід у наступний шар динаміки:

d p^{'} [v] [x + c n t] \t + = C_{x + c n t}^{x} C_{s z_{v} - 1 - x + s z_{t o} - c n t}^{s z_{t o} - c n t} y = 0 \sum c n t - 1 d p [t o] [y]

dp'[v][x + cnt] \;\t{+=}\; C_{x + cnt}^x C_{sz_v - 1 - x + sz_{to} - cnt}^{sz_{to} - cnt} \sum\limits_{y=0}^{cnt - 1} dp[to][y]

Суму $y = 0 \sum c n t - 1 d p [t o] [y]$ \sum\limits_{y=0}^{cnt - 1} dp[to][y] можна знаходити за $O (1)$ якщо підтримувати масив префіксних сум $s u m [v] [x] = y = 0 \sum x d p [v] [x]$ sum[v][x] = \sum\limits_{y=0}^{x} dp[v][x]. Цей масив можна дуже просто підтримувати за допомогою рекурентної формули $s u m [v] [x] = s u m [v] [x - 1] + d p [v] [x]$ sum[v][x] = sum[v][x - 1] + dp[v][x]. Саме тому кожен перехід динаміки можна робити за $O (1)$ .

Спробуємо оцінити складність описаного розв'язку. Для цього необхідно оцінити сумарну кількість операцій $C$ наступного псевдокоду, де $g [v]$ — список усіх вершин $t o$ таких, що $p [t o] = v$ p[to] = v:

for (int v = n; v >= 1; --v) {
    sz[v] = 1;
    for (int to : g[v]) {
        for (int x = 0; x < sz[v]; ++x) {
            for (int y = 0; y < sz[to]; ++y) {
                ++C;
            }
        }
        sz[v] += sz[to];
    }
}

Оскільки сумарний розмір усіх $g [v]$ дорівнює $(n - 1)$ (n - 1) (кількість ребер дерева), перші два цикли сумарно виконаються за $O (n)$ . Тому загальну кількість операцій $C$ , на перший погляд, можна оцінити як $O (n^{3})$ O(n^3), оскільки $sz [v]$ та $sz [t o]$ завжди не більші $n$ .

Але насправді $C$ можна оцінити як $O (n^{2})$ O(n^2). Дійсно, цикл по $x$ можна розглядити як перегляд усіх вершин з піддерева $v$ , що знаходяться лівіше піддерева $t o$ . Цикл по $y$ можна розглядати як перегляд усіх вершин з піддерева $t o$ . Неважко побачити, що у такому випадку кожна пара вершин $(x, y)$ буде розглядатися рівно один раз при $v = l c a (x, y)$ v = lca(x, y), оскільки при всіх більш високих вершинах $v$ , вершини $x$ та $y$ вже будуть знаходитися в одному піддереві. Тут $l c a (x, y)$ lca(x, y) позначає найменшого спільного предка вершин $x$ та $y$ . Оскільки загальна кількіста пар вершин $x$ , $y$ дорівнює $\frac{n ( n - 1 )}{2}$ \frac{n(n-1)}{2}, сумарну кількість операцій $C$ можна оцінити як $O (n^{2})$ O(n^2).

Розв'язок — https://pastebin.com/Za5MtZ99

Якщо написати цей розв'язок неефективно (наприклад перебирати $x$ не до поточного значення $sz [v]$ , а до загального розміру піддерева), то рішення буде працювати за $O (n^{3})$ O(n^3). Також за $O (n^{3})$ O(n^3) буде працювати рішення, що не використовує масив префіксних сум, а рахує суму окремим циклом. Саме через наявність таких рішень була зроблена сьома група тестів з обмеженнями $n \leq 200$ n \leq 200.