Rational Resistance - 343 A

https://codeforces.com/problemset/problem/343/A

Simplified Problem Statement

With the standard law of resistance in a circuit (serial is r1+r2 and parallel is 1/(1/r1 + 1/r2)), determine the smallest possible number of unit resistor to create an equivalent resistance of irreducible fraction a/b.

Constraint

a, b <= 10^18

Analysis

For very large a, it doesn’t matter that much that the value is large because what we need is to only write the value. Maybe if we can simplify the question to if we can create 1/b? This is easier since we need to have b resistor, assign them in parallel. Then get a of this, hence we can get an assignment of a/b with a*b number of resistor, which certainly is not the optimal (minimum) way.

Let us take an example first I guess. I think using a notation would help. + For serial, | for parallel

• 1/2 is o|o
• 2/3 can be created by (o|o|o) + (o|o|o), or by o|o + o|o|o|o|o|o, or by (o+o) | o.

I think for if a/b > 1, having a series of x resistor such that the a/b - x < 1 is the best way to do? It might not always be true. For example if we have 4/3, not sure if 1 + 1/3 is better of 2/3 + 2/3 is better. Although in that specific case, 1 + 1/3 use 4 resistor, meanwhile 2/3 + 2/3 uses 6.

Let us maybe see the other example from the test case, which is 199/200. The test case provided the answer as 200. We will need 1/(200/199). Which is available by? Let’s look at the 200/199, it is 1/199 + 1. What if I want 199/201? Surely there’s a better way then doing 1/199 + 1/199 + 1.

Stop stop! I see something insightful. If we flip a/b, all the operation will flip and will give the same result. E.g.:

• 2/3 is (o+o) | o
• 3/2 is (o|o) + o.
• 199/200 is (o+o+...+o) | o
• 200/199 is (o|o|...|o) + o

Maybe I can think of the proof later, but this seems to be promising. In this case, what we can do is to keep flipping such that when the value of the equation is > 1, we reduce the numerator with the denumerator. I think we can code this.

Implementation

int main() {
        setIO();
        ll a; ll b; re(a, b);
        ll count = 0;
        while(a != 0 && b != 0){
                if(a < b){
                        ll tmp = b;
                        b = a; a = tmp;
                }
                count += a/b;
                a %= b;
        }
        ps(count);
        // you should actually read the stuff at the bottom
}

Accepted!