Hello everyone! I don't have a strong foundation in fundamental algorithms and would like to talk/consult about a problem. The problem is taken from the EDU tab (ITMO Academy: pilot course) https://mirror.codeforces.com/edu/course/2/lesson/9/3/practice/contest/307094/problem/D
Let’s introduce additional notation. Suppose there are $$$D$$$ distinct types of clothing (in this problem $$$D = 4$$$), and each type $$$t$$$ corresponds to an array $$$a_t$$$ with $$$O(n)$$$ elements. Assume all clothing arrays are already sorted.
It's interesting to know, what asymptotic complexity (relative to $$$D$$$) can be achieved for this problem?
Proposed solution: In every clothing set, there is one element (cap/shirt/pants/...) with the minimal numerical value. Let’s iterate over each of the $$$D$$$ clothing types as the one contributing the minimal value in the set and select the best option.
To clarify, the $$$q$$$-th type of clothing is considered the minimal in the set $$$\text{ }$$$ { $$$a_1[i_1], a_2[i_2], ... a_D[i_D]$$$ }, $$$\text{ }$$$ if: $$$\text{ }$$$ $$$\forall k$$$ $$$\text{ }$$$ $$$a_q[i_q] \le a_k[i_k] $$$. $$$\text{ }$$$ For a fixed $$$q$$$, the best set can be found in a single pass over all $$$nD$$$ elements using a method similar to the two-pointer technique.
By iterating over all $$$q$$$, the total complexity becomes: $$$O(n\cdot D^2)$$$.
~ Sorry for machine translation
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!