Блог пользователя antivenom

Some Direction needed :/
Автор antivenom, история, 11 лет назад, По-английски

Hi everyone,I am learning Graphs for few days so every question looks graph to me.I tried this question and thought of graph(bfs) but for some reason it is running indefinitely.Any help appreciated :).Link solution

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, скрыть # |
← Rev. 5  
Проголосовать: нравится 0 Проголосовать: не нравится

It's not a graph problem, but a math problem rather.

Consider f(a, b):

  1. f(a, b) = a / b + f(a % b, b), if a > b
  2. if a < b
    Solve
    => , which reduces the problem to f(a, b — a)
    which then leads us to f(a, b % a)
    f(a, b) = f(a, b % a) + b / a, if a < b
  3. Special case comes when a = 1, but it should be trivial to see the answer.

-

By the way, I like this problem. Thank you for pointing me to it :)

→ Ответить
  • »
    »
    11 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Hi :) Thanks for answer.Let me explain my approach to you,possibly you can tell what's wrong with it.I started with resistance one and everytime I add a resistance in parallel and add another in parallel(doing something like s*1/(s+1)(parallel) and (s+1) series) and like this I am extending bfs till I reach certain ratio which is provided in the question.My approach is very same like process in this question.Two buttons .How about my approach was that total rubbish ?

    → Ответить
    • »
      »
      »
      11 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится

      Your solution (the link you gave on the main post) doesn't check for collisions.

      For example, you will visit both 1 + 1/2 and 1/2 + 1 which shouldn't be necessary.

      Your solution is not rubbish. You are just relatively inexperienced :)
      The state space is simply way too large.
      Even if we're only concerned with integers, we're looking at a set with 1018 states {1, 2, ..., 1e18}.

      → Ответить
»
11 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Use induction on n.

Let us suppose we can say the minimum number of resistors that can give us (a/b).

Claim: We know the rational number when we try to increase the the resistors by 1 from a particular base rational number (a/b).

Since there are two ways to do this resulting in (a+b/b) and (a/(a+b)) by our induction hypothesis, we now know what the minimum number of resistors can be calculated from the answer of the base rationals number.

We conclude by saying that it is a minimum over two base rational numbers since in fact the resistor values can be arrived at in two ways.

f(a,b) = min. f(a-b, b), f(a,b-a) + 1 . a-b>=1 b-a>=1 wherever the case. f(1,x)=f(x,1)=x

But that is not fast enough due to constraints. We can however use the recurrence to find a better answer. Is there an efficient way to calculate f(a-b, b) faster ?

Maybe by using division algorithm a=b.q+r ?

→ Ответить