Judging the Southeast Region

This problem was solved later in the contest, and by fewer teams, than we thought it would be. The main algorithm is straightforward, but some special cases are tricky.

First, if you have resistors from P to Q and from Q to R (and no others with Q as an endpoint) then they are in series, and you can reduce them to a single resistor between P and R. However, if the middle node is one of the endpoints A or Z (e.g. P to A to R, or P to Z to R), then you can’t. Because A and Z are the start/end points, they each have an extra connection.

Second, at the end, you’ve got to make sure there’s a single resistor between A and Z, and none anywhere else. If you end up at the end with a resistor between A and Z, and another one between P and Q, that system is NOT well formed!

Here is the Judge Input, the Judge Output, the main Solving Program, and another in Java, and one in C++.

Look below for an outline of a solution.

[spoiler]

First create two arrays – a 1d array of nodes, and a 2d array of resistances between nodes. The 1d array will hold a count of the number of resistors which are connected to that node. The 2d array will hold resistances, or some sentinel value (like -1.0) if there’s no resistor between those nodes.

Now, write a method which will place a resistor into the circuit, something like place( int i, int j, double r). if there is no resistor between i and j (resistance[i][j]<0.0) then just increment nodes[i], increment nodes[j], resistance[i][j]=resistance[j][i]=r. If there’s already a resistor there, then leave nodes[i] and nodes[j] alone, and merge this new resistor with the one that’s already there using the Parallel rule. You can use this method whenever tyou place a resistor into the circuit – reading them in, or later in the algorithm. This’ll take care of all parallel resistors!

Now, let’s look for resistors in series. That’s easy – just look for a node i (skipping A and Z) such that nodes[i]==2. If a node has exactly two resistors connected, then it has to be the center node of two resistors in series! Don’t forget to exclude A and Z. Once you find one (let’s call it Q), you can look through the resistance[][] array to find which two other nodes (let’s call them P and R) are connected and the resistance between them. Then, just set resistance[P][Q]=resistance[Q][P]=-1.0, resistance[Q][R]=resistance[R][Q]=-1.0, resistance[P][R]=resistance[R][P]=(use the Series rule), and nodes[q]=0. Just keep doing this until there are no more nodes with nodes[i]==2.

Once there are no more resistors in series, then check to see if this system is well-formed. See if it reduced to a single resistor between A and Z. Check to see if nodes[A]==1, nodes[Z]==1, and nodes[P]==0 for every other node (that last part was forgotten by a lot of teams!)

[/spoiler]