Problem A
The Coalition Structure Generation Problem

A hospital in your city has tasked you with dividing up its workforce into teams. In more detail, you have been given a list of the hospital’s employees $1,\ldots ,n$ together with a number of values that represent how well all different teams (subsets of the employees) are expected to perform. Moreover, the hospital requested that each employee must partake in exactly one team, and you may assume that the teams do not affect each other’s performance. Consequently, you have decided to partition the employees (i.e., generate a “coalition structure”) in a way that maximizes their total (aggregated) expected performance.

More formally, suppose $v(C) \mapsto [-100\, 000,100\, 000]$ yields how well a team $C \subseteq \{ 1,\ldots ,n\} $ is expected to perform. Then, your goal is to find a set of teams $\{ C_1,\ldots ,C_ m\} $ that maximizes $\sum _{i=1}^ m v(C_ i)$, for which $C_ i \cap C_ j = \emptyset $ for all $i \neq j$; $C_ i \neq \emptyset $ for $i=1,\ldots ,m$; and $\bigcup _{i=1}^ m C_ i = \{ 1,\ldots ,n\} $ holds.

Input

In the first line there will be an integer $1 \leq n \leq 18$. Then, there will be $2^ n - 1$ lines. Each such line represents exactly one team (together, the lines represent all possible teams), and consists of three parts. First, there will be an integer $-100\, 000 \leq v \leq 100\, 000$ equal to the team’s expected performance. Then, there will be a number $k > 0$ equal to the team’s size. Finally, there will be $k$ integers, each representing an employee $e \in \{ 1,\ldots ,n\} $ on the team.

Warning! The input files for this problem are quite large. See the Kattis help section for advice on fast IO in your chosen language.

Output

The first line of the output should consist of a single non-negative integer $1 \leq m \leq n$ that is equal to the number of teams in your coalition structure. Then, $m$ lines should follow, each representing one team. These lines should use the same representation as the input, excluding the value that corresponds to the team’s expected performance. In other words, there should be a number $k$ equal to the team’s size, followed by $k$ integers, each representing an employee $e \in \{ 1,\ldots ,n\} $ on the team.

Scoring

The total score of your submission is the sum of your score over all test cases. There are $5$ hidden test groups with different value distributions.

• Group 1: Hand-crafted distribution specifically designed to be difficult for certain classes of greedy local search algorithms.

• Group 2: Normal distribution.

• Group 3: Sparse normal distribution. Each coalition value is drawn from $\mathcal{N}(\mu _1, \sigma _1^2)$ with small probability $p$, else from $\mathcal{N}(\mu _2, \sigma _2^2)$, where $\mu _1 >> \mu _2$ and $\sigma _1^2 >> \sigma _2^2$.

• Group 4: Sparse uniform distribution.

• Group 5: Uniform distribution.

Each hidden test group contains $10$ test cases, for a total of $50$ hidden test cases, in addition to the two sample test cases below. The score of a single test case is computed as follows:

where $V$ is the value (i.e., aggregated expected performance of the employees) of your coalition structure, and $V_{best} > 0$ is the best (highest) achievable value. The maximum total score is thus $52$.

3
1 1 1
2 1 2
3 1 3
5 2 1 2
6 2 1 3
7 2 2 3
8 3 1 2 3

2
1 1
2 2 3

2
1 1 1
2 1 2
1 2 1 2

2
1 1
1 2