UVa 11271

From Algorithmist
Jump to navigation Jump to search

11271 - Lattice of resistors[edit]

Summary[edit]

Given an infinite square lattice of resistors, you are asked to find the resistance between any two points (one of them is fixed at the origin without loss of generality).

Explanation[edit]

There is an analytic formula for the resistance R(i, j) that involves an awfully looking double integral. Obviously, numerical integration is out of question. One can easily derive the recurrence relation for R(i, j)[1]. Its direct bottom-up evaluation becomes numerically unstable if i and j are above 20 or so. Even if we could circumvent this instability, according to the problem statement i and j can be as large as 264 – 1.

Now we should think about this problem from a physical point of view. When i and j are large, we no longer have a lattice but a uniform media, and the resistance should depend only on the distance from the point (i, j) to the origin. Indeed, there exists an asymptotic expression of the form R(i, j) ∼ 1/π log(i2 + j2) + b[1]. Recall that we are asked only for 3 digits of precision, hence we hope that asymptotic expression should become valid not too far from the origin. It can easily be checked that for i and j above 18 or so the asymptotic formula is accurate enough. This boundary also ensures that straightforward bottom-up evaluation of recurrences for small i and j will not suffer numerical instabilities.

Notes[edit]

At the present time, both UVa online judge and uDebug have incorrect solutions. Values of R(i, j) can be calculated using symbolic evaluation of the integral. The answer is always of the form r + s / π for some rational r and s, and can easily be evaluated to any given precision (4 digits would be enough). UVa and uDebug disagree at least in one point. Finding these "corner cases" is up to the reader.

Solutions[edit]

C++: 11271_lattice_of_resistors.cpp

References[edit]

<references>

  1. 1.0 1.1 Pozrikidis C. An Introduction to Grids, Graphs, and Networks