## 11271 - Lattice of Resistors

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### 11271 - Lattice of Resistors

Note that R(a,b)=R(b,a).

Also handle negative coordinateswith symmetry.

With some clever manipulation you
can get the following recurrence relationship:

Code: Select all

``````a,b non-negative.
R(a,b) the resistance is (a>=b):
if b=0 ->  4*R(a-1,0)-R(a-2,0)-2*R(a-1,1)
else if a=b -> (4*(a-1)*R(a-1,a-1)-(2*(a-1)-1)*R(a-2,a-2))/(2*(a-1)+1)
else if a=b+1 -> 2*R(b,b)-R(b,b-1);
otherwise -> 4*R(a-1,b)-R(a-2,b)-R(a-1,b+1)-R(a-1,b-1)

Base Cases are:
R(0,0)=0
R(1,0)=0.5
R(0,1)=0.5
R(1,1)=2/pi
``````
Of course, you have to figure out how to compute this really fast and
accurate to 3 decimal places or more.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
Since I'm not an electrical engineer, I don't really know how to derive those equations, but I want to see if I can derive them first.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
I think this is one of the problems most (if not all) coders should avoid to even try during a running contest.

It's either you know it, or you don't (that's where Google comes into picture).

Of course, we need to see if we can understand and solve it offline. I even found a PDF containing the a closed-form formula involving complex calculus.

Tough problemset for me.
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
I found that the recurrence relation is quite unstable. I actually got negative answer for values as small as (24,0)

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am
For (24,0),
my program outputs 1.526

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
I got negative number for (24,0) using just the recurrence from above.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am
Don't apply the recursion directly ...
you get accumulation of numerical error, resulting in negative numbers. There are some additional tricks to get this to work.
btw, the alternative solution uses numerical integration.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
I'll try with numerical integration. It's going to be too slow anyway.
I'm computing a 2d integral using simpson's approximation.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### Re: 11271 Hint (Spoiler warning ...)

baodog wrote:Note that R(a,b)=R(b,a).

Also handle negative coordinateswith symmetry.
From your problem statement:

Code: Select all

``All values will fit inside an unsigned 64 bit integer.``

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### No negative inputs..

There are actually no negative inputs in the dataset.
You can check if you want.

However, -6 does fit inside an unsigned 64 bit integer.
How many bits does -6 take up ?

DGBHS
New poster
Posts: 7
Joined: Tue May 26, 2015 11:58 am

### Re: 11271 - Lattice of Resistors

i have got some integral formula in this page ... http://www.mathpages.com/home/kmath668/kmath668.htm
is it usable ? this problem seems one of the hardest problem i ever seen.

DGBHS
New poster
Posts: 7
Joined: Tue May 26, 2015 11:58 am

### Re: 11271 - Lattice of Resistors

and is there any solution without recursion?

DGBHS
New poster
Posts: 7
Joined: Tue May 26, 2015 11:58 am

### Re: 11271 - Lattice of Resistors

i got this function
(1-e^(-abs(n*(log(e, (2-cosx+sqrt(3-4cosx+cosx^2))))))*cos(px))/(sinh(abs(log(e, (2-cosx+sqrt(3-4cosx+cosx^2))))))

will it work?
the solution of the integration of the function is
csch(abs(log(-cos(x)+sqrt(cos^2(x)-4 cos(x)+3)+2))) (1-cos(p x) exp(-abs(n log(-cos(x)+sqrt(cos^2(x)-4 cos(x)+3)+2))))

but it does not give the correct solution .

I just got mad with this problem 