Construct an Array (Easy Version)

The intimidating pile of inequalities is really just an ordering problem wearing a fake mustache.

1. Every pair is present

There are exactly

$$\frac{n(n+1)}2$$

pairs $(i,j)$ satisfying $1\le i\le j\le n$. The input contains exactly that many restrictions, and no pair occurs twice. Therefore every possible pair occurs exactly once, including every diagonal pair $(i,i)$.

Let $c_{ij}\in\{1,2\}$ denote the restriction type for $(i,j)$.

2. Diagonal restrictions fix all signs

For $(i,i)$, the constrained sum is $2a_i$:

• If $c_{ii}=1$, then $2a_i\ge0$, hence $a_i\ge0$.
• If $c_{ii}=2$, then $2a_i<0$, hence $a_i<0$.

So the indices are split into a non-negative group $P$ and a negative group $N$.

This immediately settles pairs whose endpoints are in the same group:

• If $i,j\in P$, then $a_i+a_j\ge0$ automatically. Their restriction must be type $1$.
• If $i,j\in N$, then $a_i+a_j<0$ automatically. Their restriction must be type $2$.

If either rule is violated, the answer is NO. Otherwise, same-group pairs impose nothing else.

3. Cross-group restrictions compare magnitudes

Consider $p\in P$ and $q\in N$. Define positive-side magnitudes

$$x_p=a_p,\qquad x_q=-a_q.$$

Here $x_p\ge0$ and $x_q>0$, and

$$a_p+a_q=x_p-x_q.$$

Therefore:

| Restriction | Required comparison | Directed edge | |---|---:|---:| | $c_{pq}=1$ | $x_q\le x_p$ | $q\to p$ | | $c_{pq}=2$ | $x_p<x_q$ | $p\to q$ |

Build a directed graph using exactly these edges for all cross-group pairs. Intuitively, an edge points from the endpoint that may receive the smaller magnitude toward the endpoint that must receive the larger one.

The first relation is non-strict, but we will deliberately satisfy it strictly. That is allowed: $x_q<x_p$ certainly implies $x_q\le x_p$. The only question is whether making every edge strict could create a fake impossibility. It does not.

4. Why cycles are exactly the obstruction

Every graph edge joins $P$ and $N$, so the graph is bipartite.

Suppose it contains a directed cycle. While following that cycle:

• An edge from $N$ to $P$ represents a non-strict comparison $x_N\le x_P$.
• An edge from $P$ to $N$ represents a strict comparison $x_P<x_N$.

A cycle alternates between the two groups, so it contains at least one edge of the second kind. Chaining all comparisons around the cycle gives

$$x_v\le\cdots <\cdots\le x_v,$$

which implies $x_v<x_v$. That is impossible. Hence any feasible instance must produce a DAG.

Now suppose the graph is acyclic. Take any topological order

$$v_1,v_2,\ldots,v_n$$

and assign

$$x_{v_k}=k.$$

Every edge $u\to v$ goes forward in the topological order, so $x_u<x_v$. Consequently:

• For a type-$1$ cross pair, the edge is $q\to p$, giving $x_q<x_p$, which is stronger than the required $x_q\le x_p$.
• For a type-$2$ cross pair, the edge is $p\to q$, giving exactly the required $x_p<x_q$.

Finally restore the signs fixed by the diagonal:

$$a_i= \begin{cases} x_i,&c_{ii}=1,\\ -x_i,&c_{ii}=2. \end{cases}$$

All assigned magnitudes are positive. That is fine even though the first group merely permits zero; nobody said we had to use it.

5. Algorithm

1. Store all restriction types in a symmetric matrix.
2. For every pair $i<j$:
   • If their diagonal types are equal, verify that their pair type is the same forced type.
   • Otherwise identify the non-negative endpoint $p$ and negative endpoint $q$. Add $q\to p$ for type $1$, or $p\to q$ for type $2$.
3. If a same-group check failed, print NO.
4. Run Kahn's topological sort on the directed graph.
5. When the $k$-th vertex is removed from the queue, give it magnitude $k$ and the sign dictated by its diagonal.
6. If fewer than $n$ vertices are removed, a directed cycle exists, so print NO. Otherwise print the constructed array.

Correctness proof

Lemma 1. A same-group pair is satisfiable exactly when its restriction has the forced type checked by the algorithm.

Proof. Two non-negative values always have a non-negative sum, so only type $1$ works. Two negative values always have a negative sum, so only type $2$ works. These conclusions do not depend on the chosen magnitudes. $\square$

Lemma 2. If the cross-group graph has a directed cycle, no valid array exists.

Proof. The cycle alternates between $P$ and $N$. Its $N\to P$ edges encode non-strict magnitude inequalities, while its $P\to N$ edges encode strict ones. There is at least one strict edge, so chaining the inequalities around the cycle states that one magnitude is strictly smaller than itself, a contradiction. $\square$

Lemma 3. If all same-group checks pass and the cross-group graph is acyclic, the algorithm's array satisfies every restriction.

Proof. Topological ranks strictly increase along every edge. Thus every type-$1$ cross pair has negative-side magnitude smaller than positive-side magnitude, making its sum non-negative, and every type-$2$ cross pair has positive-side magnitude smaller, making its sum negative. Lemma 1 handles all same-group pairs. The assigned signs also satisfy every diagonal restriction. Since every possible pair appears in the input, all restrictions are covered. $\square$

Theorem. The algorithm prints YES with a valid array if and only if such an array exists.

Proof. If it prints YES, validity follows from Lemma 3. If it prints NO, either a same-group restriction is impossible by Lemma 1, or topological sorting found a cycle, which is impossible by Lemma 2. Thus it rejects exactly the infeasible instances. $\square$

Complexity

The matrix scan and graph construction take $O(n^2)$ time. Topological sorting takes $O(n+E)=O(n^2)$ time, and the matrix plus graph use $O(n^2)$ memory. The output values satisfy $|a_i|\le n\le1000$, comfortably below $10^9$.