Degree Set (Codeforces 976D)
Tags: Implement, graphs

You are given a sequence of n positive integers d1, d2, ..., dn (d1 < d2 < ... < dn). Your task is to construct an undirected graph such that:  there are exactly dn + 1 vertices;  there are no self-loops;  there are no multiple edges;  there are no more than 106 edges;  its degree set is equal to d. Vertices should be numbered 1 through (dn + 1).Degree sequence is an array a with length equal to the number of vertices in a graph such that ai is the number of vertices adjacent to i-th vertex.Degree set is a sorted in increasing order sequence of all distinct values from the degree sequence.It is guaranteed that there exists such a graph that all the conditions hold, and it contains no more than 106 edges.Print the resulting graph.

Input: The first line contains one integer n (1 ≤ n ≤ 300) — the size of the degree set.The second line contains n integers d1, d2, ..., dn (1 ≤ di ≤ 1000, d1 < d2 < ... < dn) — the degree set.

Output: In the first line print one integer m (1 ≤ m ≤ 106) — the number of edges in the resulting graph. It is guaranteed that there exists such a graph that all the conditions hold and it contains no more than 106 edges.Each of the next m lines should contain two integers vi and ui (1 ≤ vi, ui ≤ dn + 1) — the description of the i-th edge.


Sample Inputs:
3
2 3 4

3
1 2 3

Sample Outputs:
8
3 1
4 2
4 5
2 5
5 1
3 2
2 1
5 3

4
1 2
1 3
1 4
2 3

Solution (Python):
def readline():
    return list(map(int, input().split()))

def solve(d):
    while d:
        dn = d.pop()
        if not d:
            for i in range(1, dn + 1):
                for j in range(i, dn + 1):
                    yield (i, j + 1)
            return
        else:
            d1 = d.pop(0)
            for i in range(1, dn + 1):
                for j in range(max(dn - d1 + 1, i), dn + 1):
                    yield (i, j + 1)
            d = [di - d1 for di in d]

def main():
    (n,) = readline()
    d = readline()
    assert len(d) == n
    edges = list(solve(d))
    print(len(edges))
    print('\n'.join(map('{0[0]} {0[1]}'.format, edges)))
main()

Solution (Python):
def readline():
    return list(map(int, input().split()))

def SolveDegreeSet(DegreSet, n):
    edges = []
    verticesCount = 0
    if n == 0:
        verticesCount = 1
        return (edges, verticesCount)
    if n == 1:
        verticesCount = DegreSet[0] + 1
        for i in range(1, verticesCount + 1):
            for j in range(i + 1, verticesCount + 1):
                edges.append([i, j])
        return (edges, verticesCount)
    newDegreeSet = []
    for i in range(1, n - 1):
        newDegreeSet.append(DegreSet[i] - DegreSet[0])
    prevSolveDegreeSet = SolveDegreeSet(newDegreeSet, n - 2)
    verticesCount = prevSolveDegreeSet[1]
    edges = prevSolveDegreeSet[0]
    verticesCount += DegreSet[n - 1] - DegreSet[n - 2]
    for i in range(0, DegreSet[0]):
        verticesCount += 1
        for j in range(1, verticesCount):
            edges.append([j, verticesCount])
    return (edges, verticesCount)
(n,) = readline()
d = readline()
par = list(SolveDegreeSet(d, n))
edges = par[0]
print(len(edges))
print('\n'.join(map('{0[0]} {0[1]}'.format, edges)))

Solution (Python):
from sys import stdin
from sys import stdout
n = int(stdin.readline())
d = [0] + list(map(int, stdin.readline().split()))
e = []
for i in range(1, n + 1):
    for u in range(d[i - 1] + 1, d[i] + 1):
        for v in range(u + 1, d[n - i + 1] + 2):
            e.append([u, v])
stdout.write('{}\n'.format(len(e)))
for ei in e:
    stdout.write('{} {}\n'.format(ei[0], ei[1]))