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).
Editorial lacks clarity. A lot of things are unexplained.
1 Like