Maximum Diameter Graph (Codeforces 1082D)
Tags: Implement, graphs

Graph constructive problems are back! This time the graph you are asked to build should match the following properties.The graph is connected if and only if there exists a path between every pair of vertices.The diameter (aka "longest shortest path") of a connected undirected graph is the maximum number of edges in the shortest path between any pair of its vertices.The degree of a vertex is the number of edges incident to it.Given a sequence of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ construct a connected undirected graph of $$$n$$$ vertices such that:  the graph contains no self-loops and no multiple edges;  the degree $$$d_i$$$ of the $$$i$$$-th vertex doesn't exceed $$$a_i$$$ (i.e. $$$d_i \le a_i$$$);  the diameter of the graph is maximum possible. Output the resulting graph or report that no solution exists.

Input: The first line contains a single integer $$$n$$$ ($$$3 \le n \le 500$$$) — the number of vertices in the graph.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n - 1$$$) — the upper limits to vertex degrees.

Output: Print "NO" if no graph can be constructed under the given conditions.Otherwise print "YES" and the diameter of the resulting graph in the first line.The second line should contain a single integer $$$m$$$ — the number of edges in the resulting graph.The $$$i$$$-th of the next $$$m$$$ lines should contain two integers $$$v_i, u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$v_i \neq u_i$$$) — the description of the $$$i$$$-th edge. The graph should contain no multiple edges — for each pair $$$(x, y)$$$ you output, you should output no more pairs $$$(x, y)$$$ or $$$(y, x)$$$.

Note: Here are the graphs for the first two example cases. Both have diameter of $$$2$$$.  $$$d_1 = 1 \le a_1 = 2$$$$$$d_2 = 2 \le a_2 = 2$$$$$$d_3 = 1 \le a_3 = 2$$$   $$$d_1 = 1 \le a_1 = 1$$$$$$d_2 = 4 \le a_2 = 4$$$$$$d_3 = 1 \le a_3 = 1$$$$$$d_4 = 1 \le a_4 = 1$$$ 

Sample Inputs:
3
2 2 2

5
1 4 1 1 1

3
1 1 1

Sample Outputs:
YES 2
2
1 2
2 3

YES 2
4
1 2
3 2
4 2
5 2

NO

Solution (Python):
n = int(input())
single = []
out = []
lst = [int(x) for x in input().split()]
index_2 = n
for i in range(n):
    if lst[i] == 1:
        single.append(i)
    if lst[i] > 1:
        index_2 = min(index_2, i)
prev_vt = index_2
single_index = 0
diam = 0
if index_2 != n and lst[index_2] > 1:
    if single_index < len(single) - 1:
        diam += 1
    for i in range(1, lst[index_2]):
        if single_index < len(single) - 1:
            out.append((single[single_index] + 1, index_2 + 1))
            single_index += 1
        else:
            break
for i in range(index_2 + 1, n):
    if lst[i] > 2:
        for j in range(2, lst[i]):
            if single_index < len(single) - 1:
                out.append((single[single_index] + 1, i + 1))
                single_index += 1
            else:
                break
    if lst[i] > 1:
        diam += 1
        out.append((prev_vt + 1, i + 1))
        prev_vt = i
if single_index != len(single):
    out.append((single[single_index] + 1, prev_vt + 1))
    single_index += 1
    diam += 1
if single_index == len(single):
    print('YES', diam)
    print(len(out))
    for el in out:
        print(*el)
else:
    print('NO')

Solution (Python):
t = int(input())
d = [0] + list(map(int, input().split()))
s = 0
leaf = []
other = []
for i in range(1, len(d)):
    if d[i] == 1:
        leaf.append(i)
    else:
        other.append(i)
    s += d[i]
if s / 2 < t - 1:
    print('NO')
    exit(0)
ans = []
for i in range(1, len(other)):
    ans.append((other[i - 1], other[i]))
    d[other[i]] -= 1
    d[other[i - 1]] -= 1
if len(leaf) == 1:
    ans.append((leaf[0], other[0]))
    d[leaf[0]] -= 1
    d[other[0]] -= 1
    print('YES', len(other))
elif len(leaf) > 1:
    p = 0
    ans.append((other[0], leaf[0]))
    d[other[0]] -= 1
    ans.append((other[len(other) - 1], leaf[1]))
    d[other[len(other) - 1]] -= 1
    for i in range(2, len(leaf)):
        while not d[other[p]]:
            p = p + 1
        ans.append((leaf[i], other[p]))
        d[other[p]] -= 1
    print('YES', len(other) + 1)
else:
    print('YES', len(other) - 1)
print(len(ans))
for i in range(len(ans)):
    print(ans[i][0], ans[i][1])

Solution (Python):
a = []
n = 0
Ones = []

def solution():
    s = 0
    for item in a:
        s = s + item
    if s < 2 * (n - 1):
        print('NO')
        return
    for i in range(n):
        if a[i] == 1:
            a[i] = 0
            Ones.append(i)
    t = len(Ones)
    d = n - t - 1 + min(2, t)
    print('YES ' + str(d) + '\n' + str(n - 1))
    l = -1
    if len(Ones) != 0:
        l = Ones[len(Ones) - 1]
        Ones.remove(l)
    for i in range(n):
        if a[i] > 1:
            if l != -1:
                a[l] = a[l] - 1
                a[i] = a[i] - 1
                print(str(l + 1) + ' ' + str(i + 1))
            l = i
    i = n - 1
    while i >= 0:
        while len(Ones) > 0 and a[i] > 0:
            a[i] = a[i] - 1
            u = Ones[len(Ones) - 1]
            print(str(i + 1) + ' ' + str(u + 1))
            Ones.remove(u)
        i = i - 1
if __name__ == '__main__':
    line = int(input())
    n = int(line)
    line = str(input()).split()
    for i in range(n):
        a.append(int(line[i]))
    solution()