Editorial for COI '19 #2 Pastiri

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.

Denote the nodes of the tree by $V$ ~V~. We will identify a sheep/shepherd with the node it occupies.

Notice that the task can be seen as an instance of the so called set cover problem: For every node $v \in V$ ~v \in V~, consider the set $S_v$ ~S_v~ of sheep which would be protected if we put a shepherd in node $v$ ~v~. Then we need to find the smallest subset $P \subseteq V$ ~P \subseteq V~ of nodes such that $\bigcup_{v \in P} S_v$ ~\bigcup_{v \in P} S_v~ equals the set of all sheep. The general set cover problem is NP-complete, but the specific tree structure here will help us to solve the problem in polynomial time.

Let's start with the first subtask, the case when the tree is a chain. A shepherd can protect only the first sheep to the left and/or to the right, so the family $\{S_v \mid v \in V\}$ ~\{S_v \mid v \in V\}~ contains the following subsets:

$\{x\}$ ~\{x\}~ for every sheep $x$ ~x~;
$\{x, y\}$ ~\{x, y\}~ for consecutive sheep $x, y$ ~x, y~ such that $x-y$ ~x-y~ is even.

We proceed with the following greedy algorithm: look at the first sheep. if the second one has the same parity, place a shepherd on the node halfway between them, otherwise place a shepherd in the same node as the first sheep. Next, remove the protected sheep and repeat the same algorithm. This solution has complexity $\mathcal O(N+K)$ ~\mathcal O(N+K)~.

To solve the second subtask, we make use of representing the subsets of sheep by bitmasks in $\{0, 1, \dots, 2^K-1\}$ ~\{0, 1, \dots, 2^K-1\}~. We first find the sets $S_v$ ~S_v~ for every node $v \in V$ ~v \in V~ in $\mathcal O(KN)$ ~\mathcal O(KN)~ by running breadth-first search from every sheep.

We can then solve this set cover instance by dynamic programming. For each bitmask $mask$ ~mask~, let $f(mask)$ ~f(mask)~ denote the minimum number of sets $S_v$ ~S_v~ which cover $mask$ ~mask~. We iterate through the states $mask$ ~mask~ in increasing order. When calculating $f(mask)$ ~f(mask)~, we iterate over all $submask \subseteq mask$ ~submask \subseteq mask~, and each time $submask$ ~submask~ corresponds to some of the sets $S_v$ ~S_v~, we recalculate $f(mask) := f(mask \mathbin{\text{XOR}} submask) + 1$ . To finish the transition, we put $f(submask) := f(mask)$ ~f(submask) := f(mask)~ for all $submask \subseteq mask$ ~submask \subseteq mask~.

Memory complexity is $\mathcal O(N+2^K)$ ~\mathcal O(N+2^K)~, and time complexity is $\mathcal O(KN+3^K)$ ~\mathcal O(KN+3^K)~. (We leave the proof as an exercise.)

For the remaining subtasks, we first pick an arbitrary node as the root. For each sheep $x$ ~x~, we will refer to the set $\{v \in V \mid x \in S_v\}$ ~\{v \in V \mid x \in S_v\}~ as its territory. We say that two sheep $x$ ~x~ and $y$ ~y~ are friends if their territories have a nonempty intersection. The main idea is to greedily place a shepherd that protects some sheep and all of the (currently) unprotected friends of that sheep. The following claim will help us with that:

Claim 1. For some sheep $x$ ~x~, let $a(x)$ ~a(x)~ be its highest ancestor that is in its territory. Then, $S_{a(x)}$ ~S_{a(x)}~ contains all friends of $x$ ~x~ that are not deeper than $x$ ~x~. Proof. Let $y$ ~y~ be a friend of $x$ ~x~ that is not deeper than $x$ ~x~. If $y$ ~y~ is in the subtree of $a(x)$ ~a(x)~, the claim is obvious, so assume the contrary. Take some node $z$ ~z~ that is not part of territories of $x$ ~x~ and $y$ ~y~, and let $w$ ~w~ be the midpoint of the path between $x$ ~x~ and $y$ ~y~. We have

$\displaystyle d(z, x) = d(z, y) = d(z, w)+d(w, x) = d(z, w)+d(w, y)$

where $d(u, v)$ ~d(u, v)~ denotes the distance between nodes $u$ ~u~ and $v$ ~v~. Also, for every sheep $t$ ~t~ it's true that

$\displaystyle d(z, w)+d(w, x) = d(z, x) \le d(z, t) \le d(z, w)+d(w, t)$

which implies $d(w, x) \le d(w, t)$ ~d(w, x) \le d(w, t)~, and $d(w, y) \le d(w, t)$ ~d(w, y) \le d(w, t)~ is proved analogously. Hence, $w$ ~w~ is contained in the intersection of territories of $x$ ~x~ and $y$ ~y~. Moreover, since $y$ ~y~ is not deeper than $x$ ~x~, $w$ ~w~ is an ancestor of $x$ ~x~, so it must be located on the path from $x$ ~x~ to $a(x)$ ~a(x)~. Since $y$ ~y~ is not contained in the subtree of $a(x)$ ~a(x)~, we have

$\displaystyle d(a(x), y) \le d(w, y) = d(w, x) \le d(a(x), x)$

so a shepherd in $a(x)$ ~a(x)~ protects $y$ ~y~, as needed. □

According to Claim 1, the following algorithm is correct:

Repeat until all sheep are protected:
- Place a shepherd in $a(x)$ ~a(x)~, where $x$ ~x~ is (one of) the deepest currently unprotected sheep.

The straightforward implementation in the complexity $\mathcal O(N(N+K))$ ~\mathcal O(N(N+K))~, is sufficient to solve the third subtask. To solve the fourth subtask, we need to speed up the algorithm. For each node $v$ ~v~, let $dep(v)$ ~dep(v)~ and $dist(v)$ ~dist(v)~ denote the depth of the node and the distance to the closest sheep, respectively. We can calculate $dist$ ~dist~ by running a BFS starting from each sheep. Alternatively, we can imagine that we added a dummy node connected to all the sheep and run the BFS starting in that node. The following fact will help us to efficiently determine $a(x)$ ~a(x)~ for each sheep $x$ ~x~:

Observation 2. If $v$ ~v~ is an ancestor of $x$ ~x~, then $dist(v) \le dep(x)-dep(v)$ ~dist(v) \le dep(x)-dep(v)~, where equality is attained if and only if $v$ ~v~ is in the territory of $x$ ~x~.

Due to the above, $a(x)$ ~a(x)~ is the index of first maximum of $dist(v)+dep(v)$ ~dist(v)+dep(v)~ over all $v$ ~v~ on the path from the root to $x$ ~x~. Thus we can calculate $a(x)$ ~a(x)~ for each sheep $x$ ~x~ by a simple depth-first search from the root.

The only thing left is maintaining the deepest unprotected sheep efficiently.

If we sort the sheep by decreasing depth, we can reduce this problem to maintaining the set of protected sheep.

Consider the directed graph $G$ ~G~ with the same vertex set $V$ ~V~ as the given tree, and with edges $(u, v)$ ~(u, v)~, where $\{u, v\}$ ~\{u, v\}~ is an edge from the given tree such that $dist(v) = dist(u)+1$ ~dist(v) = dist(u)+1~.

Observation 3. For each node $v \in V$ ~v \in V~, $S_v$ ~S_v~ is exactly the set of sheep $x$ ~x~ such that there exists a path in $G$ ~G~ from $x$ ~x~ to $v$ ~v~.

Whenever we place a new shepherd, we can run a DFS from that node following edges of $G$ ~G~ backwards, ignoring the nodes that were already visited. According to Observation 3, sheep is protected if and only if it was visited by the DFS. Since each node is visited at most once, the complexity of this part is linear.

Complexity of the solution is $\mathcal O(N + K \log K)$ ~\mathcal O(N + K \log K)~. Notice that the factor $\log K$ ~\log K~ comes from sorting the sheep by depth, which is of course possible to do with complexity $\mathcal O(N+K)$ ~\mathcal O(N+K)~ because the depths are at most $N$ ~N~. Therefore it's possible to solve the task in linear complexity.

Comments

There are no comments at the moment.