@dpraveen thanks now it’s clear to me 
The number ∑i≥1ϕiai∑i≥1ϕiai won't change, where ϕ=1+5√2ϕ=1+52 is a solution of ϕ2=ϕ+1ϕ2=ϕ+1.
What is this?!???
can you link editorials with questions It will be easy to search
Yes this is interesting, can you please elaborate?
yes its correct now
I understood one thing that these two arrays of length N - [0 0…1] and [1 0…0 0] are different. The f() for the first one will be phi^1 while for the second one will be phi^N. For the array of size N will have a non-zero element at nth pos. So, to minimise it make all element 0 and put 1 at the Nth element. This will ensure that the f() is calculated for an array of length N.
Any operation on array a doesnt change the value of f(a). I think it means that you cannot change the length of the array ‘a’ more than log(f(a)).
log(f(a)) - gives a number which is the max length possible for the given array.
1 Like
“on the subarray starting from the element having index pos assuming that this element was changed by deltapos and the next element to the right was changed by deltanxt.” Can somebody please explain this to me?
@underdog_eagle: I don’t have a specific set of problems. If you see Topcoder Div 2 hard problems, you will set a lot of such examples of dp problems, which require multiple dimensions in the state.
Sleek trick! I love it even more because it uses phi and the problem is called Fibonacci Array.
There is a reason for the problem to be called “Fibonacci Array” - if all n members of the initial array are equal to 1 then the answer will be the n-th fibonacci number.
2 Likes
div2 hard mean div2 1000 pointers or anything else?
Yes, div 2 1000 level problems.
1 Like
Can you please tell me, how do you approach such a DP problems with such a lenient solution in one go?
I mean what type of technique do you follow in solving these ones?
Shoudn’t it be: dp[pos][deltapos][deltanxt] += dp[pos+1][deltanxt-op][op]?
Also, I think there shouldn’t be a +1 here: 0 ≤ op ≤ min(arrpos+deltapos , arrnxt+deltanxt) + 1 (in the two places where it appears).
what does f(a) represent wrt array that we have? and how did you come up with this function and what is the general idea about this function?
Can anyone point out where is a mistake in this code:
#include <iostream>
#include <cstring>
#include <cassert>
#define ll long long int
#define DELTA 50
#define MOD 1000000007
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n;
ll a[101], dp[101][101][101];
cin >> n;
for(int i=1;i<=n;i++)
cin >> a[i];
for(int i=n+1;i<101;i++)
a[i]=0;
memset(dp, -1, sizeof(dp));
dp[100][DELTA][DELTA] = 1;
for(int pos=99;pos>0;pos--){
for(int deltapos=-50;deltapos<=50;deltapos++){
for(int deltanext=-50;deltanext<=50;deltanext++){
ll& reff = dp[pos][deltapos+DELTA][deltanext+DELTA];
reff = 0;
for(int op=0;op<=min((a[pos]+deltapos), (a[pos+1]+deltanext)); op++) {
reff += dp[pos + 1][deltanext + DELTA - op][op + DELTA];
reff %= MOD;
}
}
}
}
cout << dp[1][DELTA][DELTA] << endl;
}
return 0;
}
It passess first subtask but fails in second subtask.
And one another query:
we have 0\le op \le min(a[pos]+deltapos, a[pos+1]+deltanext) and we are using op to index into the dp table. Now max value of op can be more than 50 because if a[pos]=a[pos+1]=50 and deltanext=deltapos=50 then op can be 100. So why we have taken -50\le deltanext, deltapos \le 50?