Розбір

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

Блок 1

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

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

Блок 2

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

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

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

Блок 3

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

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

Блок 4

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

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

Блок 5

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

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

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

Якщо ж ці дві умови виконуються, необхідно розподілити $(r - 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}$ позначає кількість способів обрати $k$ предметів з $n$ . Ці значення можна підрахувати за $O (n^{2})$ за допомогою рекурентної формули $C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k}$ перед підрахунком основної динаміки. Після підрахунку усіх значень динамічного програмування, відповіддю на задачу буде значення dp[1][n].

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

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

Блок 6

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

База динаміки — dp[1][1] = 1. Подивимось, як можна підрахувати значення динаміки dp[r][x] при $r > 1$ . Не обмежуючи загальності будемо вважати, що $c_{r} =$ «<». Оскільки повинно виконуватись відношення $a_{r - 1} < a_{r}$ , можемо перебрати, чому дорівнює $a_{r - 1} = y = 1 \dots x - 1$ . Отримуємо, що $d p [r] [x] = y = 1 \sum x - 1 d p [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]$ . Використовуючи цю формулу, можна підрахувати усі значення динаміки за $O (n^{2})$ . Після підрахунку усіх значень динамічного програмування, відповіддю на задачу буде $i = 1 \sum n d p [n] [i]$ .

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

Блок 7

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

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

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

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

Спробуємо оцінити складність описаного розв'язку. Для цього необхідно оцінити сумарну кількість операцій $C$ наступного псевдокоду, де $g [v]$ — список усіх вершин $t o$ таких, що $p [t o] = 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)$ (кількість ребер дерева), перші два цикли сумарно виконаються за $O (n)$ . Тому загальну кількість операцій $C$ , на перший погляд, можна оцінити як $O (n^{3})$ , оскільки $sz [v]$ та $sz [t o]$ завжди не більші $n$ .

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

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

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