## 10808 - Rational Resistors

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Destination Goa wrote:What's the reason of O((m+n)^2) = O(n^4) solution if basic approach works at O(n^3)?
O((m+n)^2) =?= O(n^4) ?? I don't think so
Actually the method Christian describes is O((n+m)^3).
Destination Goa wrote:Joey,
If you set x as potential in some cell, then parallel resistors are eliminated automatically during building matrix A (otherwise you'll get WA).

Yes, but you build an entirely different matrix by this approach, and no resistors are eliminated automaticly.

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
What is m? Number of resistors? If so, then m = O(n^2).

About auto-elimination. Do you mean eliminating resistors connecting same pair nodes or something else? I think we talk about different solutions here.

Mine is: let x[1]...x[N] be potentials of N nodes. c[1]...c[N] is current excess (0 for all, except +1 for source and -1 for destination). Equation system is X*A=C.

Initially A is all zeroes. Then, for each resistor R connecting V1;V2

a[v1][v2] += 1/r;
a[v1][v1] -= 1/r;

a[v2][v1] += 1/r;
a[v2][v2] -= 1/r;

So, this is O(m+n^3) solution (n - number of nodes, m - number of resistors), and it sums duplicate resistors automatically. Actually, it stores sum(1/R1+1/R2+...+1/Rk) for each pair (v1;v2) where resistors R1...Rk connect this pair in either direction.
To be the best you must become the best!

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Destination Goa wrote:What is m? Number of resistors? If so, then m = O(n^2).
Aha. Ok I see it, sorry.
Destination Goa wrote:About auto-elimination. Do you mean eliminating resistors connecting same pair nodes or something else? I think we talk about different solutions here.
That was were I was talking about. The method Christian describes (and which I implemented) _is_ completely different from the method you describe. And the things I descibed were applying to this other method, not yours.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
I've just got AC, but I still have a question about the problem.

I use long long and can easily construct test case to make my AC-code fail:

Code: Select all

``````1
6 15
0 1 1
0 2 2
1 2 9
0 3 3
1 3 1
2 3 4
0 4 9
1 4 5
2 4 1
3 4 6
0 5 9
1 5 7
2 5 1
3 5 8
4 5 9
15
0 1
0 2
1 2
0 3
1 3
2 3
0 4
1 4
2 4
3 4
0 5
1 5
2 5
3 5
4 5``````
It's merely a complete graph of 6 nodes with arbitary values on all edges. So I want ask whether other solver (with long long) can produce correct output for this case. Is it my luck to get AC?

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
i am getting WA can any one plz post some cases?
Self judging is the best judging!