Mock CCC '18 Contest 3 S4 - A Graph Problem - Olympiads Online Judge

Mock CCC '18 Contest 3 S4 - A Graph Problem

Points: 10

Time limit: 0.6s

Memory limit: 1G

Problem type

Given an undirected weighted graph where there is an edge between every pair of distinct vertices of nonnegative integer weight, let $a_i$ $a_{i}$ be the sum of the weights of the edges incident on vertex $i$ $i$ .

Given a sequence of integers $b_1$ $b_{1}$ through $b_N$ $b_{N}$ , determine if it is possible to construct a graph of $n$ $n$ vertices such that $a_i = b_i$ $a_{i} = b_{i}$ for every vertex in the graph.

Constraints

$1 \le N \le 50$ $1 \leq N \leq 50$

$1 \le b_i \le 10^9$ $1 \leq b_{i} \leq 10^{9}$

There is no opportunity for partial credit on this problem.

Input Specification

The first line contains a single integer, $N$ $N$ .

Each of the next $N$ $N$ lines contains a single integer, $b_1$ $b_{1}$ through $b_N$ $b_{N}$ in order.

Output Specification

Output YES if it is possible to construct such a graph. Output NO otherwise.

Sample Input 1

Copy

Sample Output 1

Copy

YES

Sample Input 2

Copy

Sample Output 2

Copy

NO

Comments

1

Dan13llljws commented on Dec. 8, 2019, 11:34 p.m. ← edited →

It doesnt make sense if you only have one node but you cannot make a graph