For the first subtask, the bounds are small enough to permit a brute-force over all permutations of the available resistors, as there are at most resistors in total within the chains (or else the answer will definitely be no
).
To determine whether an arrangement is valid, consider the circuit as a graph where each resistor chain is a set of edges. Then for a resistor chain's placement to be valid, consider only those edges. They must form an Eulerian trail. The necessary and sufficient condition is that it forms a single connected component and there are either exactly zero or two nodes with odd degrees. This can be checked for each resistor chain in in total.
Time Complexity:
To solve the full task, consider when exactly it is possible to construct the circuit with given resistor chains. Again viewing the circuit as a graph, note that exactly of the nodes have odd degree. However, an Eulerian trail has at most two nodes with odd degrees while the rest have even degrees. So for nodes to have odd degrees in the union of the Eulerian trails, there must be at least Eulerian trails. So from this, we see that it is necessary for as well as the sum of the lengths to equal .
In fact, this is also sufficient. We will prove this with strong induction. It is important to keep in mind that the condition is equivalent to the sum being and the average of the lengths being at most .
Separate the chains into three sets : those with length , those with length , and those of length at least .
If , then we can construct the entire circuit. (This is motivated by considering .) Set aside chains of length at most and concatenate the remaining chains into one larger chain of length . Then with the concatenated chain, move through the leftmost edge of each row, starting from the bottom row. Then, for each chain of length set aside, move through the middle, then right once. Next, for each chain of length set aside, go right once. For example, if and the lengths (after setting aside and concatenation) are , the construction would be:
Note that this solves the second subtask.
If this is not the case, then consider an arbitrary chain from of length . Note that but We want to find an and a such that and and If this is possible, then we know by the previous case that we can use chains of length , chains of length , and this chain of length to reduce the circuit to a smaller . Simple algebra tells us that it is indeed possible as long as or there is an odd length in . Note that this is always the case for the third subtask, and so it solves it.
If none of the above conditions have been met, then we must have only chains of length and chains of even length at least . Additionally, . Consider two arbitrary chains from of length and . We have and and wish to find an where and It is easy to see that this is possible with . It only remains to construct a portion of the circuit with these chains so that we may reduce the circuit to a smaller . With the chain of length , place it around the leftmost middle edge so that the top row has edges with it and the bottom row has edges. Then with the other long chain, begin it at the leftmost node on the bottom, and have it go in a square wave pattern. For example, when , the construction is:
So all cases have been covered and by induction, the claim is proved.
Time Complexity:
Comments