DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Graph Construction

Back to problem

Editorial

Let RiR_iRi​ be the number of edges from vertex iii to a vertex with a larger index, and let LiL_iLi​ be the number of edges from a vertex with a smaller index to vertex iii. Then Li+Ri=DiL_i+R_i=D_iLi​+Ri​=Di​.

Set X0=0X_0=0X0​=0 and L0=0L_0=0L0​=0. When moving from Xi 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

Ri=Xi−Xi−1+Li−1,Li=Di−Ri.R_i=X_i-X_{i-1}+L_{i-1},\qquad L_i=D_i-R_i.Ri​=Xi​−X

For every iii, we must have 0≤Ri≤N−i0\le R_i\le N-i0≤Ri​≤N−i and 0≤Li≤i−10\le L_i\le i-1. If any condition fails, print .

Now process the vertices from 111 to NNN. For every previously processed vertex, maintain how many edges it still has to create toward vertices with larger indices. When processing vertex iii, exactly LiL_iLi​ previous vertices must be connected to ii.

Choose the LiL_iLi​ vertices with the largest remaining values. Store (remaining edges,vertex index)(\text{remaining edges},\text{vertex index})(remaining edges,vertex index) in a max-priority queue. Each time a pair with vertex vvv is popped, add edge (v,i)(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 iii is connected to a previous vertex yyy but not to another previous vertex xxx. Suppose their current remaining values satisfy rx≥ryr_x\ge r_yrx​≥.

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

−1X_{i-1}
Xi−1​
XiX_iXi​
RiR_iRi​
iii
Li−1L_{i-1}Li−1​
i−1i-1i−1
Xi−Xi−1=Ri−Li−1,X_i-X_{i-1}=R_i-L_{i-1},Xi​−Xi−1​=Ri​−Li−1​,
Li,RiL_i,R_iLi​,Ri​
i−1​
+
Li−1​,Li​=
Di​−
Ri​.
0
≤
Li​≤
i−
1
−1-1−1
i
(v,i)
111
LiL_iLi​
(Ri,i)(R_i,i)(Ri​,i)
000
000
ry​

After using the edge to iii, vertex yyy still uses ry−1r_y-1ry​−1 edges to later vertices, while xxx uses rxr_xrx​ such edges. Therefore, there must be some vertex k>ik>ik>i such that (x,k)(x,k)(x,k) is an edge and (y,k)(y,k)(y,k) is not. Otherwise every later neighbor of xxx would also be a later neighbor of yyy, implying rx≤ry−1r_x\le r_y-1rx​≤ry​−1, a contradiction.

We can delete (y,i)(y,i)(y,i) and (x,k)(x,k)(x,k) and add (x,i)(x,i)(x,i) and (y,k)(y,k)(y,k). This preserves every degree and every required number of left/right edges. Thus, whenever a feasible solution exists, there is also a feasible solution that prefers a vertex with a larger remaining value at the current step.

Repeating this exchange shows that choosing the largest LiL_iLi​ remaining values at every step preserves feasibility. Therefore, if the priority-queue algorithm fails, no valid graph exists. Conversely, if it succeeds, the edges recorded by the algorithm satisfy every Li,RiL_i,R_iLi​,Ri​ requirement and therefore form a valid graph.

)
O(N2)O(N^2)O(N2)

Solution written by GPT5.6