snippetMinor
Parition a multiset of numbers into two subsets, how to maximize the sum of their medians?
Viewed 0 times
sumthemediansmultisetintonumberssubsetsparitiontwomaximize
Problem
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
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#148514, answer score: 4
Revisions (0)
No revisions yet.