4
$\begingroup$

Given a multiset $S$ of numbers, partition it into two subsets $S_1 $ and $S_2$. How to maximize the sum of their medians? For example, the median of {1,2} is 1.5.

I've found a greedy algorithm that $S_1$ contains the maximum of $S$ (if multiple, select one), $S_2$ contains the rest of $S$. It's intuitively correct but I can't prove it.

$\endgroup$

1 Answer 1

4
$\begingroup$

Your algorithm is correct. The following is its proof of correctness.

Let $S_1$ and $S_2$ be the optimal partitions of $S$. Let their medians be $m_1$ and $m_2$. Let the maximum element is $M$ that belongs to $S_1$ (without loss of generality). Let $m$ is the median of $S_1 \cup S_2 \setminus \{M\}$. Then, we can show that the value $M + m$ is at least $m_1+m_2$.

Proof: When we merge the sets: $S_1 \setminus \{M\}$ and $S_2$. Then, in $S_1 \cup S_2 \setminus \{M\}$, there are at least $\lfloor |S_1|/2 \rfloor + \lfloor |S_2|/2 \rfloor-1$ elements that are larger than $\min\{m_1,m_2\}$. Suppose there are at least $\lfloor |S_1|/2 \rfloor + \lfloor |S_2|/2 \rfloor$ elements larger than $\min\{m_1,m_2\}$; then, we are done. That is, $\lfloor |S_1|/2 \rfloor + \lfloor |S_2|/2 \rfloor \geq \lfloor (|S_1|+|S_2|-1)/2 \rfloor$, the median $m$ of $S_1 \cup S_2 \setminus \{M \}$ has value at least $\min\{m_1,m_2\}$. Since $M \geq \max\{m_1,m_2\}$. We get $m+M \geq m_1 + m_2$. Hence proved.

Therefore, let us assume that there are exactly $\lfloor |S_2|/2 \rfloor + \lfloor |S_2|/2 \rfloor-1$ elements that are larger than $\min\{m_1,m_2\}$. Let us make some cases:

Case 1: $|S_1|$ and $|S_2|$ are odd. In this case, there are always $\lfloor |S_2|/2 \rfloor + \lfloor |S_2|/2 \rfloor$ elements with value larger than $\min\{m_1,m_2\}$. So we are done.

Case 2: $|S_1|$ and $|S_2|$ are even. Let $m_1 = \frac{(l_1+r_1)}{2}$ and $m_2 = \frac{(l_2+r_2)}{2}$ such that $l_1,r_1$ are middle elements of $S_1$, and $l_2,r_2$ are middle elements of $S_2$. Note that in $S_1 \cup S_2 \setminus \{M\}$, there are at least $\lfloor |S_1|/2 \rfloor + \lfloor |S_2|/2 \rfloor$ elements larger than $\min\{l_1,l_2\}$. Therefore, observe that the median $m$ is at least $\max\{l_1,l_2\}$ or $\min\{r_1,r_2\}$. Since $M \geq \max\{r_1,r_2\}$, it is easy to see that $m+M$ is at least $\frac{(l_1+r_1)}{2} + \frac{(l_2+r_2)}{2} = m_1 + m_2$. Hence proved.

Case 3: $|S_1|$ is odd and $|S_2|$ is even. Let $m_2 = \frac{(l_2+r_2)}{2}$ such that $l_2,r_2$ are middle elements of $S_2$. Note that the median of $S_1 \cup S_2 \setminus \{M\}$ is either at least $m_1$ or $\frac{(l_2+r_2)}{2}$ or $\frac{(l_2+m_1)}{2}$. Since $M \geq \max\{m_1,l_2,r_2\}$, it is easy to see that $m+M$ is at least $m_1+m_2$ for each of the possible values of $m$. Hence proved.

Case 4: $|S_1|$ is even and $|S_2|$ is odd. It is similar to Case 3.

$\endgroup$
8
  • $\begingroup$ You said ⌊|S1|/2⌋+⌊|S2|/2⌋≥⌊(|S1|+|S2|−1)/2⌋, however you forget that M >= min(m1, m2), so the inference m >= min(m1, m2) is wrong. An example S1=[-1,100,500]; S2=[1,200]. Though you assume S1 and S2 are the the optimal partition, this condition is not used. $\endgroup$
    – Voyager
    Jan 20, 2022 at 8:11
  • $\begingroup$ @Voyager For even sized array, how are you defining the median? $\endgroup$ Jan 20, 2022 at 10:22
  • $\begingroup$ As same as median wikipedia page $\endgroup$
    – Voyager
    Jan 20, 2022 at 10:25
  • $\begingroup$ @Voyager True. I will fix my answer. Else, I will delete it. Thanks for pointing out the mistake. I wrote the proof thinking of odd-sized subsets $S_1$ and $S_2$. $\endgroup$ Jan 20, 2022 at 11:01
  • 1
    $\begingroup$ The solution to the problem of maximising the median looks so obvious, and then turns out to be really hard… Thanks for that answer. Rare to find a problem that looks that obvious intuitively and is that hard. $\endgroup$
    – gnasher729
    Jan 20, 2022 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.