antivenom's blog

Some Direction needed :/
By antivenom, history, 9 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
9 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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 :)

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

    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 ?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ?

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

    1 ≤ a, b ≤ 1018

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

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

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

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

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

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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

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

            You're right. Made a typo there.
            Thanks for pointing that out :)

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

    Hey thankyou :)

    → Reply