I tried to solve the following problem.
We get N and A (0)
N <= 5000 A(0) <= 10^6 and even if i is odd then A(i) >= 3 * A(i-1) if i is even A(i)= 2 * A(i-1) + 3 * A(i-2) element at odd index must be odd and at even it must be even.
We have to minimize the sum of the array.
and we are given Q numbers
Q <= 1000 X<= 10^18
We need to determine if it is possible to get subset sum = X from our array.
What I have tried
Creating a minimum sum array is easy. Just follow the equations and limitations.
The approach I know for subset-sum is dynamic programming with the time complexity sum * sizeof (array), but since sum can be as large as 10 ^ 18, this approach does not work.
Is there an equation relationship that I'm missing?