Contest Duration: - (local time) (100 minutes) Back to Home

## F - Close Group Editorial by en_translator

Let $$V$$ be the vertex set of the graph, $$S$$ be a non-empty subset of $$V$$ and $$f(S)$$ be the answer for this problem when the input is the subgraph induced by $$S$$.
What we want is $$f(V)$$, but it is necessary to calculate all $$f(S)$$ when obtaining $$f(V)$$, so let us consider calculating all $$f(S)$$.

If the induced subgraph by $$S$$ is complete, then $$f(S) = 1$$; otherwise $$f(S)$$ is determined by $$\displaystyle \min_{T \subset S}f(T)+f(S \setminus T)$$.
Therefore, one can determine $$f(S)$$ in order that smaller subsets are calculated earlier.

Let us consider the complexity.
One can determine if each induced subgraph is complete in $$O(2^N N^2)$$ time for all $$S$$.
The problem is $$\displaystyle \min_{T \subset S}f(T)+f(S \setminus T)$$ part.
If $$T$$ is iterated through all subset of $$V$$, the total computation time for all $$S$$ will be $$O(2^N \cdot 2^N)=O(4^N)$$; actually, however, $$S$$ can be processed in a total of $$O(3^N)$$ time, since $$T$$ can only be a subset of $$S$$, and

$\sum_{S \subset V} 2^{|S|}=3^N.$

This formula can also be understood from the fact that each element of $$V$$ can be either

• contained in both $$S$$ and $$T$$,
• contained only in $$S$$, or
• not contained in either set,

independently.

Sample Code (C++) : https://atcoder.jp/contests/abc187/submissions/19103570
Sample Code (Python) : https://atcoder.jp/contests/abc187/submissions/19103577

The answer for this problem is the chromatic number of complement graph when

• two vertices directly connected by an edge can be painted with the same color (if not, the edge is removed), and
• two vertices not directly connected by edges cannot be painted with the same color.

It is known that the chromatic number of a graph calculated in a total of $$O(2^NN)$$ time, so the original problem can be solved in a total of $$O(2^NN)$$ time as well.

Related Materials (Japanese): https://www.slideshare.net/wata_orz/ss-12131479

posted:
last update: