Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
⌊|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$