×

# SUMCUBE - Editorial

Practice

Contest

Author: Hanlin Ren

Tester: Jingbo Shang

Editorialist: Hanlin Ren

hard

# PREREQUISITES:

math, combinatorics, sqrt-decomposition

# 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^{N-p}$. 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 sqrt-decomposition tricks may help.

# EXPLANATION:

We enumerate all subsets $S\subseteq V$ and calculate $f(S)^k$ and add them together.

Time complexity: $O(M2^N)$.

The answer is the number of ways to choose the following things:

• a subset $S$ of $V$;
• a list of edges of length $k$: $(e_1,e_2,\dots,e_k)$

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^{N-p}$, 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^{N-p}$ to the answer. This can pass subtask 2 and 4.

Specially, 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^{N-2}$.

For $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(d-1)$ 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_v-1)$.

For $p=4$, the answer is $a_{24}=M^2-a_{22}-a_{23}$.

This subtask can be done in $O(M)$.

(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:

• We pick two edges that has a common vertex, and duplicate one of them. There are $3a_{23}$ ways: $a_{23}$ ways to pick such two edges and select one(to duplicate), and $3$ ways to arrange them(112,121,211);
• We pick a triangle. we can enumerate one vertex in the triangle, say $v$, then the number of triangles is $$tri=\sum_{v\in V}\sum_{(u,v)\in E}\sum_{(w,v)\in E}[(u,w)\in E].$$ We define $B(v)=\sum_{(u,v)\in E}\sum_{(w,v)\in E}[(u,w)\in E]$, then there are $tri=\sum_{v\in V}B(v)$ triangles.

thus $a_{33}=3a_{23}+tri$;

For $p=4$, there are three cases:

• We pick two edges that doesn't have common vertices, and duplicate one of them. There are $3a_{24}$ ways;
• We pick a claw. Let's enumerate the degree-3 vertex of the claw, say $v$, then there are $\deg_v(\deg_v-1)(\deg_v-2)$ ways. The total answer is $claw=\sum_{v\in V}\deg_v(\deg_v-1)(\deg_v-2)$.
• We pick a path of $4$ vertices($P_4$). Let's enumerate the middle edge, suppose its endpoints are $u$ and $v$. Then there are $(\deg_u-1)(\deg_v-1)$ ways to pick the remaining two edges. We can rearrange the three edges in $6$ ways, so the total answer is $P_4=6\sum_{(u,v)\in E}(\deg_u-1)(\deg_v-1)$.

However every triangle is also counted $3$ times, thus $a_{34}=3a_{24}+claw+P_4-3\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 $u-v-w$. 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_v-1)(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_v-1)(M-\deg_v+2)+B(v)-2(\deg_v-1)\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^3-a_{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.

### Author's solution

Note 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:

• First we can use hash tables to support the operation "check if an edge is in $E$" in constant time;
• Enumerate $v\in V$;
• If $\deg_v\le \sqrt{M}$, we use brute-force and the complexity is $O(\deg_v^2)=O(\deg_v\sqrt{M})$;
• Otherwise $\deg_v>\sqrt{M}$, we enumerate all $M$ edges and see if its two endpoints are both $v$'s neighbors. This costs $O(M)=O(\deg_v\sqrt{M})$ time;
• The overall complexity is $O(\sum_v\deg_v\sqrt{M})=O(M\sqrt{M})$.

### Tester's solution

When 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, (mask[v]&mask[w]).count().

The overall complexity is $O(\frac{MN}{64})$.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

7★r_64
261924
accept rate: 16%

19.7k350498541

 5 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^{|V|-2} \sum_{x \in V} \sum_{y \in V} e_{xy} = 2^{|V|-2} 2|E|.$$ We let $$c_{11} = \sum_{x \in V} \sum_{y \in V} e_{xy} = 2|E|.$$ 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^{|V|-2} 2 c_{22} + 2^{|V|-3} 4 c_{211} + 2^{|V|-4} 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_x-1),$$ $$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^{|V|-2} 4 c_{33} + 2^{|V|-3} ( 24 c_{321} + 8 c_{222} ) + \\ & 2^{|V|-4} ( 8 c_{3111} + 6 c_{2211_0} + 24 c_{2211_1} ) + \\ & 2^{|V|-5} 12 c_{21111} + 2^{|V|-6} 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_x-1)(d_x-2)$$ $$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''} = 4|E|^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''} \\ & = (2|E|+4) c_{211} + 2 c_{222} - 2 \sum_{x \in V} d_x^2(d_x-1) - 4 \sum_{x \in V} \sum_{y \in V} e_{xy} d_y (d_x-1) \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''} \\ & = (2|E|)^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 682●2●3●13 accept rate: 12%
 1 Similar to the author's solution for counting triangles, this is the approach that I have used: In the adjacency lists of a vertex $u$, only keep vertices $v$ such that : $deg(u) \le deg(v)$ $uvw$ is a triange if $(u, v) \in E$ and $w \in adj(u) \cap adj(v)$ 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 116●3 accept rate: 12%
 1 I am still not getting this :/ Is anyone thinking to make a video editorial for this question? answered 12 Sep '17, 09:32 231●3 accept rate: 0%
 0 Subtask 2 and 4 The answer is the number of ways to choose the following things: a subset SS of VV; a list of edges of length kk: (e1,e2,…,ek)  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 15.2k●1●18●60 accept rate: 18% @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) r_647★ 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) r_647★ 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)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,498
×1,334
×1,176
×288
×286
×10

question asked: 18 Aug '17, 14:23

question was seen: 1,716 times

last updated: 12 Sep '17, 09:32