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

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

11271 - Lattice of Resistors

Post by baodog » Mon Sep 10, 2007 8:32 pm

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:

Post by sclo » Tue Sep 11, 2007 5:33 pm

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:

Post by turuthok » Tue Sep 11, 2007 8:38 pm

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:

Post by sclo » Tue Sep 11, 2007 8:48 pm

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

Post by baodog » Tue Sep 11, 2007 9:27 pm

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:

Post by sclo » Tue Sep 11, 2007 10:43 pm

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

Post by baodog » Tue Sep 11, 2007 11:17 pm

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:

Post by sclo » Wed Sep 12, 2007 4:14 am

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

Post by Robert Gerbicz » Fri Sep 14, 2007 5:38 pm

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

Post by baodog » Fri Sep 14, 2007 5:48 pm

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 :D ?

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

Re: 11271 - Lattice of Resistors

Post by DGBHS » Tue May 26, 2015 12:04 pm

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

Post by DGBHS » Tue May 26, 2015 12:06 pm

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

Post by DGBHS » Tue May 26, 2015 12:28 pm

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

Post Reply

Return to “Volume 112 (11200-11299)”