You are not logged in. Please login at www.codechef.com to post your questions!

×

SUMCUBE - Editorial

1
2

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)

explanation for "triangle","claw" etc

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.

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.

This question is marked "community wiki".

asked 18 Aug '17, 14:23

r_64's gravatar image

7★r_64
261923
accept rate: 16%

edited 11 Sep '17, 17:13

admin's gravatar image

0★admin ♦♦
19.5k348496535


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.

link

answered 11 Sep '17, 22:03

liouzhou_101's gravatar image

7★liouzhou_101 ♦♦
6822313
accept rate: 12%

edited 11 Sep '17, 22:17

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.

link

answered 12 Sep '17, 04:47

khalid545's gravatar image

5★khalid545
1163
accept rate: 12%

I am still not getting this :/

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

link

answered 12 Sep '17, 09:32

eight_bitguy's gravatar image

5★eight_bitguy
2313
accept rate: 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 :)

link

answered 11 Sep '17, 16:10

vijju123's gravatar image

6★vijju123 ♦
14.5k11854
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 ♦6★

@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) vijju123 ♦6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,029
×1,281
×1,103
×286
×277
×10

question asked: 18 Aug '17, 14:23

question was seen: 1,645 times

last updated: 12 Sep '17, 09:32