When I slept soundly last night, a dream took me back to the times when I was taking my college entrance contest. I was given this problem:↵
↵
Let $n$ be a positive integer and $S$ be a multiset consisting of numbers from $\\{1, 2, ..., n\\}$. Integer $i\,(1 \leq i \leq n)$ appears $a_i \geq 0$ times in $S$. Also, I was given a positive integer $k$. A partition of $S$ into multisets, namely $\cup_{i=1}^t S_i$, is valid iff **all** of the following three conditions hold:↵
↵
(1) $\cup_{i=1}^t S_i = S$.↵
↵
(2) $\forall 1 \leq i< j \leq t,\,S_i \neq S_j$.↵
↵
(3) $\forall 1 \leq i\leq t$, the size of $S_i$ is less or equal than $k$, i.e., $|S_i| \leq k$.↵
↵
Find the minimum possible number of **distinct** multisets in the partition of $S$.↵
↵
For example, if $k=2$ and $S=\\{1, 1, 1, 2, 2, 2\\}$, the answer is $1$ because you can decompose $S$ into $3 \times \\{1, 2\\}$, so you should answer $1$ because the problem asks for the **distinct** multisets. ↵
↵
When I wake up, I find this problem looks easy but I cannot solve it even if $k=2$. Is this problem greedy or related to the maximum flow? How about $k>2$?
↵
Let $n$ be a positive integer and $S$ be a multiset consisting of numbers from $\\{1, 2, ..., n\\}$. Integer $i\,(1 \leq i \leq n)$ appears $a_i \geq 0$ times in $S$. Also, I was given a positive integer $k$. A partition of $S$ into multisets, namely $\cup_{i=1}^t S_i$, is valid iff **all** of the following three conditions hold:↵
↵
(1) $\cup_{i=1}^t S_i = S$.↵
↵
(2) $\forall 1 \leq i
↵
(3) $\forall 1 \leq i
↵
Find the minimum possible number of **distinct** multisets in the partition of $S$.↵
↵
For example, if $k=2$ and $S=\\{1, 1, 1, 2, 2, 2\\}$, the answer is $1$ because you can decompose $S$ into $3 \times \\{1, 2\\}$, so you should answer $1$ because the problem asks for the **distinct** multisets. ↵
↵
When I wake up, I find this problem looks easy but I cannot solve it even if $k=2$. Is this problem greedy or related to the maximum flow? How about $k>2$?
