I was trying to solve the following problem.

We are given 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 need to minimize the sum of the array.

and We are given a Q numbers

 Q <= 1000
 X<= 10^18

We need to determine is it 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 constraints.

The approach that I know for subset-sum is dynamic programming which has time complexity sum*sizeof(Array) but since sum can be as large as 10^18 that approach won't work.

Is there any equation relation that I am missing ?


closed as unclear what you're asking by D.W. Nov 11 at 21:03

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What is a Q number? $\endgroup$ – gnasher729 Oct 13 at 4:33
  • $\begingroup$ Q(query) means the number of times will be given different X. $\endgroup$ – Learner007 Oct 13 at 9:34
  • $\begingroup$ I can't understand the problem statement. If you'd like the question to be considered for re-opening, please include a full citation to the original source where you encountered this problem, and edit the question to make sure we can understand the task you are trying to solve. $\endgroup$ – D.W. Nov 11 at 21:04

If the only condition is that $a_i >= 3a_{i-1}$ for even i then this should be quite trivial? What subset sums can you achieve by just picking the last two array elements?

  • $\begingroup$ But there is also another condition. $\endgroup$ – Learner007 Oct 12 at 13:39
  • $\begingroup$ If a0 to a4 are fixed, what choices do you have for a5 and therefore for the sum a0 + ... + a5? $\endgroup$ – gnasher729 Oct 13 at 4:32
  • 1
    $\begingroup$ You may have figured out by now that your problem statement is very unclear, and my guess at what the problem is ( guess, right) seems to have been wrong. But I’ll give you a last hint: If array elements grow fast enough then a greedy algorithm will solve the subset sum problem (if it has a solution), and no dynamic programming is needed. $\endgroup$ – gnasher729 Oct 13 at 11:52

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