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

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

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

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

Уточним, $$$q$$$-ый тип одежды является минимальным в комплекте если: $$$a_q[i_q] \le a_k[i_k] $$$ $$$(\forall k)$$$. Для фиксированного $$$q$$$ это делается за один проход по всем данным — $$$O(n \ cdot D)$$$.

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

Как я понял, Вы предлагаете перебирать $$$a_1$$$ и для каждого $$$a_1[i]$$$ найти "граничные" значения: $$$a_2[j] \le a_1[i] \le a_2[j+1]$$$ , $$$a_3[k] \le a_1[i] \le a_3[k+1]$$$, . . .

Затем рассмотреть все возможные варианты выбора границ для каждого $$$a_t$$$ ($$$t \gt 1$$$). Итого сложность: $$$O(n \cdot 2^{D-1} + n \cdot D)$$$ (второе слагаемое взялось так как мы перебрали все элементы во всех $$$D$$$ массивах).

Я не силён в переборах, возможно первый вариант можно тоже улучшить. И, довольно интересно, какой лучшей асимптотики относительно $$$D$$$ можно добиться.

P.s.: I plan to translate, but currently not familiar how make 2 language comment on codeforces