The intended solution is a DP one and hence this solution might be an over-kill but it surely is a unique way to approach the problem!
Monic Polynomials
A polynomial whose leading coefficient is 1 is called a monic polynomial.
Notice that a monic polynomial with degree n has the form a_n x^n + a_{n-1} x^{n-1} + ... + a_1 x^1 + a_0 , where a_n = 1 .
Coefficient Analysis
Suppose we have a monic polynomial of degree n with all roots as positive real numbers. Apart from the coefficient notation, the polynomial can also be written as (x - x_n) (x - x_{n-1}) ... (x - x_1) , where x_1, x_2, ... x_n are the roots of the polynomial.
Let us try to formulate the relation between this representation and the coefficient representation.
(x - x_n) (x - x_{n-1}) ... (x - x_1) = a_n x^n + a_{n-1} x^{n-1} + ... + a_1 x^1 + a_0
-
| a_{n-1} | can be written as \sum\limits_{i} x_i . It can be viewed as the Sum of the product of all the roots, when the product is taken 1 at a time
-
| a_{n-2} | can be written as \sum\sum\limits_{i<j} x_i * x_j . It can be viewed as the Sum of the product of all the roots, when the product is taken 2 at a time
-
| a_{n-3} | can be written as \sum\sum\limits_{i<j<k} \sum x_i * x_j * x_k. It can be viewed as the Sum of the product of all the roots, when the product is taken 3 at a time
-
…
-
| a_{0} | can be written as x_1 * x_2 * x_3 * ... *x_n. It can be viewed as the Sum of the product of all the roots, when the product is taken ALL at a time.
So, if we are given n positive numbers, we can easily find the sum, when the product is taken k at a time. How? We can just construct the coefficient representation of the polynomial whose roots are the given numbers and we can just read off the required coefficients.
Finding the Coefficient Representation in O(n^2)
Suppose that the roots are x_1, x_2, ..., x_n . The degree of this polynomial is n. Suppose we have the coefficient representation of the polynomial with roots x_1, x_2, ... x_{k-1}. How can we get the result for a polynomial with an additional root x_{k}? Observe that P_k = (x-x_k)*P_{k-1}.
P_k = (x-x_k) [a_{k-1 }x^{k-1} + a_{k-2-} x^{k-2} + ... + a_1 x^1 + a_0 ]
P_k = f(x) + g(x)
- Here, f(x) = (x)[a_{k-1 }x^{k-1} + a_{k-2-} x^{k-2} + ... + a_1 x^1 + a_0 ]
- Here, g(x) = (-x_k) [a_{k-1 }x^{k-1} + a_{k-2-} x^{k-2} + ... + a_1 x^1 + a_0 ]
Upon analyzing the individual coefficients, we notice that all the coefficients in f(x) get promoted up by one level (due to multiplication by x) while all the coefficients in g(x) get magnified in intensity by a factor of - x_k .
Upon adding f(x) and g(x), we get the following relation for the new coefficients
a_i' = a_{i-1} - x_k*(a_i)
a_0' = - x_k*(a_0)
a_k = 1
To fill the i-th entry, we require the old value of i-th entry. We can populate the result from the leading coefficients down to the constant term.
A monic polynomial with degree 0 has the coefficient representation as [1] . We start out with the polynomial of degree 1 and build the coefficient representation of degree n using the above algorithm in a bottom-up manner.
Hence, we can construct the coefficient representation in time 1 + 2 + 3 + ... n = O(n^2)
Code to Find the Coefficient Representation
vector<int> coefficient(degree + 1, 1);
for(int i = 0; i < degree; i++)
{
int current_root = root[i];
for(int k = i; k >= 0; k--)
{
if(k == 0)
coefficient[k] = coefficient[k] * -current_root;
else
coefficient[k] = coefficient[k-1] - coefficient[k] * current_root;
}
}
The Original Problem
We are given an array and we need to find the number of good subsequences, i.e, subsequences which consist of pairwise distinct elements (and some more restrictions). Notice that the elements of the array are prime and are less than 8000. If you simulate this, you’ll find that there aren’t many primes in this range. (It’s around 1000). Hence, an O(p^2) algorithm should get us through the time limit, where p is the number of distinct primes in the array.
First, we create a hashmap and update the frequency of each prime. The maximum size of the hashmap can be around 1000.
So, suppose we have n distinct primes in the hashmap, with frequency x_1, x_2, x_3, ... x_n.
Let us try to construct subsequences of each length. Of course, the maximum length can be k.
-
There is one good subsequence of length 0. This can be viewed as the leading coefficient of the corresponding polynomial.
-
How many good subsequences are there of length 1? Clearly, we can select the i-th prime, and it would give us x_i ways to pick its copy from the array. Hence, total ways is \sum\limits_{i} x_i . This is nothing but | a_{n-1} |.
-
How many good subsequences are there of length 2? Clearly, we can select the i-th and j-th prime. Now, we have x_i choices to pick a copy of the i-th prime and x_j choices to pick a copy of the j-th prime. Hence, total ways is \sum\sum\limits_{i<j} x_i * x_j . This is nothing but | a_{n-2} |.
-
Similarly, For Subsequences of length 3, we can pick the i-th, j-th, k-th prime and we would have x_i, x_j, x_k choices respectively to pick their copy from the array. Hence, total ways is \sum\sum\limits_{i<j<k} \sum x_i * x_j * x_k. This is nothing but | a_{n-3} |.
-
…
-
Finally we have to stop at subsequences of length k.
To conclude, every coefficient of this polynomial represents the number of good subsequences of some length.
Note that if there was no restriction on k, our answer would simply be | P(-1) | , which can be computed in linear time without finding the coefficient representation. [We can simply put x = -1 in (x - x_n) (x - x_{n-1}) ... (x - x_1) ].
Algorithm
1) Create a hashmap and store the frequency of every element present in the array.
2) Update k as min(k, size_of_hash_map)
3) Visualize all the values in the hashmap as roots
4) Create the coefficient representation with these roots.
5) Finally, return the absolute sum of the first (k+1) coefficients.
* We need to start from the leading coefficient.
.
Time Complexity
O(p^2 + array\_length) where p is the number of distinct elements in the array.
