Задача 1

Дано корневое дерево и число $$$k$$$. Для каждой вершины $$$u$$$ найти кол-во вершин в поддереве вершины $$$u$$$ отдаленных от $$$u$$$ на расстояние не более $$$k$$$ рёбер.

Рассмотрим решение за $$$O(N)$$$. При этом возникнет забавная структура — RQ на stack-е с запросами $$$O(1)$$$ (по сути префикс-сумма).

Всем привет! У меня нет особой базы в фундаментальных алгоритмах и хотел бы посоветоваться по поводу задачи. Задача взята из вкладки EDU (ITMO Academy: пилотный курс) https://codeforces.me/edu/course/2/lesson/9/3/practice/contest/307094/problem/D

Давайте введем дополнительные обозначения. Пусть всего будет $$$D$$$ различных типов одежды (в текущей задаче $$$D = 4$$$), и каждому типу $$$t$$$ соответствует массив $$$a_t$$$ с $$$O(n)$$$ элементами. Также, пусть массивы одежды будут уже отсортированы.

Хочется узнать, какой лучшей асимптотики относительно $$$D$$$ можно добиться?

Вариант решения. В каждом комплекте одежде есть какой-то элемент (кепка/майка/штаны/...) с минимальным числовым значением. Давайте переберем каждый из $$$D$$$ типов одежды в роли минимального в комплекте и возьмем лучший вариант.

Уточним, $$$q$$$-ый тип одежды является минимальным в комплекте $$$\text{ }$$$ { $$$a_1[i_1], a_2[i_2], ... a_D[i_D]$$$ }, $$$\text{ }$$$ если: $$$\text{ }$$$ $$$\forall k$$$ $$$\text{ }$$$ $$$a_q[i_q] \le a_k[i_k] $$$. $$$\text{ }$$$ Для фиксированного $$$q$$$ лучший комплект можно найти за один проход по всем $$$nD$$$ данным по аналогии с методом двух указателей.

Перебрав все $$$q$$$ получим сложность: $$$O(n\cdot D^2)$$$