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

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

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
  • Проголосовать: не нравится

»
9 лет назад, # |
← 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 :)

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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 ?

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← 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}.

      → Ответить
»
9 лет назад, # |
← 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 ?

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

    1 ≤ a, b ≤ 1018

    Your conclusion is obviously correct, but far from sufficient to solve this problem.

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

      How would you reduce the problem from a,b to something involving a,b,r,q where r and q are remainder and quotient?

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

        Assuming you're asking the case with a > b
        It's rather straightforward.

        Let me explain the intuitions. We have 2 equations: (1) R = Re + R0, (2)
        Notice equation (2) would yield results R < 1.
        This means if is greater than 1 and we decompose it into (where N >= 1 and M < 1), N has to come from equation (1).

        → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          You said "f(a, b) = a / b + f(a % b, a), if a > b"

          In that case f(5,2) = 2 + f(1, 5) = 2+5 = 7

          I think it should be f(a,b) = a/b + f(a%b, b)

          so that f(5,2) = 2 + f(1,2) = 2+2= 4

          f(1,x) = f(x,1)=x

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

    Hey thankyou :)

    → Ответить