SUMCUBE - Editorial

[r_64]

PROBLEM LINK:

Practice

Contest

Author: Hanlin Ren

Tester: Jingbo Shang

Editorialist: Hanlin Ren

DIFFICULTY:

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:

Subtask 1

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

Time complexity: O(M2^N).

Subtask 2 and 4

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.

Subtask 2

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}.

Subtask 3

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).

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:

• 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{aligned} 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{aligned}

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.

Subtask 6

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}).

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.
Tester’s solution can be found here.

[vijju123]

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

[liouzhou_101]

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.

[khalid545]

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.

[eight_bitguy]

I am still not getting this

Is anyone thinking to make a video editorial for this question?

[r_64]

@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.

[vijju123]

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

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…

[r_64]

@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)).

[vijju123]

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