PROBLEM LINK:
Author: Praveen Dhinwa
Testers: Animesh Fatehpuria Pushkar Mishra
Editorialist: Pushkar Mishra
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:
find_missing(A[], N):
mask = 0; // our bitmask variable
for (i = 1 to N) {
for (j = 1 to N) {
if(GCD(A[i], A[j]) not in A[]) {
set the GCD(A[i], A[j]) - 1 bit to 1 in the mask;
}
}
}
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..j-1]? 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 r-1} + {n-1 \choose r-1} = {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
Clearly, \mathcal{O}(N * 2^N) is too large now as N \leq 25 for this task. So we can’t do the the same as we did for Subtask 1.
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 non-important 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 non-important 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 non-important numbers numbers too. Therefore, we have some new cases: we can choose K numbers from the r options, or we can choose K-1 from the r options and the left over 1 from the non-important numbers, or we can choose K-2 from the r options and the left over 2 from the non-important ones, and so on. This can be calculated just as before except the fact that when we use the non-important 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 M-1} 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 non-important ones can be added:
calc(i):
if(dp[i] != 0) {
return 0;
}
r = number of set bits of i;
for (p = r-1 to K-1) {
temp1 = ncr[p][r-1]; // number of ways of taking from $r$ numbers.
temp2 = ncr[K -1 - p + q - 1][q-1]; // number of ways of taking from
// the non-important numbers.
// in this case we assume that there are
// q non-important numbers from 1 to L.
// q can range from 1 to 5.
ans = ans + (temp1 * temp2); // multiplying to get all possibilities
// and adding to the global answer counter.
}
return ans;
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
If we try to use the same solution as before, this time our solution will have N = 22. But that will barely make it under 2 seconds. Maybe with some very neat optimisations and prunings, it can. But there is a more elegant way. We can think more in terms of DP and note the fact that inclusion/exclusion of prime numbers doesn’t affect the GCD closure of a set as much as the inclusion/exclusion of composite numbers does.
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.