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