0
$\begingroup$

The following problem was part of a local programming contest I attended..(I solved it via the obvious Brute Force solution)
I was wondering whether there was a cleaner Dynamic Programming solution.
Problem Statement:
You have an array $a$ of $n$ integers and an integer $k$. Your task is to find a subset $m$ of a where the following 2 conditions hold:
1) $\prod\limits_{x\in m}x \equiv 0\mod k$.
2) Size of $m$ is minimal possible (size of $m \gt 0$).

Constraints:
$1 \le n \le 10^4$
$1 \le a_i \le 10^9$
$2 \le k \le 10^9$
Time Limit = 3 seconds
Memory Limit = 256 MegaBytes

(I am a beginner in the concept of DP, so I am looking for a detailed explanation and if possible. some code. Thanks in advance :D)

$\endgroup$
3
  • 1
    $\begingroup$ Please credit the original source where you encountered this task. Can you link to the original problem? (even if it is not in English) $\endgroup$
    – D.W.
    Dec 30, 2020 at 20:42
  • $\begingroup$ Please do not re-post questions. $\endgroup$
    – D.W.
    Dec 30, 2020 at 20:45
  • $\begingroup$ We've provided resources on how to approach dynamic programming tasks: cs.stackexchange.com/tags/dynamic-programming/info. Please study those materials, follow the systematic process outlined there, and then edit your question to show the progress you've made and at what stage you got stuck. $\endgroup$
    – D.W.
    Dec 30, 2020 at 20:49

2 Answers 2

1
$\begingroup$
  1. Compute all the prime factors of $k$. It would take $O(\sqrt{k})$ time $\approx$ $10^5$ time. Note that, there could be at most $10$ different prime factors of $k$ since considering the $10$ smallest prime numbers gives the product: $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29$ which exceeds $10^9$. Let us call the prime factors of $k$ as: $f_{1}, \dotsc,f_{10}$ with multiplicities $m_{1}, \dotsc,m_{10}$, respectively. The sum of multiplicities (or total number of prime factors) $\sum_{i = 1}^{10}m_{i}$ could be at most $30$ since $2^{30}$ exceeds $10^{9}$.
  2. Now, you also need to factorize the numbers given in array $a$. However, you do not need to obtain all its factors. You just need to obtain the factors which are among $f_{1},\dotsc,f_{10}$ since other prime factors are irrelevant for $\prod\limits_{x\in m}x \equiv 0\mod k$. Therefore, just check that if an array entry $a[j]$ is divisible by some factors $f_{i}$ (obtained in step 2) and obtain its multiplicity in $a[j]$. Let $m_{i}^{j}$ denote the multiplicity of factor $f_{i}$ for an array entry $a[j]$. Computing all $m_{i}^{j}$ would take at most $\sum_{i = 1}^{10}m_{i} \cdot n = 30 \cdot n$ time $\approx 10^{6}$ time.
  3. Now, you just need a Dynamic Programming approch to obtain the minimum value on size of $m$. Let $A$ denote a matrix of dimension $(m_{1}+1)$x $(m_{2}+1)$ x $\dotsc$x $(m_{10}+1)$ x $n$ such that an entry $A[j_{1}][j_{2}] \dotsc[j_{10}][t]$ denote the minimum size value of $m$ such that $\prod\limits_{x\in m}x \equiv 0\mod k'$ for $m \subseteq \{a_{1},\dotsc,a_{t}\}$ and $k' = \prod_{i = 1}^{10} j_{i} \cdot f_{i}$. In otherwords, $k'$ is composed of all possible combinations of the factors $f_{1}, \dotsc,f_{10}$. Therefore $k'$ can take at most $(m_{1}+1) \cdot (m_{2}+1) \dotsc (m_{10}+1) \approx 2^{10} \approx 10^{3}$ different values. This bound is based on the assumption that all $10$ factors are distinct. If all the factors are the same the we have $k' \leq 30$ since $2^{30}$ exceeds $10^9$. So I believe $k'$ would take at most $\approx 2 \cdot 2^{10} \approx 2 \cdot 10^3$ different values.

Now, assuming 1 based indexing for the matrix $A$, we define the DP steps as follows.

The Main DP step:

$$ A[j_{1}][j_{2}]\dotsc[j_{10}][t+1] = \min \left\{\begin{array}{lr} A[j_{1}][j_{2}]\dotsc[j_{10}][t], & \textrm{do not pick $a[t+1]$}\\ 1 + A[j_{1}-m_{1}^{t}][j_{2}-m_{2}^{t}]\dotsc[j_{10}-m_{10}^{t}][t], & \textrm{pick $a[t+1]$}\\ \end{array}\right. $$

The Base Step:

$A[j_{1}][j_{2}]\dotsc[j_{10}][1] = 1$ if $j_{i} \leq m_{i}^{1}$ for all $1 \leq i \leq 10$. And $A[j_{1}][j_{2}]\dotsc[j_{10}][1] = \infty$ otherwise. Here $\infty$ means that it is not possible to satisfy the constraint $\prod\limits_{x\in m}x \equiv 0\mod k'$ given $m \subseteq \{a_{1} \}$ and $k' = \prod_{i = 1}^{10} j_{i} \cdot f_{i}$.

The Required Ouput:

The output of the DP procedure would be the solution: $A[m_{1}][m_{2}]\dotsc[m_{10}][n]$ which naturally denote the minimum size value of $m$ such that $\prod\limits_{x\in m}x \equiv 0\mod k'$ for $m \subseteq \{a_{1},\dotsc,a_{n}\}$ and $k' = k = \prod_{i = 1}^{10} m_{i} \cdot f_{i}$.

Running Time Analysis of DP:

The size of the matrix $A$ is $(\textrm{number of possible value of $k'$}) \cdot n \approx 2 \cdot 10^3 \cdot 10^4 \approx 2 \cdot 10^{7}$. Computing each entry takes 2 or 3 operations. Therefore total running time would be $\approx 6 \cdot 10^7$.


Thus the overall running time is $\approx 10^5 + 10^6 + 6 \cdot 10^ 7 \approx 10^8$. I have done the loose analysis, so it should be doable in 3 sec.

Total Space Complexity $\approx $ size of the matrix $A$ $\approx 2 \cdot 10^7$

$\endgroup$
3
1
$\begingroup$

I am the author of this problem and it was problem B in my contest. I have written an editorial here with the normal DP solution to get the 50 points and the coordinate compression DP which would get the 100 points.

$\endgroup$
1
  • $\begingroup$ (A pity you can't comment (yet). OTOH, this non-answer to this non-question is more likely to survive here than on other SE sites.) $\endgroup$
    – greybeard
    Dec 31, 2020 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.