Efficient way to verify if pair of numbers are medians of partition of sets Given a multi-set of multi-sets $\mathcal{S} = \{S_1, \ldots,S_i, \ldots, S_n \}, S_i \subset \mathbb{R}$. Denote powerset of $\mathcal{S}$ as $\mathbb{P}(\mathcal{S})$.
My question is, given a pair $(x, y) \in \mathbb{R}^2$, how can one efficiently verify $\exists P \in \mathbb{P}(\mathcal{S})$ such that, $\textbf{median}(\cup_{I \in P} I) = x$ and $\textbf{median}(\cup_{J \in \mathcal{S} \setminus P} J) = y$ ?
 A: I don't have time write now to write this up fully, but here's the idea in brief. I'll come back later to try to refine it.
Try "picking" ahead of time which element(s) will be the median. Let's ignore the case where x = (x1+x2)/2. Just assume that x is drawn from some element in one of the sets. Fix that, and fix the one that y comes from. (We'll try all n^2 of these possibilites.)
Now each set basically just becomes four numbers: how many numbers are more than x, and how many are less than x? how many are more than y, how many are less than y?
You want to do a subset sum kinda deal on both of these numbers at once. Where the sets in P have equal numbers > and < x, and the sets outside P have equal numbers > and < y. You can solve regular subset sum (in unary) with a dynamic programming approach, where you tall up all the possible sums. Here you need to do it in x and y at once, so you make a 2D grid for your dynamic programming, which makes it take O(n^2) time to evaluate for one particular one. Since we did it for all pairs, it's O(n^4) overall.
Then you gotta take into account the case where it's possible that x is an average of two elements. But you can use pretty much the same idea. You get at most O(n^4) ways to do it, so then O(n^6) overall.
I think if you're slightly smarter about counting you can show it's actually at most O(n^5) possible pairs, but I'm not sure.
You also have to be careful about how to properly handle counting elements that are equal to x, or y, in your counting, but that's what we get by 'fixing' which element is actually $x$. In short: if $x=2$, take all the $2$'s in your sets and add a tag, like $2$, $2'$, $2''$, etc. These sort by tag, so we count $2' > 2$. But then we try solving for when $x=2$, or $x=2'$, and so on.
