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 \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$$$?
I have no idea to solve it also.
You should describe in more detail what value you want. I don't know where this 1 came from.
and if $$$[1,1,2,2,2]$$$ is split into $$$[1,2][1,2][1,2]$$$ , does it not meet the $$$(s_i≠s_j)$$$?
The author updated this question. Deleted (si≠sj).
For the case of $$$k=2$$$, this problem is equivalent to a given array. You can select two numbers at a time, subtract the larger one from the smaller one, and then delete the smaller one. Ask the minimum number of operations to clear the array. For $$$3\le k$$$, I guess this greedy strategy will fail.
I have encountered this problem on Codechef (in $$$k=2$$$). The author of the problem only gives a dp approach. So I guess there is no algorithm with complexity independent of $$$∑{a_i}^k$$$.
Attachment: It would be much better if there is a limit of $$$∑a_i≤10^5$$$, but there is no reason to do so, otherwise why not directly input the S set?
Yes, the original condition (2), which states that $$$S_i \neq S_j$$$ for $$$i < j$$$ has been removed. It is wrong and misleading. I have to make it clear. Maybe I was still dreaming when I wrote the statements. I feel sorry.
When $$$S=\{1, 1, 1, 2, 2, 2\}$$$ and $$$k=2$$$, we could split $$$S$$$ into three same multisets, each of them is $$$\{1, 2\}$$$. There is only one distinct subset as the three multisets are the same. In your problem, when $$$S=\{1, 1, 2, 2, 2\}$$$ and $$$k=2$$$, the answer should be $$$2$$$: Two $$$\{1, 2\}$$$ and one $$$\{2\}$$$.
Would you please provide me with the link to the CodeChef problem?
I forgot. I only remember that this is after June 2022.
The dp solution is that in the worst case, you need n operations to clear all array elements (because you cannot delete two elements at the same time). But if you divide the array into k disjoint subsets so that the subset can be divided into two subsubsets and the sum of the two subsubsets is the same, then the answer is n-k. (It is easy to prove this. The last operation for this subset is to extract a number from these two subsets and eliminate them together.)
For each i, use
dp[i][j]to save only 1~i numbers, and the absolute value of the difference between the current distance subset and the same sum is j, and the maximum number of subsets divided.Auto comment: topic has been updated by div4only (previous revision, new revision, compare).