Editorial for An Animal Contest 4 P5 - Neighbourly Neighbourhoods - Olympiads Online Judge

Editorial for An Animal Contest 4 P5 - Neighbourly Neighbourhoods

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.

Author: sjay05

In summary, this problem asks us to construct a directed graph of $N$ $N$ nodes with $M$ $M$ edges, such that there are $X$ $X$ SCC's (Strongly Connected Components) on the condition that $Q$ $Q$ pairs $(x_i, y_i)$ $(x_{i}, y_{i})$ belong to the same SCC.

Consider the edge types for a graph with $X$ $X$ SCCs:

Edges within an SCC. For an SCC consisting of $\alpha$ $α$ nodes (size $\alpha$ $α$ ), there are a maximum of $\alpha(\alpha-1)$ $α (α - 1)$ possible edges that can be formed.
Edges between SCCs. Consider all $\binom{X}{2}$ $(\binom{X}{2})$ pairs of SCCs. For an SCC with size $\alpha$ $α$ and another with size $\beta$ $β$ , $\alpha\beta$ $α β$ edges can be formed between them.

The next step involves choosing $X$ $X$ distinct SCCs:

Subtask 1

Since $Q = 0$ $Q = 0$ , we pick the $X$ $X$ SCCs to to be $\{1\}, \{2\}, \dots, \{X-1\}, \{X \dots N\}$ ${1}, {2}, \dots, {X - 1}, {X \dots N}$ . The size of the last SCC needs to be maximized, to maximize the number of edges that can be placed on the first condition listed above.

Subtask 2

Let $P$ $P$ be the maximum number of SCCs that can be created from the input. This can be finding the number of connected components of the $Q$ $Q$ constraints with a DSU. If $P < X$ $P < X$ , output -1. If $P > X$ $P > X$ , the largest $P-X+1$ $P - X + 1$ components (by size) must be considered as 1 SCC, to total $X$ $X$ SCCs. The "largest" are being considered to maximize the number of edges to be placed on the first condition listed above.

Let $sz[i]$ $s z [i]$ be the size of the $i$ $i$ -th SCC. For the $X$ $X$ SCCs considered, each requires a minimum of $sz[i]$ $s z [i]$ edges to satisfy the properties of an SCC, unless it is a single node. For example, if one set of nodes were $\{1, 2, \dots, k\}$ ${1, 2, \dots, k}$ , the edges formed would be $1 \to 2, 2 \to 3, \dots, k-1 \to k, k \to 1$ $1 \to 2, 2 \to 3, \dots, k - 1 \to k, k \to 1$ .

If $\sum sz[i] > M$ $\sum s z [i] > M$ , there are not enough edges to satisfy the constraint of $M$ $M$ edges, so output -1.

Finally if $\sum sz[i] < M$ $\sum s z [i] < M$ , for each SCC with size $sz[i]$ $s z [i]$ you can add $sz[i](sz[i]-1) - sz[i]$ $s z [i] (s z [i] - 1) - s z [i]$ more edges, and add edges between SCCs. Note that when constructing edges between SCCs, for each pair of SCCs (suppose SCC $a$ $a$ and SCC $b$ $b$ ), edges must only flow from a node in $a$ $a$ to a node in $b$ $b$ , or vice versa. Accounting for both directions will unite $a$ $a$ and $b$ $b$ as 1 SCC, which needs to be avoided.

At this point, if we have already reached our $M$ $M$ required edges, we can simply output them and terminate our program. If $M$ $M$ is still greater than the number of possible edges that can be added, output -1.

Time Complexity: $\mathcal{O}(N + Q \log N + M \log M)$ $O (N + Q \log N + M \log M)$

Comments

There are no comments at the moment.