Graph And Its Complement
Contest: Educational Codeforces Round 45 (Rated for Div. 2)
Difficulty rating: 1700
Tags: constructive algorithms, graphs, implementation

Given three numbers $$$n, a, b$$$. You need to find an adjacency matrix of such an undirected graph that the number of components in it is equal to $$$a$$$, and the number of components in its complement is $$$b$$$. The matrix must be symmetric, and all digits on the main diagonal must be zeroes.

In an undirected graph loops (edges from a vertex to itself) are not allowed. It can be at most one edge between a pair of vertices.

The adjacency matrix of an undirected graph is a square matrix of size $$$n$$$ consisting only of "0" and "1", where $$$n$$$ is the number of vertices of the graph and the $$$i$$$-th row and the $$$i$$$-th column correspond to the $$$i$$$-th vertex of the graph. The cell $$$(i,j)$$$ of the adjacency matrix contains $$$1$$$ if and only if the $$$i$$$-th and $$$j$$$-th vertices in the graph are connected by an edge.

A connected component is a set of vertices $$$X$$$ such that for every two vertices from this set there exists at least one path in the graph connecting this pair of vertices, but adding any other vertex to $$$X$$$ violates this rule.

The complement or inverse of a graph $$$G$$$ is a graph $$$H$$$ on the same vertices such that two distinct vertices of $$$H$$$ are adjacent if and only if they are not adjacent in $$$G$$$.

Input format:
In a single line, three numbers are given $$$n, a, b \,(1 \le n \le 1000, 1 \le a, b \le n)$$$: is the number of vertexes of the graph, the required number of connectivity components in it, and the required amount of the connectivity component in it's complement.

Output format:
If there is no graph that satisfies these constraints on a single line, print "NO" (without quotes).

Otherwise, on the first line, print "YES"(without quotes). In each of the next $$$n$$$ lines, output $$$n$$$ digits such that $$$j$$$-th digit of $$$i$$$-th line must be $$$1$$$ if and only if there is an edge between vertices $$$i$$$ and $$$j$$$ in $$$G$$$ (and $$$0$$$ otherwise). Note that the matrix must be symmetric, and all digits on the main diagonal must be zeroes.

If there are several matrices that satisfy the conditions — output any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3 1 2

Example output:
YES
001
001
110

Example input:
3 3 3

Example output:
NO

Editorial:
Let's prove that if $$$a > 1$$$, then $$$b = 1$$$. Let $$$G$$$ be the original graph, and $$$H$$$ — the complement of the graph $$$G$$$. Let's look at each pair of vertices $$$(u, v)$$$. If $$$u$$$ and $$$v$$$ belong to different components of the graph $$$G$$$, then there is an edge between them in the graph $$$H$$$. Otherwise, $$$u$$$ and $$$v$$$ belong to the same component of the graph $$$G$$$, but since $$$G$$$ has more than one component, there is vertex $$$x$$$ in other component of $$$G$$$, and there are edges $$$\{u,x\}$$$ and $$$\{v, x\}$$$ in $$$H$$$. That's why, there is a connected path for any pair of vertices $$$(u, v)$$$, and the graph $$$H$$$ is connected. Similarly, the case $$$b > 1$$$ is proved.
So, if $$$min(a, b) > 1$$$, then the answer is "NO". Otherwise, $$$min(a, b) = 1$$$. Consider the case where $$$b = 1$$$ (if $$$b > a$$$, we can swap $$$a$$$ and $$$b$$$, and output complement of the constructed graph). To have $$$a$$$ components in the graph $$$G$$$, it is enough to connect the vertex $$$1$$$ with the vertex $$$2$$$, the vertex $$$2$$$ with the vertex $$$3$$$, $$$\cdots$$$, the vertex $$$n - a$$$ with the vertex $$$n - a + 1$$$.
A particular cases are the tests $$$n = 2, a = 1, b = 1$$$ and $$$ n = 3, a = 1, b = 1$$$. There is no suitable graph for them.