Всем привет! У меня нет особой базы в фундаментальных алгоритмах и хотел бы посоветоваться по поводу задачи. Задача взята из вкладки 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)$$$
Here is a O(n*D*(log(n)+log(D))) solution:
Start like you did : pick minimum of each D clothing types, and store each clothing item in a priority queue. Then store them into a minimum prioirty queue(M), while also storing the maximum value(max) seperately.
While you still have clothing items available:
1) Get the current style value by taking max-min(M) and update if lesser than current value
2) pop minimum value of off M. gets value and types of clothing
3) get next item in the same type of clothing as M if it exists, else you are done.
4) check if it is greater than max if so update max.
5) place new element in M.
Doing this will correctly calculating minimum difference. While taking nd log n to put all elements in correct priority queue initially and nd log d to handle logic of M.
Amazing! Such a beautiful solution. When I was thinking, I kept iterating through one certain type of clothing and avoided "parallel" iterating.
Your solution clarified everything perfectly! Thank so much!