Editorial for Baltic OI '18 P4 - Alternating Current

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.

Subtask 1

There are only $2^M$ ~2^M~ wirings, so when $M \le 15$ ~M \le 15~ we can simply try all of them and check if any wiring satisfies the constraints. To check a wiring, we can go through all wires in each direction separately and for each wire mark the segments that are covered by that wire. This yields an algorithm which runs in time $\mathcal O(2^M MN)$ ~\mathcal O(2^M MN)~.

Subtask 4

No wire passes through the separator between segments $1$ ~1~ and $N$ ~N~, so there is a natural order on wires, namely by starting point. We'll sort the wires according to this measure, and go through them one by one and assign their directions greedily.

When we see a wire, the choice is between assigning it clockwise and counter-clockwise direction. If the maximum ending point assigned to clockwise wires is greater than the maximum ending point assigned to counter-clockwise wires, then we are strictly better off assigning it a counter-clockwise direction, since clockwise and counter-clockwise directions are symmetrical. (Note that this symmetry comes from our common starting point.) Otherwise, we may assign it a clockwise wire. If we get any gaps, the answer is impossible, otherwise this greedy solution will work.

Subtask 5

The main observation is that if one wire $w$ ~w~ covers only a subset of the segments covered by another wire $w'$ ~w'~, then we can without loss of generality assign the direction of $w$ ~w~ to be opposite the direction of $w'$ ~w'~, because assigning the direction of $w$ ~w~ to be the same as the direction of $w'$ ~w'~ would accomplish nothing. Let us therefore assign parents to as many of the wires as possible, in such a way that:

If $w'$ ~w'~ is the parent of $w$ ~w~ then $w$ ~w~ covers a subset of the segments covered by $w'$ ~w'~.
A wire which is itself a parent has no parent.

By doing this we have partitioned the wires into two disjoint sets: The set of parents and the set of nodes that have a parent. From now on we will focus on the set of parents, which we denote by $\mathcal W$ ~\mathcal W~.

No wire $w$ ~w~ in $\mathcal W$ ~\mathcal W~ covers only a subset of the segments covered by any other wire $w'$ ~w'~ in $\mathcal W$ ~\mathcal W~, because if that were the case we could have let $w'$ ~w'~ be the parent of $w$ ~w~. Instead, the wires in $\mathcal W$ ~\mathcal W~ partially overlap or are completely disjoint.

Let us now sort the wires in $\mathcal W$ ~\mathcal W~ by increasing start segment, and let $w_1, \dots, w_k$ ~w_1, \dots, w_k~ be the sorted list of wires in $\mathcal W$ ~\mathcal W~. Let us now prove the following lemma:

Lemma 1. Suppose that $k$ ~k~ is even and that there is a valid wiring. Then we get a valid wiring by assigning the wires $w_1, w_3, w_5, \dots, w_{k-1}$ ~w_1, w_3, w_5, \dots, w_{k-1}~ in one direction and the wires $w_2, w_4, w_6, \dots, w_k$ ~w_2, w_4, w_6, \dots, w_k~ in the other direction.

Proof. Suppose, for the sake of contradiction, that there is some segment $s$ ~s~ which is not covered in both directions when the wires $w_1, w_3, w_5, \dots, w_{k-1}$ ~w_1, w_3, w_5, \dots, w_{k-1}~ are assigned in one direction and the wires $w_2, w_4, w_6, \dots, w_k$ ~w_2, w_4, w_6, \dots, w_k~ are assigned in the other. Since there exists a valid wiring, all segments must be covered by at least one wire in $\mathcal W$ ~\mathcal W~, so let us assume that $w_i$ ~w_i~ covers $s$ ~s~. If $w_{i-1}$ ~w_{i-1}~ or $w_{i+1}$ ~w_{i+1}~ covered $s$ ~s~ then $s$ ~s~ would be covered by wires in both directions, and therefore $w_i$ ~w_i~ must be the only wire in $\mathcal W$ ~\mathcal W~ that covers $s$ ~s~. This means that all other wires (not in $\mathcal W$ ~\mathcal W~) covering $s$ ~s~ must be children of $w_i$ ~w_i~, but then we would assign their directions to be opposite the direction of $w_i$ ~w_i~, so $s$ ~s~ is again covered by wires in both directions. □

Lemma 1 implies that in the case when $k$ ~k~ is even, we can simply use an alternating assignment to the wires $w_1, \dots, w_k$ ~w_1, \dots, w_k~ and then check whether that assignment is a valid one.

The case when $k$ ~k~ is odd is slightly harder. For this case we use the following lemma:

Lemma 2. Suppose that $k$ ~k~ is odd and that there is a valid wiring. Then there is an $i$ ~i~ such that we get a valid wiring if we assign the wires $w_i, w_{i+2}, w_{i+4}, \dots, w_{i-1}$ ~w_i, w_{i+2}, w_{i+4}, \dots, w_{i-1}~ in one direction and the wires $w_{i+1}, w_{i+3}, w_{i+5}, \dots, w_{i-2}$ in the other direction, where all indices are taken modulo $k$ ~k~.

Proof. Consider a valid wiring. Since $k$ ~k~ is odd there exists an $i$ ~i~ such that the valid wiring assigns the same direction to $w_{i-1}$ ~w_{i-1}~ and $w_i$ ~w_i~. We claim that we get a valid wiring if we assign the wires $w_i, w_{i+2}, w_{i+4}, \dots, w_{i-1}$ ~w_i, w_{i+2}, w_{i+4}, \dots, w_{i-1}~ in one direction and the wires $w_{i+1}, w_{i+3}, w_{i+5}, \dots, w_{i-2}$ in the other direction. Suppose for the sake of contradiction that there is some segment $s$ ~s~ which is not covered in both directions by this wiring. Since there exists a valid wiring, $s$ ~s~ must be covered by at least one wire $w_j$ ~w_j~ in $\mathcal W$ ~\mathcal W~.

Suppose that $s$ ~s~ is covered by $w_{i-1}$ ~w_{i-1}~ or $w_i$ ~w_i~. If $s$ ~s~ is also covered by $w_{i-2}$ ~w_{i-2}~ or $w_{i+1}$ ~w_{i+1}~ then $s$ ~s~ is covered by wires in both directions, so we can assume that $s$ ~s~ is not covered by $w_{i-2}$ ~w_{i-2}~ or $w_{i+1}$ ~w_{i+1}~. This means that all other wires containing $s$ ~s~ (not in $\mathcal W$ ~\mathcal W~) must be children of either $w_{i-1}$ ~w_{i-1}~ or $w_i$ ~w_i~, but then we would assign their directions to be opposite the directions we assign to $w_{i-1}$ ~w_{i-1}~ and $w_i$ ~w_i~, so $s$ ~s~ is again covered by wires in both directions.

Suppose that $s$ ~s~ is covered by some wire $w_j \in \mathcal W$ ~w_j \in \mathcal W~, for $j \notin \{i-1, i\}$ ~j \notin \{i-1, i\}~. If $w_{j-1}$ ~w_{j-1}~ or $w_{j+1}$ ~w_{j+1}~ also covered $s$ ~s~ then $s$ ~s~ would be covered by wires in both directions, so let's assume that $w_j$ ~w_j~ is the only wire in $\mathcal W$ ~\mathcal W~ that covers $s$ ~s~. Then all other wires covering $s$ ~s~ must be children of $w_j$ ~w_j~, which means that they are assigned directions opposite to the direction assigned to $w_j$ ~w_j~, so $s$ ~s~ is covered by wires in both directions. □

For subtask 3 it is sufficient to iterate through all possible values of $i$ ~i~ and check the resulting wiring for each. For subtask 5 we need to be more clever. A wiring that assigns the wires $w_i, w_{i+2}, \dots, w_{i-1}$ ~w_i, w_{i+2}, \dots, w_{i-1}~ in one direction and the wires $w_{i+1}, w_{i+3}, \dots, w_{i-2}$ ~w_{i+1}, w_{i+3}, \dots, w_{i-2}~ in the other direction is valid if and only if:

All segments are covered by at least one wire.
For all $j \notin \{i-1, i\}$ ~j \notin \{i-1, i\}~, the wires $w_{j-1}, w_j, w_{j+1}$ ~w_{j-1}, w_j, w_{j+1}~ and all their children together cover, in both directions, all the segments covered by $w_j$ ~w_j~.
The wires $w_{i-1}, w_i, w_{i+1}, w_{i+2}$ ~w_{i-1}, w_i, w_{i+1}, w_{i+2}~ and all their children together cover, in both directions, all the segments covered by $w_i$ ~w_i~ and $w_{i+1}$ ~w_{i+1}~.

The requirements 1 and 2 above are almost independent of the choice of $i$ ~i~ (except that we require $j \notin \{i-1, i\}$ ~j \notin \{i-1, i\}~), so when we change the value of $i$ ~i~ we only need to check if requirement 3 is satisfied, which can be done in amortized constant time over all choices of $i$ ~i~.

The time complexity of the algorithm is dominated by the process of finding parents of nodes and sorting the wires in $\mathcal W$ ~\mathcal W~, which takes time $\mathcal O(M \log M)$ ~\mathcal O(M \log M)~.

Comments

There are no comments at the moment.