Official Analysis

Explanation

It's a bit hard to know where to start with this problem, so let's try a way simpler case: what if all $d[i]$s are either $0$ or $1$?

In this case, $d[i]=0$ means that $i$ is the chosen node (which we can only have one of), and $d[i]=1$ means that it's a direct neighbor (which we can have at most $k$ of).

Now we can extend this to include possibilities where $d[i]=2$. These nodes have to be neighbors of the nodes where $d[i]=1$, so we try to link them up with the direct neighbors of the chosen node.

The only way Valera could've made a mistake is if the number of nodes that are $d+1$ away is greater than $k-1$* times the number of nodes that are $d$ away, since that would force us to allocate more edges than the constraints would allow.

If you know what BFS Trees are, we're basically constructing one of these.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
import sys

node_num, max_adj = [int(i) for i in input().split()]

dists = [[] for _ in range(node_num)]
for n, d in enumerate(input().split()):
	dists[int(d)].append(n)

if len(dists[0]) != 1:
	print(-1)  # only one node can have distance 0

Copy
import java.io.*;
import java.util.*;

public class RestoreGraph {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer initial = new StringTokenizer(read.readLine());
		int nodeNum = Integer.parseInt(initial.nextToken());
		int maxAdj = Integer.parseInt(initial.nextToken());

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {
	int node_num;