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?!???
can you link editorials with questions It will be easy to search
Yes this is interesting, can you please elaborate?
yes its correct now