Editorial for DMOPC '21 Contest 4 P5 - Graph Generator

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: Riolku, X_Ray

Subtask 1

There are many different solutions for this subtask. One of them will be addressed here.

Observe that for each generation phase $K > 1$ ~K > 1~, we essentially add a bridge between a copy of the original graph $G$ ~G~ and the amalgamation of all previous generations. We can greedily build our answer for a generation phase $i$ ~i~ off of the answer for generation phase $i-1$ ~i-1~. In this case, let $G[i]$ ~G[i]~ be our graph after $i$ ~i~ generation phases, and let $g$ ~g~ be an active generator node. Here, let $d(u, v)$ ~d(u, v)~ be the distance of the shortest path between an unordered pair of nodes $u$ ~u~ and $v$ ~v~, and $G_u$ ~G_u~ means a node $u$ ~u~ that is a part of graph $G$ ~G~.

The sum of the shortest paths between all unordered pairs of nodes $\{u, v\}$ ~\{u, v\}~ after $i$ ~i~ generation phases = Sum of the shortest paths between all unordered pairs of nodes $\{u, v\}$ ~\{u, v\}~ such that both $u$ ~u~ and $v$ ~v~ are a part of the graph created after $i-1$ ~i-1~ generation phases + Sum of the shortest paths between all unordered pairs of nodes $\{u, v\}$ ~\{u, v\}~ such that both $u$ ~u~ and $v$ ~v~ are in the copy of the original graph + Sum of the shortest paths between all unordered pairs of nodes $\{u, v\}$ ~\{u, v\}~ such that $u$ ~u~ is a part of the graph created after $i-1$ ~i-1~ generation phases and $v$ ~v~ is a part of the copy of the original graph. Let these be known as terms $\{A, B, C\}$ ~\{A, B, C\}~ respectively. Term $A$ ~A~ is our previous solution, and term $B$ ~B~ can be precomputed. Term $C$ ~C~ can be easily calculated through simple combinatorics (left as an exercise to the reader).

$\displaystyle \begin{align*} \sum_{u \neq v}^{G[i]} d(G[i]_u, G[i]_v) &= \sum_u^{G[i-1]} \sum_v^G d(G[i-1]_u, G_v) + \sum_{u \neq v}^{G[i-1]} d(G[i-1]_u, G[i-1]_v) + \sum_{u \neq v}^G d(G_u, G_v) \\ &= \sum_u^{G[i-1]} \sum_v^G (d(G[i-1]_u, G[i-1]_g)+d(G_v, G_1)+1) + \sum_{u \neq v}^{G[i-1]} d(G[i-1]_u, G[i-1]_v) + \sum_{u \neq v}^G d(G_u, G_v) \\ &= \left(\sum_u^{G[i-1]} d(G[i-1]_u, G[i-1]_g)\right)N + \left(\sum_u^G d(G_u, G_1)\right)N(i-1)+N^2(i-1) + \sum_{u \neq v}^{G[i-1]} d(G[i-1]_u, G[i-1]_v) + \sum_{u \neq v}^G d(G_u, G_v) \end{align*}$

We can also greedily calculate the sum of all paths between the active generator node $g$ ~g~ and all other nodes in the graph, with a transition time of $\mathcal O(1)$ ~\mathcal O(1)~.

$\displaystyle \sum_u^{G[i]} d(G[i]_u, G[i]_g) = \sum_u^{G[i-1]} d(G[i-1]_u, G[i-1]_g) + d(G_u, G_1)N(i-1)+\sum_u^G d(G_u, G_g)$

We can precompute $\sum_u^G d(G_u, G_1)$ ~\sum_u^G d(G_u, G_1)~ and $\sum_u^G d(G_u, G_g)$ ~\sum_u^G d(G_u, G_g)~ in $\mathcal O((N+M)^2)$ ~\mathcal O((N+M)^2)~. As each transition takes $\mathcal O(1)$ ~\mathcal O(1)~ time, the total time complexity of the algorithm is $\mathcal O((N+M)^2+K)$ ~\mathcal O((N+M)^2+K)~.

Time Complexity: $\mathcal O((N+M)^2+K)$ ~\mathcal O((N+M)^2+K)~

Subtask 2

Observe that graph $G$ ~G~ is now a complete graph. We can express the graph after $K$ ~K~ generations as a $K$ ~K~ layered $L$ ~L~-nary tree of graphs $G$ ~G~, where $L$ ~L~ is the number of generator nodes in graph $G$ ~G~. The distance between any two nodes on two graphs $a, b$ ~a, b~ can be easily calculated in $\mathcal O(1)$ ~\mathcal O(1)~ using the graph $\text{LCA}(a, b)$ ~\text{LCA}(a, b)~.

Iterating through all pairs of graphs $\{a, b\}$ ~\{a, b\}~ would inevitably exceed the time limit. However, it is observed that the distance between two graphs after $K$ ~K~ generation phases is at most $2(K-1)$ ~2(K-1)~. We can thus use Combinatorics to compute the answer in $\mathcal O(K)$ ~\mathcal O(K)~.

Time Complexity: $\mathcal O(K)$ ~\mathcal O(K)~

Subtask 3

There are a few full solutions. One of them will be addressed here.

First, we should change our way of thinking. For each generation phase, rather than imagining a copy of graph $G$ ~G~ being attached to each of the $L^{i-1}$ ~L^{i-1}~ active generator nodes in the $i$ ~i~th generation phase, we can imagine one copy of graph $G[i-1]$ ~G[i-1]~ being attached to each of the $L$ ~L~ generator nodes in a graph $G$ ~G~ with their bottommost node 1. Thus, we can do something broadly similar to Subtask 1. Here, $G_x[i-1]$ ~G_x[i-1]~ means the $x$ ~x~th copy of graph $G[i-1]$ ~G[i-1]~, and $gu$ ~gu~ means a generator node $u$ ~u~. Simply put, the sum of the shortest paths between all unordered pairs of nodes $\{u, v\}$ ~\{u, v\}~ after $i$ ~i~ generation phases = Sum of shortest paths between all unordered pairs of nodes such that both nodes are in the same copy of graph $G[i-1]$ ~G[i-1]~ + Sum of shortest paths between all unordered pairs of nodes such that both nodes are in the copy of $G$ ~G~ + Sum of shortest paths between all unordered pairs of nodes such that both nodes are in different copies of graph $G[i-1]$ ~G[i-1]~ + Sum of shortest paths between all unordered pairs of nodes such that one node is in a copy of graph $G[i-1]$ ~G[i-1]~ and the other is in the copy of $G$ ~G~. Let these be known as terms $\{A, B, C, D\}$ ~\{A, B, C, D\}~ respectively.

$\displaystyle \sum_{u \neq v}^{G[i]} d(G[i]_u, G[i]_v) = \sum_{u \neq v}^G d(G_u, G_v) + \left(\sum_{u \neq v}^{G[i-1]} d(G[i-1]_u, G[i-1]_v)\right)L + \sum_{x=1}^L \sum_{y=x+1}^L \left(\sum_u^{G_x[i-1]} \sum_v^{G_y[i-1]} d(G_x[i-1]_u, G_y[i-1]_v)\right) + \sum_{x=1}^L \left(\sum_u^{G_x[i-1]} \sum_v^G d(G_x[i-1]_u, G_v)\right)$

Terms $A$ ~A~ can be quickly precomputed, while term $B$ ~B~ is exactly our answer in the previous iteration. Calculating terms $C$ ~C~ and $D$ ~D~ may seem problematic to calculate, but they can be decomposed into more trivial calculations.

First, let us address Term $C$ ~C~, the sum of shortest paths between all unordered pairs of nodes such that both nodes are in different copies of graph $G[i-1]$ ~G[i-1]~. We can observe a similar phenomenon as in subtask 1, except we have $\frac{L(L-1)}{2}$ ~\frac{L(L-1)}{2}~ possible bridges of varying lengths. Rather than repetitively performing the same calculations over and over again, we can efficiently combine the $\frac{L(L-1)}{2}$ ~\frac{L(L-1)}{2}~ calculations into one single calculation.

$\displaystyle \begin{align*} & \sum_{x=1}^L \sum_{y=x+1}^L \left(\sum_u^{G_x[i-1]} \sum_v^{G_y[i-1]} d(G_x[i-1]_u, G_y[i-1]_v)\right) \\ &= \sum_{x=1}^L \sum_{y=x+1}^L \left(\sum_u^{G_x[i-1]} d(G_x[i-1]_u, G_x[i-1]_1) + \sum_v^{G_y[i-1]} d(G_y[i-1]_v, G_y[i-1]_1) + \left(\sum_{k=0}^{i-2} NL^k\right)^2 (d(g_x, g_y)+2)\right) \\ &= L(L-1)\left(\sum_{k=0}^{i-2} NL^k\right)\left(\sum_u^{G[i-1]} d(G[i-1]_u, G[i-1]_1)\right) + \left(\sum_{k=0}^{i-2} NL^k\right)^2 \left(\sum_{gu \neq gv}^G d(G_{gu}, G_{gv})\right)+L(L-1)\left(\sum_{k=0}^{i-2} NL^k\right)^2 \end{align*}$

Where $\sum_{k=0}^{i-2} NL^k$ ~\sum_{k=0}^{i-2} NL^k~ is the number of nodes in graph $G[i-1]$ ~G[i-1]~.

Next, let us address term $D$ ~D~: the sum of shortest paths between all unordered pairs of nodes such that one node is in a copy of graph $G[i-1]$ ~G[i-1]~ and the other is in the copy of $G$ ~G~. It turns out that we are performing calculations nearly identical to those in subtask 1: the only node which changes across the $L$ ~L~ calculations is the generator node used in the copy of $G$ ~G~. Thus, we can combine the $L$ ~L~ calculations into one single calculation.

$\displaystyle \begin{align*} & \sum_{x=1}^L \left(\sum_u^{G_x[i-1]} \sum_v^G d(G_x[i-1]_u, G_v)\right) \\ &= \sum_{x=1}^L \left(\left(\sum_u^{G[i-1]} d(G[i-1]_u, G[i-1]_1)\right)N+\left(\sum_u^G d(G_u, G_{gx})\right)\left(\sum_{k=0}^{i-2} NL^k\right)+N\left(\sum_{k=0}^{i-2} NL^k\right)\right) \\ &= \left(\sum_u^{G[i-1]} d(G[i-1]_u, G[i-1]_1)\right)NL+\left(\sum_{u \neq gv}^G d(G_u, G_{gv})\right)\left(\sum_{k=0}^{i-2} NL^k\right)+NL\left(\sum_{k=0}^{i-2} NL^k\right) \end{align*}$

One problem remains, which is the large term denoting the sum of all paths between the bottommost node 1 and every other node in graph $G[i]$ ~G[i]~. However, like in subtask 1, this can be greedily calculated with a transition of $\mathcal O(1)$ ~\mathcal O(1)~.

$\displaystyle \sum_u^{G[i]} d(G[i]_u, G[i]_1) = L\left(\sum_u^{G[i-1]} d(G[i-1]_u, G[i-1]_1)\right)+L\left(\sum_{k=0}^{i-2} NL^k\right)+\left(\sum_{gu}^G (G_{gu}, G_1)\right)\left(\sum_{k=0}^{i-2} NL^k\right)+\sum_u^G d(G_u, G_1)$

We can precompute $\sum_{gu \neq gv}^G d(G_{gu}, G_{gv})$ ~\sum_{gu \neq gv}^G d(G_{gu}, G_{gv})~, $\sum_{u \neq gv}^G d(G_u, G_{gv})$ ~\sum_{u \neq gv}^G d(G_u, G_{gv})~, $\sum_{gu}^G (G_{gu}, G_1)$ ~\sum_{gu}^G (G_{gu}, G_1)~ and $\sum_u^G d(G_u, G_1)$ ~\sum_u^G d(G_u, G_1)~ in $\mathcal O((N+M)^2)$ ~\mathcal O((N+M)^2)~. $\sum_u^{G[i]} d(G[i]_u, G[i]_1)$ ~\sum_u^{G[i]} d(G[i]_u, G[i]_1)~ and $\sum_{k=0}^{i-2} NL^k$ ~\sum_{k=0}^{i-2} NL^k~ have transitions with $\mathcal O(1)$ ~\mathcal O(1)~ time complexity. Thus, our transitions have a total time complexity of $\mathcal O(K)$ ~\mathcal O(K)~.

Time Complexity: $\mathcal O((N+M)^2+K)$ ~\mathcal O((N+M)^2+K)~

Alternative Solution

Another solution is to precompute all distances in $G$ ~G~ as normal, and then split up all paths into multiple parts. A path can be contained within one copy of $G$ ~G~, or span across copies. In the latter case, there are a few components to consider: the bottom of a path, where we go from the source to node $1$ ~1~, the top, where we go from a source to a generator node, the middle, where we go from a generator node to a source, the LCA node, where we go from a generator node to a generator node, or the transition edge where we transfer across components.

The solution iterates through all $K$ ~K~ heights of the graph and computes the number of copies on this level and the one below it. Using the precomputed distances that we considered above, we can compute how many edges are contributed for each part of all the paths. For example, to compute the contribution given by the parts of the path that are used as a LCA, take the pairwise sum of the generator nodes, multiply by the number of components at this height, and multiply by the number of nodes in one of the sub-graphs under this level, squared. This is admittedly a rather mathy-solution.

Time Complexity: $\mathcal O((N+M)^2+K)$ ~\mathcal O((N+M)^2+K)~

Comments

There are no comments at the moment.