Planar Perimeter
Contest: Codeforces Round 599 (Div. 1)
Difficulty rating: 3200
Tags: constructive algorithms, graphs

Ujan has finally cleaned up his house and now wants to decorate the interior. He decided to place a beautiful carpet that would really tie the guest room together.

He is interested in carpets that are made up of polygonal patches such that each side of a patch is either a side of another (different) patch, or is an exterior side of the whole carpet. In other words, the carpet can be represented as a planar graph, where each patch corresponds to a face of the graph, each face is a simple polygon. The perimeter of the carpet is the number of the exterior sides.

Ujan considers a carpet beautiful if it consists of $$$f$$$ patches, where the $$$i$$$-th patch has exactly $$$a_i$$$ sides, and the perimeter is the smallest possible. Find an example of such a carpet, so that Ujan can order it!

Input format:
The first line of input contains a single integer $$$f$$$ ($$$1 \leq f \leq 10^5$$$), the number of patches in the carpet.

The next line contains $$$f$$$ integers $$$a_1, \ldots, a_f$$$ ($$$3 \leq a_i \leq 3\cdot 10^5$$$), the number of sides of the patches. The total number of the sides of the patches $$$a_1 + \ldots + a_f$$$ does not exceed $$$3\cdot10^5$$$.

Output format:
Output the description of the carpet as a graph.

First, output a single integer $$$n$$$ ($$$3 \leq n \leq 3 \cdot 10^5$$$), the total number of vertices in your graph (the vertices must be numbered from $$$1$$$ to $$$n$$$).

Then output $$$f$$$ lines containing the description of the faces. The $$$i$$$-th line should describe the $$$i$$$-th face and contain $$$a_i$$$ distinct integers $$$v_{i,1}, \ldots, v_{i,a_i}$$$ ($$$1 \leq v_{i,j} \leq n$$$), which means that the vertices $$$v_{i,j}$$$ and $$$v_{i,(j \bmod{a_i})+1}$$$ are connected by an edge for any $$$1 \leq j \leq a_i$$$.

The graph should be planar and satisfy the restrictions described in the problem statement. Its perimeter should be the smallest possible. There should be no double edges or self-loops in the graph. The graph should be connected. Note that a solution always exists; if there are multiple solutions, output any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample, the two triangular faces are connected by a single edge, which results in the minimum perimeter $$$4$$$.

The figure shows one possible configuration for the second sample. The minimum perimeter in this case is $$$3$$$.

Example input:
2
3 3

Example output:
4
2 1 4 
1 2 3

Example input:
3
5 3 5

Example output:
6
1 2 3 4 5
4 5 6
1 3 4 6 5

Editorial:
If there is just a single face, just output it. Suppose there are at least $$$2$$$ faces.
Let's say that we "glue" a cycle to a planar graph along $$$k$$$ edges if we place this cycle so that the graph and the cycle share $$$k$$$ edges on their perimeters.
First, sort the numbers in decreasing order (then we have $$$a_1 \geq a_2 \geq \ldots \geq a_n$$$). By gluing any $$$a_i$$$ to the $$$a_1$$$ cycle, we can decrease the number of edges by at most $$$a_i-2$$$. Also note that the answer is always at least $$$3$$$, because there cannot be multiple edges between two vertices. Thus, if $$$a_1-2 \geq \sum_{i=2}^n (a_i-2)$$$, then the answer is $$$a_1 - \sum_{i=2}^n (a_i-2)$$$ (we subtract $$$2$$$ from $$$a_1$$$ to keep the perimeter at least $$$3$$$: these are the $$$2$$$ edges that we don't glue anything to).
Otherwise the answer is either $$$3$$$ or $$$4$$$ (depending on the parity of $$$\sum_{i=1}^n a_i$$$). The algorithm to construct the graph: let $$$C := a_1$$$. Iterate $$$i$$$ from $$$2$$$ to $$$n$$$. While $$$(C-2) + (a_i-2) < \sum_{j=i+1}^n (a_j-2)$$$, glue the $$$i$$$-th cycle with the graph along one edge ($$$C += (a_i-2)$$$). For the first $$$a_i$$$ such that this does not hold, glue it so that $$$\sum_{j=i+1}^n (a_j-2) \leq C-2 \leq \sum_{j=i+1}^n (a_j-2) + 1$$$. Afterwards just glue each remaining cycles $$$a_j$$$ along $$$a_j-1$$$ edges with the graph.
There is one problem with this algorithm: it can happen that we add multiple edges between two vertices. This situation is as follows: suppose you are at some point of the algorithm with a planar graph that you're building. Suppose there is an edge between some vertices $$$u$$$ and $$$v$$$ on the current perimeter, and you now happen to glue a cycle $$$C$$$ along the edges between $$$u$$$ and $$$v$$$, and the last edge of the cycle $$$C$$$ you're gluing must connect $$$u$$$ and $$$v$$$. To solve this situation, take the vertex $$$u'$$$ adjacent to $$$u$$$ to the right on the perimeter, and the vertex $$$v'$$$ adjacent to $$$v$$$ also to the right on the perimeter. Now, $$$u'$$$ and $$$v'$$$ cannot be connected by an edge in the current graph, because then it would intersect the edge between $$$u$$$ and $$$v$$$. This would be a contradiction, because the graph is planar. Then you glue the cycle $$$C$$$ along the edges between $$$u'$$$ and $$$v'$$$.
The complexity of the algorithm: $$$O(\sum_{i=1}^n a_i)$$$. You should be careful with the implementation: for example, not to make perimeter equal to $$$2$$$ at some point or use some edge in more than two faces.