Problem link is wrong bcoz you have mentioned CHEFA as code but it is CHEFFA plz rectify it
not able to get the editorial solution. Some one please explain it?
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.
12 Likes
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.
11 Likes
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.
How do we guarantee that (-50 ≤ deltapos,deltanxt ≤ 50) and also how do we conclude that dp[61][0][0] = 1.
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.
2 Likes
can someone provide a detailed explanation to it
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.
17 Likes
Editorial lacks clarity. A lot of things are unexplained.
1 Like
seems correct to me. Please let me know if there is still some error.
It is fixed now.
Hey praveen, can you help me ehre- Can somebody help me debugging this code? - help - CodeChef Discuss
I tried to use the similar approach, but I am getting WA and TLE.
how to prove that the max length is 60 ?
2 Likes
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?!???