Editorial for ECOO '21 P4 - Chris' Candy


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: AQT, Riolku

The key observation here is how many combinations a given output has. Consider the sample output grouped by type: 2 9 9 9. The counts of the elements look like this:

2 : 1
9 : 3

Now for each element, recall that two sets with the same amount of all elements are the same. Assuming the rest of our elements have K combinations, and our last element has 3 total, we have 4K total sets. Why? We can choose to have any number from 0, 1, 2, 3 of our last element, and no matter which we choose, we have K combinations for the rest of our elements, for a total of 4K combinations.

Let us have M distinct elements, each with counts C_i. Then the total number of combinations is:

\displaystyle \prod_{i = 1}^M (C_i + 1) - 1

We subtract the empty combination here.

As an example suppose we are given K = 7, as in the sample input. Then we need:

\displaystyle \prod_{i = 1}^M (C_i + 1) - 1 = 7 \displaystyle \prod_{i = 1}^M (C_i + 1) = 8

Well, since we get to choose M, what if we just factor 8?

And indeed, the sample input has C = \{1, 3\}. Another valid output for K = 7 is 1 2 3, which has C = \{1, 1, 1\}.

This should give us the understanding to solve the first subtask. We can simply output K of the same integer, since K is so small.

For the remaining subtasks, we note that we can find the sum of C to be minimal in order to check if it fits under the constraint N \le 10^5. In other words, we must find a set of numbers C_i such that

\displaystyle \prod_{i = 1}^M (C_i + 1) = K + 1

and

\displaystyle \sum_{i = 1}^M C_i

is minimum. By making a change of variable of C_i + 1 = D_i, it follows that

\displaystyle \prod_{i = 1}^M D_i = K + 1

and we are trying to minimize

\displaystyle \sum_{i = 1}^M D_i - 1

Now consider that there exists a D_i such that there exist positive integers a, b where ab = D_i. We can try to immediately minimize the sum by replacing D_i with a and b. In other words, we will replace D_i with a and b when

\displaystyle \begin{align*}
ab - 1 &> a - 1 + b - 1 \\
ab - a - b + 1 &> 0 \\
(a - 1)(b - 1) &> 0 \\
\end{align*}

The only positive integer solutions to the inequality is when a, b \ge 2, so it is always better to replace D_i with a and b. Thus, the optimal solution should have all of D_i not factorable into a, b \ge 2 meaning that all D_i should be prime. So, after factoring K into its prime factors, we can compare the sum against 10^5.

The second subtask rewards solutions who made these observations but implemented an inefficient solution, potentially by factoring in linear time.

The final subtask can be solved by factoring in \mathcal O(\sqrt{K}) time or other efficient methods. Implementation details are left as an exercise to the reader.

Time Complexity: \mathcal O(\sqrt{K})


Comments

There are no comments at the moment.