PROBLEM LINK:Author: Dmytro Berezin PROBLEM EXPLANATIONChef has an array consisting of N elements. Chef may pick any 2 adjacent elements which are both positive, decrement each of them by 1, and increment the next one (in front of them) by 1. (If those elements were the last two elements he appends 1 to the end of the array). Chef wants you to count the number of different arrays that he is able to reach via any sequence of moves. Since answer is large calculate it modulo 10^{9}+7 DIFFICULTY:easymedium PREREQUISITES:Dynamic Programming EXPLANATION:According to the given constraints, chef won't be able to construct an array having more than 60 elements (this can be proved by paper or maybe be writing a greedy checker). Observe that two different sequences of moves (without considering the order of the moves) will lead to different resulting arrays. That's because there will be at least one element which was variated differently between the two sequences of operations (You can prove that if you apply operations in order from left to right). This problem is a Dynamic Programming exercise, let's define a function that solves this problem dp[pos][deltapos][deltanxt] which denotes the number of different arrays that could be obtained by performing operations 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. (1 ≤ pos ≤ 60) (50 ≤ deltapos,deltanxt ≤ 50) The base case of our function would be dp[61][0][0] = 1 The recurrence formula of our function is kind of easy to figure out, we should try all different ways of changing the element at the index pos, and it's clear that we have min(arr_{pos}+deltapos , arr_{nxt}+deltanxt) + 1 different ways (That's because all elements must be positive during any move and we are decrementing both of arr_{pos} , arr_{pos+1}). For each number of operations op (0 ≤ op ≤ min(arr_{pos}+deltapos , arr_{nxt}+deltanxt) + 1), performing any of them would lead us to a different solution from all the others. For each (0 ≤ op ≤ min(arr_{pos}+deltapos , arr_{nxt}+deltanxt) + 1) dp[pos][deltapos][deltanxt] += dp[pos+1][deltanxtop][op] Performing op would substract op from the next element and add op to the element after the next and our current element won't be affected in future operations, so we may discard it from the state. AUTHOR'S AND TESTER'S SOLUTIONS:AUTHOR's solution: Can be found here
This question is marked "community wiki".
asked 14 Aug '17, 08:59

It's not difficult to prove the max length is at most $60$. Consider an operation. It subtracts $a_{i2}$ and $a_{i1}$ by $1$, and adds $a_i$ by $1$. The number $f(a)=\sum_{i\ge 1}\phi^ia_i=\phi a_1+\phi^2a_2+\dots+\phi^na_n$ won't change, where $\phi=\frac{1+\sqrt{5}}{2}\approx 1.618$ is a solution of $\phi^2=\phi+1$. This is because when we subtract $a_{i2}$ and $a_{i1}$ by $1$, $f(a)$ decreases by $\phi^{i2}+\phi^{i1}=\phi^{i2}(1+\phi)=\phi^{i2}\cdot\phi^2=\phi^i$, and when we add $a_i$ by $1$, $f(a)$ increases by $\phi^i$. This proves that $f(a)$ remains a constant. Let the max length be $N$. Then the minimum $f$ possible when $a_N>0$ is $\phi^N$; however the maximum $f$ that the input can provide is $\phi\cdot 50+\phi^2\cdot 50+\dots+\phi^{50}\cdot 50=\sum_{i=1}^{50}50\phi^i$. Thus $\phi^N\le\sum_{i=1}^{50}50\phi^i$. $\therefore N\le\log_{\phi}\left(\sum_{i=1}^{50}50\phi^i\right)$. We can write a python program or something to calculate this is $60.xxx$, thus $N\le 60$. (Someone asks me to elaborate. So I made this post more detailed. Hope this is easier to understand. answered 19 Aug '17, 16:44
What is this?!???
(19 Aug '17, 17:00)
Yes this is interesting, can you please elaborate?
(19 Aug '17, 21:53)
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 nonzero 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.
(20 Aug '17, 17:34)
1
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.
(20 Aug '17, 17:39)
Sleek trick! I love it even more because it uses phi and the problem is called Fibonacci Array.
(23 Aug '17, 03:36)
2
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 nth fibonacci number.
(23 Aug '17, 05:54)
showing 5 of 6
show all

This problem was really tough for me and I spent a lot of time thinking about this problem during the contest. I knew this is a dynamic programming problem but couldn't implement the solution properly. Can you provide a link to some good problems like these on multidimensional dynamic programming as I want to improve myself on this topic. answered 18 Aug '17, 17:05
@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.
(22 Aug '17, 20:53)
div2 hard mean div2 1000 pointers or anything else?
(23 Aug '17, 07:08)
1
Yes, div 2 1000 level problems.
(24 Aug '17, 20:44)

Let me try to explain the idea behind my solution. In the problem, we are allowed to apply the operations in any order, however, you can always apply the operations in the order from left to the right and the result of applying these operations is still the same. The resulting arrays due to the application of the operations will be same as the number of ways of applying these operations. So, we can instead count the number of ways of applying the operations to the array. Let us go from left to right. Suppose we are currently at index $i$. Note that the operations that were applied to the array at indices less than or equal to $i3$ won't affect the value of index $i$, because an operation can only affect three indices at max. However, the operations made at indices $i1$ and $i2$ can still affect the array value at index $i$. Now, we can apply some operations at indices $i, i + 1, i + 2$ (decrease the value by 1 at $i, i + 1$ and increase the value by 1 at $i + 2$). This observation leads us to a dp solution that can be described as under. Let $dp(i, delta, nextDelta)$ be the number of ways of creating different arrays of $A$, where $i$ denotes the current index in the array, $delta$ denotes the change in the value of $a_i$ and $nextDelta$ denotes the change in the value of $a_{i+1}$ by the operations done till now. Notice that $i$ can be greater than $n$, and $delta$ and $nextDelta$ can have negative values. The transitions of the dp states will happen as follows. The updated value of $a_i$ will be $a_i + delta$, and the value of $a_{i+1}$ will be $a_{i+1} + nextDelta$. The maximum number of operations that can be done on the index $i$ will be $min(a_i + delta, a_{i+1} + nextDelta)$. We stop when we are at some index $i > n$ and $delta$ is zero, because we can no longer make any further operations. I agree that I have kind of handwaved over a lot of arguments here. You can go to my solution to see a possible implementation of this approach. answered 18 Aug '17, 16:41
Hey praveen, can you help me ehre https://discuss.codechef.com/questions/108350/cansomebodyhelpmedebuggingthiscode I tried to use the similar approach, but I am getting WA and TLE.
(18 Aug '17, 20:30)
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?
(27 Aug '17, 15:17)

How can one person arrive at this solution? What should have been the thought process to solve this question? Can someone please help with this.
link
This answer is marked "community wiki".
answered 19 Aug '17, 10:25

Editorial lacks clarity. A lot of things are unexplained. answered 28 Aug '17, 15:34

Access denied for all solutions. answered 18 Aug '17, 15:17

not able to get the editorial solution. Some one please explain it? answered 18 Aug '17, 15:53
@sharan_omkar: I have written my idea below. Let me know if it makes sense!!
(18 Aug '17, 16:41)
@dpraveen thanks now it's clear to me :)
(19 Aug '17, 13:44)

A must do DP problem, altogether a great question. If anyone is having doubt please see the solution by @dpraveen it explains implementation part easily. answered 18 Aug '17, 20:26

How do we guarantee that (50 ≤ deltapos,deltanxt ≤ 50) and also how do we conclude that dp[61][0][0] = 1. answered 18 Aug '17, 22:46

Answer is hidden as author is suspended. Click here to view.
answered 19 Aug '17, 15:45

I used two 2d arrays instead. https://www.codechef.com/viewsolution/14980893 answered 25 Aug '17, 19:22

how to prove that the max length is 60 ?
can you link editorials with questions It will be easy to search
"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?
Shoudn't it be: dp[pos][deltapos][deltanxt] += dp[pos+1][deltanxtop][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).