Editorial :: z-ohms

I will post different solutions for this problem as soon as the competition is over.

I will explain three possible solutions.

First, you could see that the number of test cases is limited, hence you could precompute all the solutions, and just output the corresponding one.

However, the time limit was set so that the problem can be even solved real time, with some more advanced numerical math knowledge, this is solution 3.

As I mentioned in the problem, and in the hints, it is enough to know only few basic physics formulas. IR = \Delta V and KCL rule.

Now, the first solution is as following: we set the node A to be on potential V = 1, and the node B to have V = -1. Also we see that the problem is symmetric along both diagonals. Now, if we know the current going through all the resistors, we can easily recover the total resistance.

So here we have to setup a system of equations, for each node we will have that all the incoming current equals all the outgoing current, and we have Va = 1 and Vb = -1. This will be a linear system of equations that can be easily solved, and we would obtain all the Voltages in the grid.

Having all the voltages we can find the current going out of Va (V[1,1]), it will be equal to 2*(V[2,1]-V[1,1])/1 = since the problem is symmetric, and the resistors are 1ohm.

This current is now equal to the total current going from Va to Vb, hence the total resistance is:

R_{tot} = -\frac{1 - (-1)}{2(V_{2,1} - V_{1,1})} = \frac{1}{V_{1,1} - V_{2,1}}

Second solution relies on the same idea. But instead of solving the system of equation, we apply numerical method to find the voltages.

We set
V^1_{1,1} = 1
V^1_{N,N} = -1

And all other voltages to zero (or random values between zero and 1).

Now we do the following iterations:

V^k_{1,1} = 1
V^k_{N,N} = -1
V^k_{a,n} = avg(V^{k-1}_{a-1,n}, V^{k-1}_{a+1,n},V^{k-1}_{a,n-1},V^{k-1}_{a,n+1})

Where we have to take care of the edge cases (nodes that do not have four neighbours).

Once the voltages converged to a desired precision (successive iterations do not change the voltages) we can find total resistance as in previous solution

The two solutions above get slower as N increases, however there is a way to solve the problem for larger N.

I will not prove this (will require some space and time) but the idea is the following:

- We calculate the resistance for some smaller values of [[N]], for example for N = 8,10,12,14,16,18,20 and 24 (total 8 values).

-Then we want to represent the total resistance as the following function:

R_N = \frac{4}{\pi} ln(N) + \sum_{i=1}^8 \frac{C_i}{N^{2i}}

With the 8 known values we can find the 8 coefficients C. After that we apply the obtained formula to get R(N) for arbitrary N.

well u dont need to even calculate voltages...this task can be solved with DP only u need to be good at this field of physics and it will be faster than those 2 solutions but idk where from u got that third formula...will try to get it myself:D

I have not succeeded using the interpolation function which gave admin. I used a small modification:

R_N \cong \frac{4}{\pi}ln(N) + \sum_{i=0}^{12}\frac{C_i}{N^{i-1}}

halil what does i output for 5 and 6?
and how did u come up with that formula?

well for n=4 i also get that result but these 2 dont match...

well i calculated for n=5 manually and i got 2.147... and thats the same result my algorithm gives.i reckon that the test cases were made for that approximation algorithm and that those are approximate values.