PROBLEM LINK:Author: Praveen Dhinwa DIFFICULTY:Hard PREREQUISITES:DP, Simple combinatorics, Bitmask PROBLEM:Given is an array $A$, filled with numbers from 1 to 27. We have to report the number of ways in which we can add exactly $K$ numbers to this array (numbers to be added should be from 1 to $L$ and the same number can be added multiple times) such that it becomes closed under the GCD operation. To be closed under GCD operation means that if $x$ and $y$ are in the set, then so is $GCD(x$, $y)$. Note that 1 is always a member of the set. EXPLANATION:Subtask 1 In this case, we have $N \leq 15$. This clearly hints towards an exponential solution. Since this is a counting problem, clearly, there must be a an organised method of counting th ways, i.e., DP. We need to add numbers from the range $[1, L]$. For the given array, let us first find out which all numbers must be added to satisfy the property that for any two numbers from the original array, their GCD exists in the set. Since there are just $N \leq 15$ numbers initially, this can be easily done in quadratic or cubic time. Since, all the numbers are $\leq 15$, the numbers that should be added to the set can be maintained in the a single integer. We can use bits to indicate which numbers we need. For example, setting the 4th bit to 1 would mean we are missing a 5 which we need. Here is a pseudocode for generating this:
Now, we have in our $mask$ variable, the information we need to start our algorithm. Let us say that $DP[i]$ stores the numbers that we need to add when our set comprises of the numbers which were originally in array $A$ plus the elements correspoding to set bits in $i$. Clearly, the $mask$ variable we found above corresponds to $DP[0]$, i.e., $DP[0]$ = $mask$. How do we calculate $DP[j]$ from $DP[0..j1]$? Let $q$ be a bit that is set in $j$. We know that $p$ = $i$ xor $2^k$ $\leq j$. So, we can take the mask in $DP[p]$ and then see what all numbers we have/need in the set when $q+1$ is added to it. For checking that, we need to iterate over all the elements present in the array $A$ plus the elements indicated by set bits of $p$. This way, we can build the $DP[0 .. 2^L  1]$. Now, while calculating the $DP$ array, the values that interest us are when $DP[i] = 0$. This is because $DP[i]$ being zero means that if we add the elements indicated by the set bits of $i$ to our array, we will get an array closed under GCD. Let us say that $r$ bits of $i$ are set to 1 (any $r$, doesn't affect our counting). But we need to add $K$ numbers to the array. We can add a number multiple times. Here is the combinatorics part of the problem. We need to add $K$ numbers to the array and we have $r$ options. Each of the $r$ numbers must be added at least once. This is a very standard problem in combinatorics often solved by the partitions method: ways to distribute $K$ things into $r$ boxes such that each box gets at least one thing is given by ${K \choose r}$. These values can easily be precomputed for all up till 40 using the recurrence ${n \choose r1} + {n1 \choose r1} = {n \choose r}$. Adding this over all the cases when $DP[i]$ is 0 gives us our answer. The complexity of this approach is $\mathcal{O}(N * 2^N)$. Subtask 2 We need to make a certain observation. Let us think more closely about a ``closed set". There are some numbers in the range $[1, 25]$ whose addition presence or absence from the set doesn't affec the GCD closure property: these numbers are 1, 13, 17, 19, and 23 (1 because there is already a 1 in the given array $A$). Let's call these nonimportant numbers. This allows for a significant reduction. We dont need to care about the 5 (depending on $L$ this can be vary from 1 to 5) out of the 25 numbers that can be possibly added. Thus, we perform the same routine as Subtask 1 and calculate the $DP[i]$ values. We alter our meaning of set bits in $i$ to correspond to numbers from 1 to $L$ excluding the nonimportant numbers lyihng in that range. Now, when $DP[i] = 0$ we need to take care of one more thing. Let us say that $r$ bits are set in $i$. So we can add $K$ numbers by choosing from these $r$. But we also have the option of choosing from the nonimportant numbers numbers too. Therefore, we have some new cases: we can choose $K$ numbers from the $r$ options, or we can choose $K1$ from the $r$ options and the left over 1 from the nonimportant numbers, or we can choose $K2$ from the $r$ options and the left over 2 from the nonimportant ones, and so on. This can be calculated just as before except the fact that when we use the nonimportant numbers, not all of them have to be used. This subproblem is similar to the standard combinatorics problem where in $N$ things need to be filled in $M$ boxes such that some boxes can remain empty. There are ${N+M+1 \choose M1}$ ways to do it. Thus, we have a way to calculate for each $i$ the number of ways in which the numbers indicated by its set bits plus nonimportant ones can be added:
This approach has the same complexity as before, i.e., $\mathcal{O}(N * 2^N)$ except that we consider $N = 20$ since 5 out of the 25 numbers are not a part of our DP. Subtask 3 This further allows us to cut the complexity down to $\mathcal{O}(N * 2^N)$ where $N = 15$. A proper explanation of this will be added soon. Setter has implemented this technique. Please see tester's/setter's program for implementation details. COMPLEXITY:$\mathcal{O}(N * 2^N)$ per test case. SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 31 Jul '16, 04:35

My solution: precompute all possible closed sets for all possible $L$. It turns out that there are just 5 million of them for $L=27$. The sets for $L+1$ can be generated through adding/not adding $L+1$ to sets for $L$. For one test case, we can look at all supersets of the input array for the given $L$, count how many of them have a given popcount, which is the only thing that matters for the combinatorics part. If we have $S$ sets, then the time complexity with bitmasks is $O(LS+TS)$. answered 31 Jul '16, 05:56

You can also try to extend idea from subtask 2 to subtask 3 by making following observation: you don't care about numbers 11 and 13, because you can get GCD equal to 11 or 13 only if one of the numbers is 11/13 itself (you only have 22/26 as multiples of 11/13, and there is no other way to get gcd equal to 11/13 besides of using 11/13 for it). It gives you 21 number to store in your mask. I can't understand how did you get n=22 for last subtask using exactly idea from 2nd subtask  I think it will be 23, as you can't throw away 13 anymore after adding 26, unless you made observation described above. Also you can generate all valid sets with a dfs (for l=27 there are less then $2*10^5$ of such sets) and then check your input with each of these sets to answer a query (code). answered 15 Aug '16, 14:52

I just wonder how this problem is tagged hard?Shouldn't it be easymedium or medium? answered 03 Nov '16, 09:09
