RESIST - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

This problem may look scary at first to someone who haven’t seen electrical resistors before, but the basic things needed to solve are explained in the problem statement. Seeing the figures for N = 1, 2 and the low constraint on N, hints a recursive ( or iterative ) approach. Suppose we have found the resistance at the left ends of a circuit with (N-1) blocks, say P. Adding one more block at its left ends means, the horizontal Resistor (R=1) and P are in series and so Q = 1 + P, and the vertical resistor (R=1) and Q are in parallel, so the equivalent resistance is (1xQ)/(1+Q). We need to find the numerator and denominator, so we maintain them separately and update. What about reducing to lowest terms, modulo ?

Lets check the answers for N = 1, 2, 3, 4, … its 1/1 , 2/3 , 5/8, 13/21, … whoa! its fibonacci numbers :slight_smile: If for circuit with (N-1) blocks the answer is A/B, then for N blocks its (1+A/B) / (1+1+A/B) = (A+B) / (B + (A+B)) and so the fibonacci series. Considering F(n) as the nth fibonacci number and F(0) = 0, F(1) = 1 the answer we need is simply F(2n-1) / F(2n). Also, we need not worry about reducing to lowest terms, as the gcd of two adjacent fibonacci numbers = 1 ( try euclidean method !) This can be solved now using a simple iteration in time O(n). There is a O(log n) method using matrix exponentiation, but its not needed here, as the constraints are small.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

4 Likes
2

![alt text][1]

after every circuit p/q gets new p/q, which is equal to p=p+q, and q=p+2q;
q=p+2q=p+q+q can be equal to q=p+q after assigning p=p+q;
[1]: http://discuss.codechef.com/upfiles/resist_01.jpg

3

I read your editorial but was still getting TLE in python with the O(n) solution, even with mod inside:

a=1
b=1
for i in xrange(2*(N-1)):
	c = a
	a = b
	b = (c+b) % M
print(str(a%M)+"/"+str(b%M))

so I followed the matrix exponentiation link, implemented it in code and still got TLE, then I put a mod inside the multiplication and it became super fast, even for N=1000000. Got AC with 0.66 seconds :slight_smile:

http://www.codechef.com/viewsolution/3793319