Problem from my dream

Revision en1, by div4only, 2023-02-22 07:13:09

When I slept soundly last night, my dream took me back to the times when I was still a senior school student. I was given this problem during my college entrance exam:

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$$$, namely $$$\cup\limits_{i=1}^t S_i$$$ is valid iff all of the following three conditions hold:

(1) $\

Tags greedy, maximum flow

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English 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 English div4only 2023-02-22 07:26:33 0 (published)
en7 English 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 English div4only 2023-02-22 07:20:53 24 Tiny change: ' multiset of $\\{1, 2,' -> ' multiset consisting of numbers from $\\{1, 2,'
en5 English div4only 2023-02-22 07:20:09 2
en4 English div4only 2023-02-22 07:19:53 474 (published)
en3 English div4only 2023-02-22 07:16:06 244
en2 English div4only 2023-02-22 07:13:42 7 Tiny change: 'mely $\cup\limits_{i=1}^t S' -> 'mely $\cup_{i=1}^t S'
en1 English div4only 2023-02-22 07:13:09 500 Initial revision (saved to drafts)