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
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.
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.
1 Like
“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?