AtCoder Regular Contest 103 - Distance Sums

You are given a sequence D_1, D_2, ..., D_N of length N.
The values of D_i are all distinct.
Does a tree with N vertices that satisfies the following conditions exist?
 - The vertices are numbered 1,2,..., N.
 - The edges are numbered 1,2,..., N-1, and Edge i connects Vertex u_i and v_i.
 - For each vertex i, the sum of the distances from i to the other vertices is D_i, assuming that the length of each edge is 1.
If such a tree exists, construct one such tree.

-----Constraints-----
 - 2 \leq N \leq 100000
 - 1 \leq D_i \leq 10^{12}
 - D_i are all distinct.

-----Input-----
Input is given from Standard Input in the following format:
N
D_1
D_2
:
D_N

-----Output-----
If a tree with n vertices that satisfies the conditions does not exist, print -1.
If a tree with n vertices that satisfies the conditions exist, print n-1 lines.
The i-th line should contain u_i and v_i with a space in between.
If there are multiple trees that satisfy the conditions, any such tree will be accepted.

-----Sample Input-----
7
10
15
13
18
11
14
19

-----Sample Output-----
1 2
1 3
1 5
3 4
5 6
6 7

The tree shown below satisfies the conditions.

Difficulty: VERY_HARD

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
d = [int(input()) for _ in range(n)]
r = {v: i for (i, v) in enumerate(d)}
sz = [1] * n
dsorted = sorted(((di, i) for (i, di) in enumerate(d)), reverse=True)
ans = []
to = [[] for _ in range(n)]
for (di, i) in dsorted[:n - 1]:
	nd = di + (sz[i] - 1) - (n - 2 - (sz[i] - 1))
	if not nd in r:
		print(-1)
		exit()
	p = r[nd]
	to[p].append(i)
	sz[p] += sz[i]
	ans.append((i + 1, p + 1))
root = dsorted[-1][1]

def dfs(u, cur=0):
	rv = cur
	for v in to[u]:
		rv += dfs(v, cur + 1)
	return rv
if dfs(root) != d[root]:
	print(-1)
	exit()
for (u, v) in ans:
	print(u, v)


import sys
N = int(input())
Dz = 0
Di = []
d_to_ind = {}
for i in range(N):
	d = int(input())
	if i == 0:
		Dz = d
	Di.append([d, i])
	d_to_ind[d] = i
Di.sort()
Di.reverse()
x = [1] * N
ans = []
lis = [[] for i in range(N)]
for lp in range(N - 1):
	(nowd, nowi) = Di[lp]
	nexd = nowd + 2 * x[nowi] - N
	if nexd >= nowd:
		print(-1)
		sys.exit()
	if nexd not in d_to_ind:
		print(-1)
		sys.exit()
	nexi = d_to_ind[nexd]
	x[nexi] += x[nowi]
	ans.append([nowi + 1, nexi + 1])
	lis[nowi].append(nexi)
	lis[nexi].append(nowi)
from collections import deque
q = deque([0])
dis = [float('inf')] * N
dis[0] = 0
while len(q) > 0:
	now = q.popleft()
	for nex in lis[now]:
		if dis[nex] > dis[now]:
			dis[nex] = dis[now] + 1
			q.append(nex)
if sum(dis) != Dz:
	print(-1)
	sys.exit()
for i in range(N - 1):
	print(ans[i][0], ans[i][1])


import sys
from bisect import bisect_left

def input():
	return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10 ** 6)
n = int(input())
d = [[int(input()), i + 1] for i in range(n)]
check = d[0][0]
d.sort()
ind = [x[1] for x in d]
d = [x[0] for x in d]
if n <= 3:
	print(-1)
	sys.exit()
child = [1 for _ in range(n)]
ans = []
adj = [[] for _ in range(n)]
for i in range(n - 1, 0, -1):
	x = d[i]
	b = bisect_left(d, x - n + 2 * child[i])
	if d[b] != x - n + 2 * child[i] or n <= 2 * child[i]:
		print(-1)
		sys.exit()
	else:
		child[b] += child[i]
		ans.append([ind[b], ind[i]])
		adj[ind[b] - 1].append(ind[i] - 1)
		adj[ind[i] - 1].append(ind[b] - 1)
res = 0

def dfs(x, p, dis):
	global res
	res += dis
	for v in adj[x]:
		if v == p:
			continue
		else:
			dfs(v, x, dis + 1)
	return
dfs(0, -1, 0)
if res == check:
	for a in ans:
		print(*a)
else:
	print(-1)


N = int(input())
numlist = [int(input()) for _ in range(N)]
numdict = {y: x for (x, y) in enumerate(numlist)}
sorted_list = sorted(numdict.items(), reverse=True)
nextS = lambda Snow, child: Snow + 2 * child - N
amount_of_child = [1] * N
sum_of_distance_of_child = [0] * N
branch_list = []
for (S, num) in sorted_list:
	nS = nextS(S, amount_of_child[num])
	if nS in numdict:
		nextnum = numdict[nS]
		branch_list.append([num + 1, nextnum + 1])
		amount_of_child[nextnum] += amount_of_child[num]
		sum_of_distance_of_child[nextnum] += sum_of_distance_of_child[num] + amount_of_child[num]
		if amount_of_child[nextnum] == N:
			break
	else:
		print(-1)
		exit()
if sorted_list[-1][0] == sum_of_distance_of_child[sorted_list[-1][1]]:
	for _ in range(N - 1):
		(x, y) = branch_list.pop()
		print(x, y)
else:
	print(-1)
exit()


from collections import Counter
import sys

def muri():
	print(-1)
	sys.exit()
N = int(input())
D = [int(sys.stdin.readline()) for _ in range(N)]
Didx = list(range(1, N + 1))
Didx.sort(key=lambda x: -D[x - 1])
H = {d: i for (i, d) in enumerate(D, 1)}
H = Counter(H)
D = [0] + D
K = [1] * (N + 1)
Ans = []
for vn in Didx[:-1]:
	p = H[D[vn] - (N - 2 * K[vn])]
	if not p:
		muri()
	Ans.append((vn, p))
	K[p] += K[vn]
s = set()
Edge = [[] for _ in range(N + 1)]
for a in Ans:
	(x, y) = a
	Edge[x].append(y)
	Edge[y].append(x)
dist = [10 ** 9 + 7] * (N + 1)
dist[0] = 0
dist[1] = 0
stack = [1]
visited = set([1])
while stack:
	vn = stack.pop()
	for vf in Edge[vn]:
		if vf not in visited:
			visited.add(vf)
			dist[vf] = 1 + dist[vn]
			stack.append(vf)
if D[1] != sum(dist[1:]):
	muri()
for a in Ans:
	print(*a)


N = int(input())
src = [int(input()) for i in range(N)]
idx = {a: i for (i, a) in enumerate(src)}
size = [1] * N
ss = list(sorted(src))
es = []
while len(ss) > 1:
	a = ss.pop()
	k = size[idx[a]]
	b = a + 2 * k - N
	if b == a or b not in idx:
		print(-1)
		exit()
	size[idx[b]] += k
	es.append((idx[a], idx[b]))
gr = [[] for i in range(N)]
for (a, b) in es:
	gr[a].append(b)
	gr[b].append(a)
from collections import deque
dist = [N] * N
dist[idx[ss[0]]] = 0
q = deque([idx[ss[0]]])
while q:
	v = q.popleft()
	for to in gr[v]:
		if dist[to] < N:
			continue
		q.append(to)
		dist[to] = dist[v] + 1
if all((d < N for d in dist)) and sum(dist) == ss[0]:
	for (a, b) in es:
		print(a + 1, b + 1)
else:
	print(-1)


from sys import stdin, stdout
import numpy as np

def _li():
	return list(map(int, stdin.readline().split()))

def _li_():
	return list([int(x) - 1 for x in stdin.readline().split()])

def _lf():
	return list(map(float, stdin.readline().split()))

def _ls():
	return stdin.readline().split()

def _i():
	return int(stdin.readline())

def _f():
	return float(stdin.readline())

def _s():
	return stdin.readline()[:-1]
d_in = lambda : int(stdin.readline())
ds_in = lambda : list(map(int, stdin.readline().split()))

def print_list(s):
	stdout.write(' '.join(list(map(str, s))) + '\n')

def print_single(s):
	stdout.write(str(s) + '\n')
N = d_in()
D_list = np.array([d_in() for _ in range(N)])
idx = np.argsort(D_list)
sorted_D = D_list[idx]
mapping = []
for j in idx:
	mapping.append(j + 1)
nodes = [1] * N
ans = []
cost = [[0, 1] for _ in range(N)]
for i in range(N - 1, 0, -1):
	d = sorted_D[i]
	sub = nodes[i]
	target = d + 2 * sub - N
	cand = np.searchsorted(sorted_D[:i], target)
	if sorted_D[cand] != target or cand == i:
		print(-1)
		return
	else:
		ans.append((mapping[i], mapping[cand]))
		nodes[cand] += nodes[i]
		cost[cand][0] += cost[i][0] + cost[i][1]
		cost[cand][1] += cost[i][1]
if cost[0][0] != sorted_D[0]:
	print(-1)
	return
else:
	for a in ans:
		print_list(a)


import sys
input = sys.stdin.readline
N = int(input())
D = [None] + [int(input()) for _ in range(N)]
parent = [None] * (N + 1)
size = [None] + [1] * N
d_to_i = {d: i for (i, d) in enumerate(D)}
D_desc = sorted(D[1:], reverse=True)
D_subtree = [0] * (N + 1)
edges = []
bl = True
for d in D_desc[:-1]:
	i = d_to_i[d]
	d_parent = d - N + 2 * size[i]
	if d_parent not in d_to_i:
		bl = False
		break
	p = d_to_i[d_parent]
	edges.append('{} {}'.format(i, p))
	parent[i] = p
	size[p] += size[i]
	D_subtree[p] += D_subtree[i] + size[i]
root = d_to_i[D_desc[-1]]
bl &= D_subtree[root] == D[root]
if bl:
	print('\n'.join(edges))
else:
	print(-1)


import sys
sys.setrecursionlimit(101010)

def dfs(v, adj_list, depth, visited):
	visited[v] = True
	x = depth
	for w in adj_list[v]:
		if not visited[w]:
			x += dfs(w, adj_list, depth + 1, visited)
	return x

def solve(n, d):
	if n < 7:
		print(-1)
		return
	d.sort()
	w = [1] * n
	edges = []
	adj_list = [[] for _ in range(n)]
	for j in range(n - 1, 0, -1):
		(di, i) = d[j]
		pdi = di - n + 2 * w[i]
		p = None
		(lo, hi) = (0, j)
		while lo < hi:
			mid = (lo + hi) // 2
			(xdi, xi) = d[mid]
			if xdi == pdi:
				p = xi
				break
			elif xdi < pdi:
				lo = mid + 1
			else:
				hi = mid
		if p is None:
			print(-1)
			return
		(u, v) = (i, p)
		if v < u:
			(u, v) = (v, u)
		edges.append((u + 1, v + 1))
		adj_list[u].append(v)
		adj_list[v].append(u)
		w[p] += w[i]
	(d0, r) = d[0]
	visited = [False] * n
	x = dfs(r, adj_list, 0, visited)
	if x != d0:
		print(-1)
		return
	edges.sort()
	for uv in edges:
		(u, v) = uv
		print('{} {}'.format(u, v))

def main():
	n = input()
	n = int(n)
	d = []
	for i in range(n):
		di = input()
		di = int(di)
		d.append((di, i))
	solve(n, d)
main()


n = int(input())
a = []
s = []
for i in range(n):
	x = int(input())
	a.append(x * n + i)
	s.append(1)
a.sort()
a.reverse()
a.append(-1)
Sum = 0
Have = True
result = []
for i in range(n - 1):
	l = 0
	r = n
	val = a[i] // n + s[i] + s[i] - n
	while l < r:
		m = (l + r + 2) // 2
		if a[m] >= val * n:
			l = m
		else:
			r = m - 1
	if a[l] // n != val:
		Have = False
		break
	s[l] += s[i]
	Sum += s[i]
	result.append([a[i] % n, a[l] % n])
if Sum != a[n - 1] // n:
	Have = False
if Have == False:
	print('-1')
else:
	for e in result:
		print(e[0] + 1, end=' ')
		print(e[1] + 1)


def solve():
	N = int(input())
	D = [int(input()) for i in range(N)]
	if sum(D) % 2 > 0:
		print('-1')
		return
	Di = sorted([(di, i) for (i, di) in enumerate(D)], key=lambda x: x[0], reverse=True)
	d_to_i = {dd: i for (dd, i) in Di}
	ans = []
	n_child = [1] * N
	d_child = [0] * N
	for (valD, node) in Di:
		valD_par = valD - N + 2 * n_child[node]
		if valD_par in d_to_i.keys():
			node_par = d_to_i[valD_par]
			ans.append((node_par + 1, node + 1))
			n_child[node_par] += n_child[node]
			d_child[node_par] += n_child[node] + d_child[node]
			if n_child[node_par] == N:
				break
		else:
			print('-1')
			return
	(d_min, i_min) = Di[-1]
	if d_child[i_min] != d_min:
		print('-1')
		return
	for (i, j) in ans:
		print(str(i) + ' ' + str(j))
solve()


from collections import defaultdict
N = int(input())
C = defaultdict(int)
for i in range(N):
	D = int(input())
	C[D] = i + 1
E = []
H = [1] * (N + 1)
DD = sorted([[k, v] for (k, v) in C.items()], reverse=True)
Adj = [[] for i in range(N)]
for (D, n) in DD[:-1]:
	try:
		p = C[D - N + 2 * H[n]]
		if n == p:
			raise Error
		E.append([n, p])
		Adj[n - 1].append(p - 1)
		Adj[p - 1].append(n - 1)
		H[p] += H[n]
	except:
		print(-1)
		break
else:
	dist = [N] * N
	dist[DD[-1][1] - 1] = 0
	Q = [DD[-1][1] - 1] + [N] * N
	tail = 1
	for i in range(N):
		s = Q[i]
		if s == N:
			print(-1)
			break
		for adj in Adj[s]:
			if dist[adj] == N:
				dist[adj] = dist[s] + 1
				Q[tail] = adj
				tail += 1
	else:
		if sum(dist) == DD[-1][0]:
			for e in E:
				print(e[0], e[1])
		else:
			print(-1)


def solve(n, ddd):
	dsd = {d: i for (i, d) in enumerate(ddd)}
	child_cnt = [1] * n
	child_dist = [0] * n
	buf = []
	srt = sorted(list(dsd.items()), reverse=True)
	for (d, i) in srt[:-1]:
		cc = child_cnt[i]
		pd = d - (n - cc * 2)
		if pd == d or pd not in dsd:
			return -1
		pi = dsd[pd]
		buf.append((pi + 1, i + 1))
		child_cnt[pi] += cc
		child_dist[pi] += child_dist[i] + cc
	(md, mi) = srt[-1]
	if md != child_dist[mi]:
		return -1
	return buf
n = int(input())
ddd = list(map(int, (input() for _ in range(n))))
res = solve(n, ddd)
if res == -1:
	print(-1)
else:
	print('\n'.join(('{} {}'.format(*l) for l in res)))


n = int(input())
d = [int(input()) for i in range(n)]
if sum(d) % 2 > 0:
	print(-1)
	exit()
d = sorted([(dd, i) for (i, dd) in enumerate(d)], reverse=True)
d_to_i = {dd: i for (dd, i) in d}
n_child = [1] * n
d_child = [0] * n
ans = []
for (dd, i) in d:
	d_i = dd + 2 * n_child[i] - n
	if d_i in d_to_i.keys():
		i_next = d_to_i[d_i]
		ans.append((i + 1, i_next + 1))
		n_child[i_next] += n_child[i]
		d_child[i_next] += d_child[i] + n_child[i]
		if n_child[i_next] == n:
			break
	else:
		print(-1)
		exit()
(d_min, i_min) = d[-1]
if d_min == d_child[i_min]:
	for a in ans:
		print(*a)
else:
	print(-1)


(n, *d) = map(int, open(0).read().split())
z = {j: i for (i, j) in enumerate(d)}
(*s,) = sorted(d)
P = [-1] * n
S = {i: 1 for i in d}
D = {i: 0 for i in d}
ok = 1
for v in s[n - 1:0:-1]:
	p = v - n + 2 * S[v]
	if p >= v:
		ok = 0
	if p in z:
		S[p] += S[v]
		D[p] += D[v] + S[v]
		P[z[v]] = z[p]
	else:
		ok = 0
if ok and D[s[0]] == s[0]:
	for (i, pi) in enumerate(P):
		if pi != -1:
			print(i + 1, pi + 1)
else:
	print(-1)


(n, *d) = map(int, open(0).read().split())
zd = {di: i for (i, di) in enumerate(d)}
(*sd,) = sorted(d)
parent = [-1] * n
size = {i: 1 for i in d}
dist = {i: 0 for i in d}
ok = 1
for v in sd[n - 1:0:-1]:
	p = v - n + 2 * size[v]
	if p >= v:
		ok = 0
		break
	if p in zd:
		size[p] += size[v]
		dist[p] += dist[v] + size[v]
		parent[zd[v]] = zd[p]
	else:
		ok = 0
		break
if dist[sd[0]] != sd[0]:
	ok = 0
if ok:
	for (i, pi) in enumerate(parent):
		if pi != -1:
			print(i + 1, pi + 1)
else:
	print(-1)


def main():
	N = int(input())
	D = [int(input()) for i in range(N)]
	C = [1] * N
	T = [0] * N
	DI = {}
	for i in range(len(D)):
		DI[D[i]] = i
	D = sorted(D)
	P = [-1] * N
	while len(D) > 1:
		d = D.pop()
		i = DI[d]
		nd = d - N + C[i] * 2
		if nd in DI:
			ni = DI[nd]
		else:
			print(-1)
			return
		P[i] = ni
		C[ni] += C[i]
		T[ni] += T[i] + C[i]
	if D[0] == T[DI[D[0]]]:
		for i in range(N):
			if P[i] >= 0:
				print(i + 1, P[i] + 1)
	else:
		print(-1)
main()