spoj problem ACTIV hints :

general
,
1

i have been stuck in spoj problem ACTIV. Due to constraints it is getting difficult to solve for me.Kindly someone provide some hint so that i can proceed
thanks in advance :slight_smile:

2

hmm actually you have recurrance relation that

F(Pos) = F(pos + 1);
F(pos) = F(pos) +  F(Next(pos));

here Next(pos) represent that when we take pos’th element or activity then we skip those elements which can’t be participate in this set :smiley:
So This part and Base condition is easy :wink:
i think this is enough :stuck_out_tongue:

IF you want to know more do pratice :stuck_out_tongue:

3

Problem link : SPOJ ACTIV

I have written a recursive solution for this problem and it is working fine.But i am not able to store the calculated result due to memory constraint…So i want to Know how to further Minimize the state space of function arguments.

My solution link : Here in order to memoize i need 2 D array…Can any body help me to improve this recursion so that i need only 1D array.Actually at present I am comfortable little bit in top down approach.