10808 - Rational Resistors

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

Moderator: Board moderators

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Feb 18, 2005 1:05 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

Post by Destination Goa » Fri Feb 18, 2005 1:50 pm

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!

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Feb 18, 2005 2:32 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.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Wed Apr 05, 2006 9:13 am

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

Post by shanto86 » Mon Nov 06, 2006 12:28 pm

i am getting WA can any one plz post some cases?
Self judging is the best judging!

Post Reply

Return to “Volume 108 (10800-10899)”