A Problem from my dream

Правка en5, от div4only, 2023-02-22 07:20:09

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 of $$$\{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$$$ $$$\{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$$$?

Теги greedy, maximum flow

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en9 Английский div4only 2023-02-22 11:35:09 53 Tiny change: ' 1 \leq i < j \leq t,\,S_i \neq S_j$.\n\n(3) $\forall 1 \leq i ' -> ' 1 \leq i '
en8 Английский div4only 2023-02-22 07:26:33 0 (published)
en7 Английский div4only 2023-02-22 07:26:20 9 Tiny change: 'S$ into $3$ $\\{1, 2\\}' -> 'S$ into $3 \times \\{1, 2\\}' (saved to drafts)
en6 Английский div4only 2023-02-22 07:20:53 24 Tiny change: ' multiset of $\\{1, 2,' -> ' multiset consisting of numbers from $\\{1, 2,'
en5 Английский div4only 2023-02-22 07:20:09 2
en4 Английский div4only 2023-02-22 07:19:53 474 (published)
en3 Английский div4only 2023-02-22 07:16:06 244
en2 Английский div4only 2023-02-22 07:13:42 7 Tiny change: 'mely $\cup\limits_{i=1}^t S' -> 'mely $\cup_{i=1}^t S'
en1 Английский div4only 2023-02-22 07:13:09 500 Initial revision (saved to drafts)