Please go through this problem (some may have difficulty accessing it). I tried to solve this problem by doing the following: 1. Since the answer is bound to come in 60 steps. If I calculate the minimum moves to reach the answer then I am done. 2. so I thought First try, anew = a+b and ask for solution (anew,b,n-anew), and then try bnew = a+b and ask for solution of (a,bnew,n-bnew) . Then I will store the solution whichever gives me minimum steps; 3.Since three elements are forming the state of DP memoizing becomes messy and difficult to construct the actual solution. 4. I tried hard to implement but could not pass even simple test case 5. I also found it difficult to write base cases for recursion.
I wish to know how you approach such DP problems? If there are other solutions to the problem, I would be happy to know their approaches too. Please help me with this.
No help till now? Anyone please
“Help will always be given at Codeforces to those who ask for it.”
just be patient. I will surely notify you if i come up with an efficient solution.
WLOG, let's assume that final_a>=final_b => n = final_a => n=last_but_one_a+final_b. We are given n. So, the solution is simply to try various final_b, run a simple loop starting from a=n-final_b, b=final_b(if b>a subtract a from b else vice versa — this directly gives the string).
Note, we if choose a bad final_b(like n-1) then the string length > 60. Since, the operations are similar to fibonacci choosing a final_b near c=n/((sqrt(5)+1)/2) is guaranteed to work. Try various final_b near c.
For implementation details checkout a similar solution