Problem: [problem:2155F]↵
↵
For this problem, it turns out that if you just iterate over the colors in the smaller of the two sets $C_u$ and $C_v$ (and also de-dupe queries), total complexity is bounded by something like $s \sqrt {q}$. More generally, let's say we have an array $a_i$ such that $\sum a_i = s$. If we pick $q$ distinct pairs of indices $x_i \leq y_i$, then it turns out that over all possible choices, $\sum \min(a_{x_i}, a_{y_i})$ is bounded by $s \sqrt {q}$, and e. Equality is achieved when $a$ has $\sqrt{q}$ values equal to $\frac{s}{\sqrt{q}}$, and all other values equal to $0$.↵
↵
Are there any other problems that use this very interesting bound?
↵
For this problem, it turns out that if you just iterate over the colors in the smaller of the two sets $C_u$ and $C_v$ (and also de-dupe queries), total complexity is bounded by something like $s \sqrt {q}$. More generally, let's say we have an array $a_i$ such that $\sum a_i = s$. If we pick $q$ distinct pairs of indices $x_i \leq y_i$, then it turns out that over all possible choices, $\sum \min(a_{x_i}, a_{y_i})$ is bounded by $s \sqrt {q}$
↵
Are there any other problems that use this very interesting bound?
