PROBLEM LINK:Author: Hanlin Ren Tester: Jingbo Shang Editorialist: Hanlin Ren DIFFICULTY:hard PREREQUISITES:math, combinatorics, sqrtdecomposition PROBLEM:Given an undirected simple graph $G=(V,E)$, for a subset $S\subseteq V$ we define $f(S)$ is the number of edges in the induced subgraph of $S$. Find $$\sum_{S\subseteq V}f(S)^k.$$ QUICK EXPLANATION:The problem actually asks you to enumerate all lists of edges of length $k$, and suppose these $k$ edges occupy $p$ vertices, the answer is added by $2^{Np}$. We only need to count how many lists occupy $p=2\dots 2k$ vertices when $k\le 3$, and we do it for every $p=2\dots 2k$ separately. Some sqrtdecomposition tricks may help. EXPLANATION:Subtask 1We enumerate all subsets $S\subseteq V$ and calculate $f(S)^k$ and add them together. Time complexity: $O(M2^N)$. Subtask 2 and 4The answer is the number of ways to choose the following things:
such that every endpoint of every $e_i$ is in $S$. To see this, if you fix $S$ then there are exactly $f(S)^k$ ways to choose the edge list. To calculate the answer, let's enumerate the list first. For a list $(e_1,e_2,\dots,e_k)$, if a vertex $v$ is the endpoint of some $e_i$, then it must be in $S$; otherwise it's can be in $S$ or out $S$. So the number of ways to choose $S$ is $2^{Np}$, where $p$ is the number of vertices that are endpoints of some $e_i$. This gives an $O(M^k)$ algorithm: we simply enumerate the edge list, calculate its $p$ value, and add $2^{Np}$ to the answer. This can pass subtask 2 and 4. Subtask 2Specially, for $k=1$, since the graph is simple, for any edge(list of length $1$), its $p=2$. So the answer is $M\cdot 2^{N2}$. Subtask 3For $k=2$, we need to know the number of ordered edge pairs $(e_1,e_2)$ so their $p=2,3,4$ respectively. For $p=2$, the answer is $a_{22}=M$, since the graph is simple and we have to select two identical edges. For $p=3$, let's enumerate the common vertex of $e_1$ and $e_2$, say $v$. Then there are $d(d1)$ ways to select these two edges, where $d=\deg_v$ is the degree of the vertex. We sum up all the numbers, and the answer is $a_{23}=\sum_{v\in V}\deg_v(\deg_v1)$. For $p=4$, the answer is $a_{24}=M^2a_{22}a_{23}$. This subtask can be done in $O(M)$. Subtask 5(Below are some graph theory terms that'll appear later) For $k=3$, we need to know the number of edge lists $(e_1,e_2,e_3)$ so their $p=2,3,4,5,6$ respectively. For $p=2$, we need to pick $3$ identical edges, so the answer is $a_{32}=M$; For $p=3$, there are two cases:
thus $a_{33}=3a_{23}+tri$; For $p=4$, there are three cases:
However every triangle is also counted $3$ times, thus $a_{34}=3a_{24}+claw+P_43\cdot tri$. For $p=5$, the only situation is $P_2+P_3$, i.e., two chains of $2$ vertices and $3$ vertices respectively. Let's enumerate the midpoint of $P_3$, say, $v$. We can then enumerate $v$'s two neighbors $u$ and $w$, so the $P_3$ is $uvw$. How many edges could be the $P_2$? All edges that doesn't have $u,v,w$ as endpoints are eligible, so the number of valid $P_2$'s is $M\deg_u\deg_v\deg_w+f(\{u,v,w\})$, where $f(\{u,v,w\})=[(u,v)\in E]+[(u,w)\in E]+[(v,w)\in E]$ is the number of edges that are counted twice in $\deg_u+\deg_v+\deg_w$. Notice that $f(\{u,v,w\})=2+[(u,w)\in E]$, so the number of valid $P_2$'s is $M\deg_u\deg_v\deg_w+2+[(u,w)\in E]$. Thus we have $$\begin{align*} a_{35}=&3\sum_{v\in V}\sum_{(u,v)\in E}\sum_{(w,v)\in E,w\ne u}(M\deg_u\deg_v\deg_w+2+[(u,w)\in E])\\ =&3\sum_{v\in V}\left(\deg_v(\deg_v1)(M\deg_v+2)\sum_{(u,v)\in E}\sum_{(w,v)\in E,w\ne u}(\deg_u+\deg_w[(u,w)\in E])\right)\\ =&3\sum_{v\in V}\left(\deg_v(\deg_v1)(M\deg_v+2)+B(v)2(\deg_v1)\sum_{(u,v)\in E}\deg_u\right),\\ \end{align*}$$ where $B(v)=\sum_{(u,v)\in E}\sum_{(w,v)\in E}[(u,w)\in E]$ is defined above. The rest situation $p=6$ is easy: we simply subtract what we calculated from $M^3$: $a_{36}=M^3a_{32}a_{33}a_{34}a_{35}$. Everything can be solved in $O(M)$ time, except the calculation for $B(v)$. The time for computing $B(v)$ is $\sum_{v\in V}\deg_v^2=O(NM)$. That passes subtask 5. Subtask 6Author's solutionNote that the bottleneck of the above algorithm is to calculate $B$. In fact, we have a simple algorithm for computing $B(v)$ in $O(M\sqrt{M})$ time:
Tester's solutionWhen computing $B(v)$, we enumerate $v$'s neighbor $w$, and count the number of common neighbors of $v$ and $w$. This can be done in $O(\frac{N}{64})$ by using bitsets: we maintain a huge binary number $mask_v$ for every vertex $v$. $mask_v$'s $w$th bit is $1$ if and only if $(v,w)\in E$. Then to count the number of common neighbors of $v$ and $w$, we perform "and" operation on the two masks and count the number of $1$'s in the result, i.e, The overall complexity is $O(\frac{MN}{64})$. ALTERNATIVE SOLUTION:If your solution is different with ours, feel free to leave a comment. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 18 Aug '17, 14:23

I would like to share my approach, as I came up with it at a cost of 5 full pieces of A4 paper. I only use math derivation to solve it and it seems a bit different from the editorial. Given a simple graph G = (V, E), and k = 1, 2, or 3. It is asked for that $$ \sum_{S \subseteq V} f(S)^k, $$ where $f(S)$ is the number of edges whose ends are in S, i.e. $$ f(S) = \frac 1 2 \sum_{x \in S} \sum_{y \in S} [(x, y) \in E]. $$ My solution is below. Note that k is only 1, 2, or 3. We consider each case separately. For convenience, let $e_{xy}$ be short for $[(x, y) \in E]$. Here we have $e_{xy} = e_{yx}$, and $e_{xx} = 0$. Let $s_x$ be short for $[x \in S]$. Let $d_x$ be the degree of x, i.e. $$ d_x = \sum_{y \in V} e_{xy}. $$ For convenience, we now consider that $$ 2^k \sum_{S \subseteq V} f(S)^k .$$ When k = 1, $$ 2 \sum_{S \subseteq V} f(S) = \sum_{S \subseteq V} \sum_{x \in S} \sum_{y \in S} e_{xy}. $$ And then $$ \sum_{S \subseteq V} \sum_{x \in S} \sum_{y \in S} e_{xy} = \sum_{x \in V} \sum_{y \in V} e_{xy} \sum_{S \subseteq V} s_x s_y = 2^{V2} \sum_{x \in V} \sum_{y \in V} e_{xy} = 2^{V2} 2E. $$ We let $$c_{11} = \sum_{x \in V} \sum_{y \in V} e_{xy} = 2E. $$ When k = 2, $$ 4 \sum_{S \subseteq V} f(S)^2 = \sum_{S \subseteq V} \sum_{x \in S} \sum_{y \in S} \sum_{x' \in S} \sum_{y' \in S} e_{xy} e_{x'y'}. $$ Note that $$ \sum_{S \subseteq V} \sum_{x \in S} \sum_{y \in S} \sum_{x' \in S} \sum_{y' \in S} e_{xy} e_{x'y'} = 2^{V2} 2 c_{22} + 2^{V3} 4 c_{211} + 2^{V4} c_{1111}, $$ where $$ c_{22} = c_{11}, $$ $$ c_{211} = \sum_{x \in V} \sum_{y \in V} \sum_{y' \in V \setminus \{x, y\}} e_{xy} e_{xy'} = \sum_{x \in V} d_x (d_x1), $$ $$ c_{1111} = \sum_{x \in V} \sum_{y \in V} \sum_{x' \in V \setminus \{x, y\}} \sum_{y' \in S \setminus \{x, y\}} e_{xy} e_{x'y'} = 4\left( E^2 + E  \sum_{x \in V} d_x^2 \right). $$ When k = 3, $$ 8 \sum_{S \subseteq V} f(S)^3 = \sum_{S \subseteq V} \sum_{x \in S} \sum_{y \in S} \sum_{x' \in S} \sum_{y' \in S} \sum_{x'' \in S} \sum_{y'' \in S} e_{xy} e_{x'y'} e_{x''y''}. $$ Note that $$ \begin{aligned} 8 \sum_{S \subseteq V} f(S)^3 = & 2^{V2} 4 c_{33} + 2^{V3} ( 24 c_{321} + 8 c_{222} ) + \\ & 2^{V4} ( 8 c_{3111} + 6 c_{2211_0} + 24 c_{2211_1} ) + \\ & 2^{V5} 12 c_{21111} + 2^{V6} c_{111111}. \end{aligned} $$ where $$ c_{33} = c_{11} $$ $$ c_{321} = c_{211} $$ $$ c_{222} = \sum_{x \in V} \sum_{y \in V} \sum_{z \in V} e_{xy} e_{yz} e_{zx} $$ $$ c_{3111} = \sum_{x \in V} \sum_{y \in V} \sum_{y' \in V \setminus \{x, y\}} \sum_{y'' \in V \setminus \{x, y, y'\}} e_{xy} e_{xy'} e_{xy''} = \sum_{x \in V} d_x(d_x1)(d_x2) $$ $$ c_{2211_0} = c_{1111} $$ $$ c_{2211_1} = \sum_{x \in V} \sum_{y \in V} \sum_{y' \in V \setminus \{x, y\}} \sum_{y'' \in V \setminus \{x, y\}} e_{xy} e_{xy'} e_{yy''} = 4E^2  c_{222} $$ $$ \begin{aligned} c_{21111} & = \sum_{x \in V} \sum_{y \in V} \sum_{y' \in V \setminus \{x, y\}} \sum_{x'' \in V \setminus \{x, y, y'\}} \sum_{y'' \in V \setminus \{x, y, y'\}} e_{xy} e_{xy'} e_{x''y''} \\ & = (2E+4) c_{211} + 2 c_{222}  2 \sum_{x \in V} d_x^2(d_x1)  4 \sum_{x \in V} \sum_{y \in V} e_{xy} d_y (d_x1) \end{aligned} $$ $$ \begin{aligned} c_{111111} & = \sum_{x \in V} \sum_{y \in V} \sum_{x' \in V \setminus \{x, y\}} \sum_{y' \in V \setminus \{x, y\}} \sum_{x'' \in V \setminus \{x, y, x', y'\}} \sum_{y'' \in V \setminus \{x, y, x', y'\}} e_{xy} e_{x'y'} e_{x''y''} \\ & = (2E)^3  ( 4 c_{33} + 24 c_{321} + 8 c_{222} + 8 c_{3111} + 6 c_{2211_0} + 24 c_{2211_1} + 12 c_{21111} + c_{111111} ) \end{aligned} $$ Feel free to see my editorial for this problem (Chinese version). It is amazing that I AC in one go after so long derivations. My code is here. answered 11 Sep '17, 22:03

Similar to the author's solution for counting triangles, this is the approach that I have used:
So if the adjacency lists are sorted, for each edge $(u, v)$, we can compute the intersection of the adjacency lists of $u$ and $v$ in $O(adj(u) + adj(v)) = O(\sqrt{E})$, leading to the overall complexity: $O(E \log(E) + E \sqrt{E})$ Proof that $adj(u) = O(\sqrt{E})$ can be found here. answered 12 Sep '17, 04:47

I am still not getting this :/ Is anyone thinking to make a video editorial for this question? answered 12 Sep '17, 09:32

I will appreciate if someone can help me in understanding how we arrive to this conclusion. Also, if its okay, can someone give some details of Subtask 1 as well? It surely wasnt that simple, atleast for me, so I am looking at ways to refine my approach :) answered 11 Sep '17, 16:10
@vijju123: what we want is sum(f(s)^k  s is V's subset). f(s) is the number of ways to pick one edge from the induced subgraph of s. Then f(s)^k is the number of ways to pick (a list of) k edges. Hope this helps you.
(11 Sep '17, 16:16)
My confusion arises from, $k$ is only upto 3. How are we accounting for picking more than 3 edges then? Like edge length 4? And yes, thanks for that, it did help me :D Also, expressing my confusion with an example. $f(s)$ is number of ways to pick 1 edge from sub graph. Agreed. But on the ${f(s)}^{k}$ part, lets say we have a triangle (3 nodes, 3 edges). Theres only 1 way to pick them all 3. But there are 3 ways to pick 1 edge. I think I am lost somewhere in duplicates or something...
(11 Sep '17, 16:25)
@vijju123: When I say "pick a list of k edges", I mean pick $e_1,e_2,...,e_k$. There can be the same edges among $\{e_1,e_2,...,e_k\}$, and their order is important(i.e. (1,2,3) is different from (2,3,1)).
(11 Sep '17, 16:48)
That clarifies things. Not only was I disregarding repetitions, I didnt know if order has to be taken into account. Thanks for clarification!! I appreciate that :)
(11 Sep '17, 17:18)
