PROBLEM LINK:Author: Sergey Nagin DIFFICULTY:Medium PREREQUISITES:Dynamic programming, combinatorics, number theory PROBLEM:How many arrays $A[1\ldots N]$ are there such that $1 \le A_i \le M$ and $\gcd(A_i,A_j) = 1$ for all $i < j$? QUICK EXPLANATION:Every number $> 1$ appears at most once in the sequence. Everything else is $1$. Let $S$ be the set of values of the sequence that are $> 1$. Our strategy will be to enumerate all possible sets $S$, and then sum up all their contributions to the total answer. The first step is to enumerate all possible $S$'s by enumerating all subsets of $\{2, 3, \ldots, 100\}$ that are pairwise coprime. Actually, we only need the sizes, so this can be done very efficiently with memoization and some optimizations. The next step is to add the contribution of each set $S$. We only need its size, $s$. There are $\frac{N!}{(Ns)!}$ ways to select the arrangements of these values in the sequence, and everything else will be $1$. So the answer is the sum of $\frac{N!}{(Ns)!}$ among all sizes $s$. EXPLANATION:For $M \le 10$For any two numbers $a$ and $b$, $\gcd(a,b) = 1$ if and only if $a$ and $b$ has no common prime factors. In other words, if we define $P(n)$ as the set of prime factors of $n$, then $\gcd(a,b) = 1$ if and only if $P(a)\cap P(b) = \emptyset$. Since there are only four primes $\le 10$, namely $\{2,3,5,7\}$, we can formulate a dynamic programming solution that has approximately $2^4N$ states. If $S$ is a subset of $\{2,3,5,7\}$, define $f(n,S)$ as the number of sequences such that:
Clearly the answer that we want is $f(N,\{2,3,5,7\})$. Also, we can implement a subset of $\{2,3,5,7\}$ as a bitmask of $4$ bits, which is simply an integer from $0$ to $15$. To find a recurrence for $f(n,S)$, we enumerate all possible $n$th elements, from $1$ to $M$. For a value $v$ to be a valid last element, its set of prime factors, $P(v)$, must be a subset of $S$. (Using bitmasks, this can be implemented using bitwise operators.) Afterwards, the set of allowed primes for the remaining $n1$ elements is $S  P(v)$, where "$$" denotes set difference. Thus, we have the following recurrence: $$f(n,S) = \sum_{\substack{v=1 \\\ P(v)\subset S}}^M f(n1,S  P(v))$$ For optimization, the $P(v)$s can be computed beforehand. Also, for the base case, we have $f(0,S) = 1$. Thus, we can now compute $f(n,S)$ using dynamic programming! See the following pseudocode:
Representing these sets as bitmasks and using bitwise operators for set operations, we get the following more detailed pseudocode:
It's much more obvious now how many operations this will take, so we can now see that this runs fast enough for the first subtask! For $M > 10$Unfortunately, for the remaining subtasks, $M$ can reach up to $100$, and there are $25$ primes up to $100$. This means that the algorithm above will have $2^{25}N$ states. For subtask two, you might still be able to optimize a lot and squeeze into the time limit (though it isn't easy), but for subtask three, there's no way this will pass. Instead, we need to find better solutions. Solution 1Let's call a number big if it is greater than $1$. The first important insight is that every big number will appear at most once in our sequence. Otherwise, if $x > 1$ appears more than once, say at positions $i$ and $j$, then $\gcd(A_i,A_j) = x \not= 1$, which violates our requirements. This automatically means that there are at most $99$ big numbers in our sequence, and for large $N$, this means that most elements will be equal to $1$! Thus, we have two remaining tasks:
The second one is actually easy: If the set of big numbers has size $s$, then there are exactly ${N \choose s}$ ways to choose the places where these big numbers will go, and then $s!$ ways to choose which big number goes where. Everything else will be $1$, thus, there are ${N \choose s}s! = \frac{N!}{(Ns)!}$ valid sequences! To compute $N!$ and $(Ns)!^{1}$, we need to precompute all factorials and inverse factorials up to $100000$ beforehand. We can use the following simple recurrences: $$\begin{align*} N! &\equiv N(N1)! \bmod (10^9 + 7) \\\ N!^{1} &\equiv N^{1}(N1)!^{1} \bmod (10^9 + 7) \end{align*}$$ All that remains is enumerating all sets of big numbers that are pairwise coprime. Let's call such sets big sets. To begin with, let's try a simple recursive enumeration. Let's create a routine called A straightforward implementation is the following:
This
Unfortunately, this doesn't work as it is, because there are just too many big sets. So here, we will describe a few optimizations that will make things faster. First, notice that we can do a simple optimization: instead of the sets themselves, we can just enumerate the sizes of the big sets, because the sizes are all we need.
A second optimization is to collect the sizes as a list of frequency counts for each size, because the largest size of each big set is at most $m$:
But still, this isn't enough; even though the output list is now small, we still call
But this is still not enough, because there is still too many distinct calls to At this point, there are two major optimizations that will allow Optimization 1: Primes $> 50$ This optimization uses the fact that primes $> 50$ will appear never appear with other prime factors, because if $p > 50$, then $2p$ already exceeds $100$. Thus, we can try to consider these primes separately. The first step is to create a version of
The added check here is
Here, we initially call Using this optimization, Optimization 2: Limiting the values of $S$ A different optimization involves looking at the parameter
The change here is in the first few lines, where a call to This solution implemented in one of the tester's solutions below. (Sets are implemented as bitmasks.) Solution 2A different solution involves considering all primes $> 10$ specially, not just primes $> 50$. The insight here that we will use heavily is that each number has at most one prime factor $> 10$. We will need our $f(n,S)$ function earlier. Recall that $f(n,S)$ is the number of valid sequences of length $n$ where the only allowed prime factors are in $S$. This time, we will only precompute this table for $S$ that is a subset of $\{2, 3, 5, 7\}$. (Obviously this isn't enough because $M > 10$, but we will still need these values.) The key insight here is that for every value $1 \le v < 10$, the primes in the range $\left(\frac{100}{v+1}, \frac{100}{v}\right]$ are all "functionally" identical. This is a generalization of the fact that we used earlier: that primes $> 50$ can be treated specially because they all appear alone. Similarly:
Thus, really, all we care about is how many primes from each of the following ranges we take: $(100/2, 100/1]$, $(100/3, 100/2]$, $(100/4, 100/3]$, etc. Afterwards, we figure out using some combinatorics where their positions will be, and which ones will appear as $p$, $2p$, $3p$, etc. And then finally, once we take care of these primes, we can now fall back to our precomputed $f(n,S)$, because all primes $> 10$ have been accounted for already! Lots of details have been skipped, but if you want to find out more, this solution is implemented in one of the tester's solutions below, so you can check it out. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 17 May '16, 01:54

What's the running time for the author's and testers solutions? Are they faster than other contestants solutions? I guess I could enter them myself under the practice section to see. But it doesn't feel right to enter someone else's code under my name. answered 18 May '16, 17:36

The setter's and tester's solutions are not of this question. answered 18 May '16, 17:40

Another addition is we can enumerate only odd numbers <=50 and since there can be only at the most one even number per set from the set we can determine how many even numbers are possible and if there are k even numbers to choose from we have k sets of size i+1 and 1 set of size i. I solved it using the same method but with the even number thing . here's the link to my C++ solution. answered 18 May '16, 18:03

Here is the C++ solution for the question using the same method but with some additions. answered 18 May '16, 18:05

There also exist closedform polynomial expressions for F(N,M): F(N,1)=1, F(N,2)=1+N, F(N,3)=1+N+N^2, F(N,4)=1+N+2N^2 , F(N,5)=1+3NN^2+2N^3 , F(N,6) = 1+3N+2N^3 F(N,7) = 1N+9N^24N^3+2N^4 ... I don't see any pattern as such , except that F(N,M) ~ O(N^pi(M)) , where pi(M) counts no. of primes <= M. answered 19 May '16, 08:40

Can anyone explain solution 2 in more depth ? Thanks in advance. answered 19 May '16, 15:34

Fix the solutions links. They currently link to DISTNUM2 solutions.