Editorial for An Animal Contest 1 P5 - Odd Alpacas - Olympiads Online Judge

Editorial for An Animal Contest 1 P5 - Odd Alpacas

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: sjay05, samliu12

Subtask 1

We first observe that only the parity of an edge is relevant. Thus, the only relevant change we can make to a road is to change the parity of its length.

For the first subtask, we perform a graph search from each node $i$ $i$ , storing the results in a distance array and tallying the number of odd and even pathways. We repeat this step after changing the parity of each edge and track the minimum absolute difference.

Time Complexity: $\mathcal{O}(N^3)$ $O (N^{3})$

Subtask 2

Let us denote $dis(v)$ $d i s (v)$ to be the distance from the root village $1$ $1$ to $v$ $v$ .

The distance between any two nodes $a$ $a$ and $b$ $b$ in a tree can be formulated as $dis(a) + dis(b) - 2 \cdot dis(lca(a, b))$ $d i s (a) + d i s (b) - 2 \cdot d i s (l c a (a, b))$ where $lca(a, b)$ $l c a (a, b)$ is the lowest common ancestor of $a$ $a$ and $b$ $b$ .

Since $2 \cdot dis(lca(a, b))$ $2 \cdot d i s (l c a (a, b))$ is even, it does not affect the parity of the result, and the result is completely determined by the parity of $dis(a)$ $d i s (a)$ and $dis(b)$ $d i s (b)$ .

So, we perform a single DFS from an arbitrary root. To determine the number of odd pathways, we multiply the number of villages with an even distance by the number of villages with an odd distance. Complementary counting can be used to determine the number of even pathways.

We repeat this step after changing the parity of each edge and track the minimum absolute difference.

Time Complexity: $\mathcal{O}(N^2)$ $O (N^{2})$

Subtask 3

Let us define an "odd" node as an arbitrary village $v$ $v$ such that $dis(v) \equiv 1 \pmod 2$ $d i s (v) \equiv 1 (\mod 2)$ .

Similarly, an "even" node is an arbitrary village $v$ $v$ such that $dis(v) \equiv 0 \pmod 2$ $d i s (v) \equiv 0 (\mod 2)$ .

The number of "odd" and "even" nodes is used in the previous subtask to calculate the number of odd and even pathways in $\mathcal{O}(N)$ $O (N)$ time. Given the circumstances of subtask 3, for each modification, we must recalculate the number of odd and even pathways in constant time.

Suppose edge $(a, b)$ $(a, b)$ is to be modified (i.e. change its parity). Denote $x$ $x$ to be the node with lower depth among $a$ $a$ and $b$ $b$ . Then, it is easy to see that only the nodes in the subtree of $x$ $x$ will be affected by the edge modification. This is because for any path $(u, v)$ $(u, v)$ to intersect $(a, b)$ $(a, b)$ , either node $u$ $u$ or node $v$ $v$ must be in the subtree of $x$ $x$ .

Given this fact, all odd nodes in the subtree will become even nodes and vice versa. All that is left to do is keep track of the number of odd and even nodes in the subtree of each node $i$ $i$ , which can be computed recursively within the DFS function.

Time Complexity: $\mathcal{O}(N)$ $O (N)$

Comments

There are no comments at the moment.