CHEFFA - Editorial

[deadwing97]

PROBLEM LINK:

Practice
Contest

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 10⁹+7

DIFFICULTY:

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(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][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

[pish4]

Access denied for all solutions.

[divik544]

Problem link is wrong bcoz you have mentioned CHEFA as code but it is CHEFFA plz rectify it

[dpraveen]

seems correct to me. Please let me know if there is still some error.

[dpraveen]

It is fixed now.

[sharan_omkar]

not able to get the editorial solution. Some one please explain it?

[dpraveen]

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.

[dpraveen]

@sharan_omkar: I have written my idea below. Let me know if it makes sense!!

[underdog_eagle]

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.

[sandeep_007]

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.

[vijju123]

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.

[rksthegreat_1]

How do we guarantee that (-50 ≤ deltapos,deltanxt ≤ 50) and also how do we conclude that dp[61][0][0] = 1.

[devesh23]

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.

[aminuteman]

how to prove that the max length is 60 ?

[sharan_omkar]

@dpraveen thanks now it’s clear to me

[raj79]

can someone provide a detailed explanation to it

[r_64]

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.

[vijju123]

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

[akki28]

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

[meooow]

Yes this is interesting, can you please elaborate?