CHEFFA - Editorial

aug17
cheffa
dynamic-programming
easy-medium
editorial

#21

@dpraveen thanks now it’s clear to me :slight_smile:


#22

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?!???


#23

can you link editorials with questions It will be easy to search


#24

Yes this is interesting, can you please elaborate?


#25

yes its correct now


#26

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.


#27

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.


#28

“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?


#29

@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.


#30

Sleek trick! I love it even more because it uses phi and the problem is called Fibonacci Array.


#31

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.


#32

div2 hard mean div2 1000 pointers or anything else?


#33

Yes, div 2 1000 level problems.


#34

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?


#35

Shoudn’t it be: dp[pos][deltapos][deltanxt] += dp[pos+1][deltanxt-op][op]?


#36

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).


#37

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?