PROBLEM LINK:
Author: Bhuvnesh Jain
Tester: Bhuvnesh Jain
Editorialist: Bhuvnesh Jain
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Dynamic Programming, Sieve of Eranthoses
PROBLEM:
Find the number of ways to express the n as the sum of primes when
- order of primes does not matter.
- order of primes matter.
EXPLANATION:
The question can be easily solved using using precomputation which can be done using dynamic programming.
First generate the list of all prime numbers less than 5000 using sieve of Eranthoses, which can be done in O(nloglogn) complexity.
Now, let us first solve the dynamic programming problem when the order of primes does not matter. This is just a modification of the problem of expressing n as sum of first k numbers. Here the first k numbers are actually the prime numbers less than or equal to n. In, my solution dp_no_order[i] denotes the number of ways to express i as sum opf primes when ordering of primes does not matter. This can be implemented in O(np), where p = number of primes.
Finally, let us solve the problem when ordering of primes matter. Let us denote dp_order[i][j] as the number of ways to express i as the sum of primes when ordering matters and the largest prime used is j. This can easily done by using prime numbers in increasing order. For example, let us take the case when i = 10 and j = 2, 3, 5, 7.
j = 2, means (2, 2, 2, 2, 2)
j = 3 means (2, 2, 3, 3)
j = 5 means (2, 3, 5) and (5, 5)
j = 7 means (3, 7)
The complexity of this method is O(n^3) which is not enough. It can be easily optimised to O(n^2) using cummulative_dp. You can see the implementation for more details.
Some users have also done the above question using 1-D states for both parts. One such solution is here.
COMPLEXITY
O(nloglogn + np + n^2 + t), where n = 5000, t = number of test cases, p = number of primes below n.
AUTHOR’S SOLUTION:
Author’s solution can be found here.