hulk_baba's blog

By hulk_baba, 8 years ago, In English

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.

Tags #dp
  • Vote: I like it
  • +4
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

No help till now? Anyone please

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    “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.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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