## Editorial for Back From Summer '19 P6: Composite Zeyu

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.

Author: wleung_bvg

For the first subtask, we can iterate over each subset of arm lengths and count the number of unique prime factors for that subset. We can store the minimum number of primes factors for each size of the subset.

Time Complexity:

For the second subtask, we can represent an arm as a bitmask of the prime factors it contains. Since there are only primes less than or equal to , there are possible bitmasks. We can keep track of how many arms have a bitmask that is a subset of the bits for each of the bitmasks. Let be the bitmask of arm . For each arm, we can go through each of the bitmasks and increment that bitmask's count if is a submask of that bitmask.

To find the answer for each value of , we can iterate through each of the bitmasks that have a count of at least and find the minimum number of bits in those bitmasks.

Let be the number of primes less than .

Time Complexity:

For the third subtask, we can use an idea similar to the second subtask. To speed up the solution, we will split the bitmask into two parts: the first bits, and the last bits. We will keep track of , which stores the number of arms such that the last bits evaluates to , and the first bits is a submask of . For each value of , we will need to iterate through bitmasks to update the array.

Finally, remember to take the suffix minimum of the answer array, in case there are some values of that do not have a bitmask that results in a sum equal to .

Here, it is optimal to choose .

Some tricks for optimization include taking the transpose of between the initial update, and the iteration over the bitmasks, as well as reversing the order of indices in the array.

Time Complexity:

###### Alternate Solution

wleung_bvg has no idea how to SOS DP, so please bear with him.

For those who do not like data structures, there is also a dynamic programming solution using a method known as Sum Over Subsets (SOS). SOS allows us to efficiently compute the sum of all such that for all values of , given an array of size ( is the bitwise operator).

Let be the set of all submasks that differ from only in the first bits. If the bit of is a , then it's clear that any masks with the bit as cannot be a submask of . Thus, all submasks that differ only in the first bits must also only differ in the first bits. It follows that .

If the bit of is a , then we can divide into two disjoint sets. The first set is all submasks that have the bit as , and differ only in the first bits. The second is the set of all submasks that have the bit as and differ only in the first bits. Thus it follows that where is the bitwise operator).

It can be shown that these subset relations create overlapping subproblems, allowing for a dynamic programming solution by adding the values of the subsets. More information on SOS dynamic programming can be seen on a Codeforces article.

To set up the initial array, contains the number of arms that have a mask equal to . Since all bitmasks are a subset of , we can solve the subset sum problem for that mask, and due to the nature of dynamic programming, will contain the answer for each value mask . We can see that the subset relations form a directed acyclic graph, with being nodes with an outdegree of for all masks . This will be our base case for the dp. We will initialize to . From here, we can see that all will always depend on another set such that or . Thus, we can compute for all values of and by iterating over all masks in ascending order, and for each mask , compute for all values of in ascending order using the relation described above based on whether the bit is set. Specifically, if the bit is , and if the bit is .

Once this is completed, the number of arms that have a mask that is a subset of can be found at . The answer can then be recovered in a manner similar to the first solution for subtask 3.

Time Complexity: