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.

Don't know why I was downvoted (⌣̩̩́_⌣̩̩̀)

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

Sadly could not understand your whole solution but I can relate it with something like Water Jug problem. Exhaustively search all the states being lead to from current and check for final states? Is it so ?

I think i get it just this -> How did you came up c = n/((sqrt(5)+1)/2)?

still looking for it ...