div4only's blog

By div4only, history, 21 month(s) ago, In English

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$$$?

  • Vote: I like it
  • +33
  • Vote: I do not like it

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I have no idea to solve it also.

»
21 month(s) ago, # |
Rev. 23   Vote: I like it -24 Vote: I do not like it

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?

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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\}$$$.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Would you please provide me with the link to the CodeChef problem?

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 3   Vote: I like it -33 Vote: I do not like it

      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.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by div4only (previous revision, new revision, compare).