Всем привет! У меня нет особой базы в фундаментальных алгоритмах и хотел бы посоветоваться по поводу задачи. Задача взята из вкладки 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{ }$$$ $$$\forall k$$$ $$$\text{ }$$$ $$$a_q[i_q] \le a_k[i_k] $$$. $$$\text{ }$$$ Для фиксированного $$$q$$$ лучший комплект можно найти за один проход по всем $$$nD$$$ данным по аналогии с методом двух указателей.

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