Editorial for DMOPC '18 Contest 4 P6 - Dr. Henri and Resistor Chains


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: r3mark

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 3N 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 a 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 \mathcal{O}(N) in total.

Time Complexity: \mathcal{O}(N\cdot (3N)!)

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 2N of the nodes have odd degree. However, a Eulerian trail has at most two nodes with odd degrees while the rest have even degrees. So for 2N nodes to have odd degrees in the union of the Eulerian trails, there must be at least N Eulerian trails. So from this, we see that it is necessary for M\geq N as well as the sum of the lengths to equal 3N.

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 3N and the average of the lengths being at most 3.

Separate the M chains into three sets S_1, S_2, S_3: those with length 1, those with length 2, and those of length at least 3.

If |S_1|+|S_2| \ge N-1, then we can construct the entire circuit. (This is motivated by considering M=N.) Set aside N-1 chains of length at most 2 and concatenate the remaining M-N+1 chains into one larger chain of length k\ge 3. Then with the concatenated chain, move through the leftmost edge of each row, starting from the bottom row. Then, for each chain of length 1 set aside, move through the middle, then right once. Next, for each chain of length 2 set aside, go right once. For example, if N=6 and the lengths (after setting aside and concatenation) are 11, 1, 1, 1, 2, 2, the construction would be:

Case 1

Note that this solves the second subtask.

If this is not the case, then consider an arbitrary chain from S_3 of length k. Note that \frac{k}{1}\ge 3 but \displaystyle \frac{k+|S_1|+2|S_2|}{1+|S_1|+|S_2|}\le 3. We want to find an a and a b such that 0\le a\le S_1 and 0\le b\le S_2 and \displaystyle \frac{k+a+2b}{1+a+b} = 3. If this is possible, then we know by the previous case that we can use a chains of length 1, b chains of length 2, and this chain of length k to reduce the circuit to a smaller N. Simple algebra tells us that it is indeed possible as long as |S_2|\ge 1 or there is an odd length in S_3. 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 1 and chains of even length at least 4. Additionally, |S_3|\ge 2. Consider two arbitrary chains from S_3 of length 2j and 2k. We have \frac{2j+2k}{2}\ge 3 and \frac{2j+2k+|S_1|}{1+1+|S_1|}\le 3 and wish to find an a where 0\le a\le |S_1| and \displaystyle \frac{2j+2k+a}{1+1+a}=3. It is easy to see that this is possible with a=j+k-3. It only remains to construct a portion of the circuit with these chains so that we may reduce the circuit to a smaller N. With the chain of length 2j, place it around the leftmost middle edge so that the top row has j-1 edges with it and the bottom row has j edges. Then with the other long chain, begin it at the j^{\text{th}} leftmost node on the bottom, and have it go in a square wave pattern. For example, when j=3, k=4, a=4, the construction is:

Case 2

So all cases have been covered and by induction, the claim is proved.

Time Complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.