Editorial : Colored Balls

Assume you have a set of elements and you have already figured out the minimal number of groups that need to be created. Now, what happens when you add one more element to the set? What is the minimal information that you need to refresh the answer after adding the incoming element?

Let’s call a slot isolated if the group has a single element. Similarly, let’s call a slot as paired if the group has two elements.

First, we can look at all the isolated slots, and insert one a[i] in each of them. So, we need to keep track of the number of isolated slots for each subset.

Then, for the remaining a[i], we’ll first group them together in the form of (a[i], a[i]). But since this grouping is not allowed, we’ll try to correct it by using the existing paired slots. We can transform (x, y) and (a[i], a[i]) to (x, a[i]) and (y, a[i]). Hence, we also need to track the number of paired slots in each subset.

This leads us to a DP definition of

dp[one][two] is the number of subsets where the count of isolated slots is equal to “one” and the count of paired slots is equal to “two”.

For the transitions, we will just simulate the above strategy (refer to code for more details). The final answer would be

sum((one + two)*dp[one][two])