×

# CHEFFA - Editorial

Author: Dmytro Berezin
Tester: Prateek Gupta
Editorialist: Hussain Kara Fallah

# PROBLEM EXPLANATION

Chef 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 109+7

easy-medium

# 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(arrpos+deltapos , arrnxt+deltanxt) + 1 different ways (That's because all elements must be positive during any move and we are decrementing both of arrpos , arrpos+1).

For each number of operations op (0 ≤ op ≤ min(arrpos+deltapos , arrnxt+deltanxt) + 1), performing any of them would lead us to a different solution from all the others.

For each (0 ≤ op ≤ min(arrpos+deltapos , arrnxt+deltanxt) + 1)

dp[pos][deltapos][deltanxt] += dp[pos+1][deltanxt-op][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
TESTER's solution: Can be found here
EDITORIALIST's solution: Can be found here

This question is marked "community wiki".

1181234
accept rate: 0%

2.8k1419

2

how to prove that the max length is 60 ?

(19 Aug '17, 12:36)

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

(19 Aug '17, 21:48) 4★

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

(20 Aug '17, 21:15)

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

(27 Aug '17, 16:35)

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

(27 Aug '17, 16:44)

 16 It's not difficult to prove the max length is at most $60$. Consider an operation. It subtracts $a_{i-2}$ and $a_{i-1}$ 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_{i-2}$ and $a_{i-1}$ by $1$, $f(a)$ decreases by $\phi^{i-2}+\phi^{i-1}=\phi^{i-2}(1+\phi)=\phi^{i-2}\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 7★r_64 261●9●24 accept rate: 16% 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?!??? (19 Aug '17, 17:00) Yes this is interesting, can you please elaborate? (19 Aug '17, 21:53) meooow ♦6★ 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. (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 n-th fibonacci number. (23 Aug '17, 05:54) eugalt3★ showing 5 of 6 show all
 10 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 multi-dimensional dynamic programming as I want to improve myself on this topic. answered 18 Aug '17, 17:05 161●8 accept rate: 0% @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) divik5444★ 1 Yes, div 2 1000 level problems. (24 Aug '17, 20:44)
 8 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 $i-3$ won't affect the value of index $i$, because an operation can only affect three indices at max. However, the operations made at indices $i-1$ and $i-2$ 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 2.5k●53●137●170 accept rate: 20% Hey praveen, can you help me ehre- https://discuss.codechef.com/questions/108350/can-somebody-help-me-debugging-this-code 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)
 2 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 2★devesh23 1●1 accept rate: 0%
 1 Editorial lacks clarity. A lot of things are unexplained. answered 28 Aug '17, 15:34 11●1 accept rate: 0%
 0 Access denied for all solutions. answered 18 Aug '17, 15:17 4★pish4 1 accept rate: 0% It is fixed now. (18 Aug '17, 15:50)
 0 Problem link is wrong bcoz you have mentioned CHEFA as code but it is CHEFFA plz rectify it answered 18 Aug '17, 15:20 4★divik544 525●1●1●10 accept rate: 10% seems correct to me. Please let me know if there is still some error. (18 Aug '17, 15:50) yes its correct now (20 Aug '17, 13:44) divik5444★
 0 not able to get the editorial solution. Some one please explain it? answered 18 Aug '17, 15:53 26 accept rate: 50% @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)
 0 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 799●7 accept rate: 16%
 0 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 21●1 accept rate: 0%
 0 I used two 2d arrays instead. https://www.codechef.com/viewsolution/14980893 answered 25 Aug '17, 19:22 4★yvetal_1 1●1 accept rate: 0%
 0 Access denied for author's,tester's and editorialist's code @dpraveen answered 05 Sep '17, 06:36 58●4 accept rate: 0%
 0 access denied to all the solutuion . also can't see the code of @dpraveen answered 05 Nov '17, 14:58 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,212
×1,722
×193
×14

question asked: 14 Aug '17, 08:59

question was seen: 4,585 times

last updated: 05 Nov '17, 14:58