Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

hulk_baba's blog

By hulk_baba, 5 years ago,

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.

• +4

 » 5 years ago, # | ← Rev. 2 →   0 Don't know why I was downvoted (⌣̩̩́_⌣̩̩̀)
 » 5 years ago, # |   0 No help till now? Anyone please
•  » » 5 years ago, # ^ |   0 “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.
 » 5 years ago, # |   0 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
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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 ?
•  » » 5 years ago, # ^ |   0 I think i get it just this -> How did you came up c = n/((sqrt(5)+1)/2)?
 » 5 years ago, # |   0 still looking for it ...