Author: Dmytro Berezin
Tester: Prateek Gupta
Editorialist: Hussain Kara Fallah
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
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
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 = 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