Graph Construction

Let $R_i$ be the number of edges from vertex $i$ to a vertex with a larger index, and let $L_i$ be the number of edges from a vertex with a smaller index to vertex $i$. Then $L_i+R_i=D_i$.

Set $X_0=0$ and $L_0=0$. When moving from $X_i$ to , the edges whose left endpoint is become newly included, while the edges whose right endpoint is are removed. Hence and we can uniquely recover from left to right by

$$R_i=X_i-X_{i-1}+L_{i-1},\qquad L_i=D_i-R_i.$$

For every $i$, we must have $0\le R_i\le N-i$ and $0\le L_i\le i-1$. If any condition fails, print .

Now process the vertices from $1$ to $N$. For every previously processed vertex, maintain how many edges it still has to create toward vertices with larger indices. When processing vertex $i$, exactly $L_i$ previous vertices must be connected to $i$.

Choose the $L_i$ vertices with the largest remaining values. Store $(\text{remaining edges},\text{vertex index})$ in a max-priority queue. Each time a pair with vertex $v$ is popped, add edge $(v,i)$ to the answer, decrease its remaining value by , and insert it again. After choosing vertices, insert . If there are too few vertices or the largest remaining value is , the construction is impossible. After processing all vertices, also verify that every remaining value is .

If the process succeeds, the recorded edges form a valid graph, so print the number of edges and the edge list.

Proof

Consider any feasible graph in which the current vertex $i$ is connected to a previous vertex $y$ but not to another previous vertex $x$. Suppose their current remaining values satisfy $r_x\ge r_y$.

Let $M$ be the number of printed edges. There are $O(N+M)$ priority-queue operations, so the time complexity is $O(N^2\log N)$. Storing the constructed edges uses space in the worst case.